Source author record

Marc Noy

Explore this author’s publications, collaborators and research topics. This catalog record has not been claimed by its author.

ResearcherUnclaimed source record

math.CO Data Structures and Algorithms Discrete Mathematics math.LO

Catalog footprint

Research overview

10works

4topics

4close collaborators

Actions

Is this your work?

Open graph Browse papers

preprint2022arXiv

Enumeration of chordal planar graphs and maps

We determine the number of labelled chordal planar graphs with $n$ vertices, which is asymptotically $c_1\cdot n^{-5/2} γ^n n!$ for a constant $c_1>0$ and $γ\approx 11.89235$ . We also determine the number of rooted simple chordal planar maps with $n$ edges, which is asymptotically $c_2 n^{-3/2} δ^n$ , where $δ= 1/σ\approx 6.40375$ , and $σ$ is an algebraic number of degree 12. The proofs are based on combinatorial decompositions and singularity analysis. Chordal planar graphs (or maps) are a natural example of a subcritical class of graphs in which the class of 3-connected graphs is relatively rich. The 3-connected members are precisely chordal triangulations, those obtained starting from $K_4$ by repeatedly adding vertices adjacent to an existing triangular face.

preprint2020arXiv

Limiting probabilities of first order properties of random sparse graphs and hypergraphs

Let $G_n$ be the binomial random graph $G(n,p=c/n)$ in the sparse regime, which as is well-known undergoes a phase transition at $c=1$ . Lynch (Random Structures Algorithms, 1992) showed that for every first order sentence $ϕ$ , the limiting probability that $G_n$ satisfies $ϕ$ as $n\to\infty$ exists, and moreover it is an analytic function of $c$ . In this paper we consider the closure $\overline{L_c}$ in $[0,1]$ of the set $L_c$ of all limiting probabilities of first order sentences in $G_n$ . We show that there exists a critical value $c_0 \approx0.93$ such that $\overline{L_c}= [0,1]$ when $c \ge c_0$ , whereas $\overline{L_c}$ misses at least one subinterval when $c<c_0$ . We extend these results to random $d$ -uniform sparse hypergraphs, where the probability of a hyperedge is given by $p=c/n^{d-1}$ .

preprint2020arXiv

Universal singular exponents in catalytic variable equations

Catalytic equations appear in several combinatorial applications, most notably in the numeration of lattice path and in the enumeration of planar maps. The main purpose of this paper is to show that the asymptotic estimate for the coefficients of the solutions of (so-called) positive catalytic equations has a universal asymptotic behavior. In particular, this provides a rationale why the number of maps of size $n$ in various planar map classes grows asymptotically like $c\cdot n^{-5/2} γ^n$ , for suitable positive constants $c$ and $γ$ . Essentially we have to distinguish between linear catalytic equations (where the subexponential growth is $n^{-3/2}$ ) and non-linear catalytic equations (where we have $n^{-5/2}$ as in planar maps). Furthermore we provide a quite general central limit theorem for parameters that can be encoded by catalytic functional equations, even when they are not positive.

preprint2016arXiv

The number of labeled graphs of bounded treewidth

We focus on counting the number of labeled graphs on $n$ vertices and treewidth at most $k$ (or equivalently, the number of labeled partial $k$ -trees), which we denote by $T_{n,k}$ . So far, only the particular cases $T_{n,1}$ and $T_{n,2}$ had been studied. We show that $\left(c \cdot \frac{k\cdot 2^k \cdot n}{\log k} \right)^n \cdot 2^{-\frac{k(k+3)}{2}} \cdot k^{-2k-2}\ \leq\ T_{n,k}\ \leq\ \left(k \cdot 2^k \cdot n\right)^n \cdot 2^{-\frac{k(k+1)}{2}} \cdot k^{-k},$ for $k > 1$ and some explicit absolute constant $c > 0$ . The upper bound is an immediate consequence of the well-known number of labeled $k$ -trees, while the lower bound is obtained from an explicit algorithmic construction. It follows from this construction that both bounds also apply to graphs of pathwidth and proper-pathwidth at most $k$ .

preprint2013arXiv

Maximum degree in minor-closed classes of graphs

Given a class of graphs G closed under taking minors, we study the maximum degree Δ_n of random graphs from G with n vertices. We prove several lower and upper bounds that hold with high probability. Among other results, we find classes of graphs providing orders of magnitude for Δ_n not observed before, such us \log n/ \log \log \log n and \log n/ \log \log \log \log n.

preprint2012arXiv

Clusters, generating functions and asymptotics for consecutive patterns in permutations

We use the cluster method to enumerate permutations avoiding consecutive patterns. We reprove and generalize in a unified way several known results and obtain new ones, including some patterns of length 4 and 5, as well as some infinite families of patterns of a given shape. By enumerating linear extensions of certain posets, we find a differential equation satisfied by the inverse of the exponential generating function counting occurrences of the pattern. We prove that for a large class of patterns, this inverse is always an entire function. We also complete the classification of consecutive patterns of length up to 6 into equivalence classes, proving a conjecture of Nakamura. Finally, we show that the monotone pattern asymptotically dominates (in the sense that it is easiest to avoid) all non-overlapping patterns of the same length, thus proving a conjecture of Elizalde and Noy for a positive fraction of all patterns.

preprint2012arXiv

On the probability of planarity of a random graph near the critical point

Consider the uniform random graph $G(n,M)$ with $n$ vertices and $M$ edges. Erdős and Rényi (1960) conjectured that the limit $$ \lim_{n \to \infty} \Pr\{G(n,\textstyle{n\over 2}) is planar}} $$ exists and is a constant strictly between 0 and 1. Łuczak, Pittel and Wierman (1994) proved this conjecture and Janson, Łuczak, Knuth and Pittel (1993) gave lower and upper bounds for this probability. In this paper we determine the exact probability of a random graph being planar near the critical point $M=n/2$ . For each $λ$ , we find an exact analytic expression for $p(λ) = \lim_{n \to \infty} \Pr{G(n,\textstyle{n\over 2}(1+λn^{-1/3})) is planar}.$ In particular, we obtain $p(0) \approx 0.99780$ . We extend these results to classes of graphs closed under taking minors. As an example, we show that the probability of $G(n,\textstyle{n\over 2})$ being series-parallel converges to 0.98003. For the sake of completeness and exposition we reprove in a concise way several basic properties we need of a random graph near the critical point.

preprint2010arXiv

Asymptotic enumeration and limit laws for graphs of fixed genus

It is shown that the number of labelled graphs with n vertices that can be embedded in the orientable surface S_g of genus g grows asymptotically like $c^{(g)}n^{5(g-1)/2-1}γ^n n!$ where $c^{(g)}>0$ , and $γ\approx 27.23$ is the exponential growth rate of planar graphs. This generalizes the result for the planar case g=0, obtained by Gimenez and Noy. An analogous result for non-orientable surfaces is obtained. In addition, it is proved that several parameters of interest behave asymptotically as in the planar case. It follows, in particular, that a random graph embeddable in S_g has a unique 2-connected component of linear size with high probability.

preprint2010arXiv

The maximum degree of planar graphs I. Series-parallel graphs

We prove that the maximum degree $Δ_n$ of a random series-parallel graph with $n$ vertices satisfies $Δ_n/\log n \to c$ in probability, and $\mathbb{E}\, Δ_n \sim c \log n$ for a computable constant $c>0$ . The same result holds for outerplanar graphs.

preprint2008arXiv

Bijections for Baxter Families and Related Objects

The Baxter number can be written as $B_n = \sum_0^n Θ_{k,n-k-1}$ . These numbers have first appeared in the enumeration of so-called Baxter permutations; $B_n$ is the number of Baxter permutations of size $n$ , and $Θ_{k,l}$ is the number of Baxter permutations with $k$ descents and $l$ rises. With a series of bijections we identify several families of combinatorial objects counted by the numbers $Θ_{k,l}$ . Apart from Baxter permutations, these include plane bipolar orientations with $k+2$ vertices and $l+2$ faces, 2-orientations of planar quadrangulations with $k+2$ white and $l+2$ black vertices, certain pairs of binary trees with $k+1$ left and $l+1$ right leaves, and a family of triples of non-intersecting lattice paths. This last family allows us to determine the value of $Θ_{k,l}$ as an application of the lemma of Gessel and Viennot. The approach also allows us to count certain other subfamilies, e.g., alternating Baxter permutations, objects with symmetries and, via a bijection with a class of plan bipolar orientations also Schnyder woods of triangulations, which are known to be in bijection with 3-orientations.

Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.