Jordi Castellví Foguet

We study random \(k\)-connected chordal graphs with bounded tree-width. Our main results are scaling limits and quenched local limits.

Given \(t\geq 2\) and \(0\leq k\leq t\), we prove that the number of labelled \(k\)-connected chordal graphs with \(n\) vertices and tree-width at most \(t\) is asymptotically \(c n^{-5/2} \gamma^n n!\), as \(n\to\infty\), for some constants \(c,\gamma >0\) depending on \(t\) and \(k\). Additionally, we show that the number of \(i\)-cliques (\(2\leq i\leq t\)) in a uniform random \(k\)-connected chordal graph with tree-width at most \(t\) is normally distributed as \(n\to\infty\).

The asymptotic enumeration of graphs of tree-width at most \(t\) is wide open for \(t\geq 3\). To the best of our knowledge, this is the first non-trivial class of graphs with bounded tree-width where the asymptotic counting problem is solved. Our starting point is the work of Wormald [Counting Labelled Chordal Graphs, Graphs and Combinatorics (1985)], were an algorithm is developed to obtain the exact number of labelled chordal graphs on \(n\) vertices.

We determine the number of labelled chordal planar graphs with \(n\) vertices, which is asymptotically \(c_1\cdot n^{-5/2} \gamma^n n!\) for a constant \(c_1>0\) and \(\gamma \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} \delta^n\), where \(\delta = 1/\sigma \approx 6.40375\), and \(\sigma\) 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.

Bousquet-Mélou and Schaeffer gave in 2000 a bijective enumeration of some planar maps called constellations. In 2019, Lepoutre described a bijection between bicolorable maps of arbitrary genus and some unicellular maps of the same genus.

We present a bijection between constellations of higher genus and some unicellular maps that generalizes both existing bijections at the same time.

Using this bijection, we manage to enumerate a subclass of constellations on the torus, proving that its generating function is a rational function of the generating function of some trees.

We determine the number of labelled chordal planar graphs with \(n\) vertices, which is asymptotically \(c_1\cdot n^{-5/2} \gamma^n n!\) for a constant \(c_1>0\) and \(\gamma \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} \delta^n\), where \(\delta = 1/\sigma \approx 6.40375\), and \(\sigma\) 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.

A graph is chordal if it has no induced cycle of length greater than three. This talk is mainly devoted to the enumerative study of labelled chordal planar graphs. We follow the canonical decomposition of graphs into \(k\)-connected components for \(k = 1, 2, 3\) and we make use of the dissymmetry theorem to keep our proofs purely combinatorial. The 3-connected graphs in this family are precisely chordal triangulations: the ones obtained starting from a \(K_4\) and repeatedly adding vertices adjacent to an existing triangular face. We then consider networks, which are 2-connected labelled chordal planar graphs rooted at a directed edge whose vertices have no labels. From the generating function of networks, we obtain the generating functions of 2-connected, connected and, finally, general labelled chordal planar graphs. The singularity analysis of the resulting equations leads to our main result: the number of labelled chordal planar graphs with \(n\) vertices is asymptotically \(c_1 n^{-5/2} \gamma^n n!\), where \(c_1 > 0\) is a constant and \(\gamma \approx 11.89235\). Using the same techniques, we also determine the number of rooted simple chordal planar maps with \(n\) edges, which is asymptotically \(c_2 n^{-3/2} \delta^n\), where \(\delta = 1 / \sigma \approx 6.40375\), and \(\sigma\) is an algebraic number of degree 12.

Work in collaboration with Marc Noy and Clément Requilé.

Given \(t\geq 2\) and \(0\leq k\leq t\), we prove that the number of labelled \(k\)-connected chordal graphs with \(n\) vertices and tree-width at most \(t\) is asymptotically \(c n^{-5/2} \gamma^n n!\), as \(n\to\infty\), for some constants \(c,\gamma >0\) depending on \(t\) and \(k\). Additionally, we show that the number of \(i\)-cliques (\(2\leq i\leq t\)) in a uniform random \(k\)-connected chordal graph with tree-width at most \(t\) is normally distributed as \(n\to\infty\).

The asymptotic enumeration of graphs of tree-width at most \(t\) is wide open for \(t\geq 3\). To the best of our knowledge, this is the first non-trivial class of graphs with bounded tree-width where the asymptotic counting problem is solved. Our starting point is the work of Wormald [Counting Labelled Chordal Graphs, Graphs and Combinatorics (1985)], were an algorithm is developed to obtain the exact number of labelled chordal graphs on \(n\) vertices.