On properties of random dissections and triangulations (Q653837): Difference between revisions

A dissection of a convex \(n\)-gon is a partition of the polygon into polygonal regions by means of non-crossing diagonals, whereas triangulations are a special case of dissections with all regions being triangles. For a random triangulation, \textit{Z. Gao} and \textit{N.C. Wormald} [``The distribution of the maximum vertex degree in random planar maps,'' J. Comb. Theory, Ser. A 89, No.\,2, 201--230 (2000; Zbl 0944.05057)] used methods from analytic combinatorics to determine the limiting distribution of the maximum vertex degree, and obtained some precise bounds on the number of vertices of degree \(k\). The paper studies properties of random graphs that are drawn uniformly at random from the class consisting of biconnected outerplanar graphs, or equivalently dissections of large convex polygons. It also obtains very sharp concentration results for the number of vertices of any given degree, and for the number of induced copies of a given fixed graph. The proposed method gives similar results for random graphs from the class of triangulations of convex polygons. It also shows that recent progress in the construction of so-called Boltzmann samplers can be used to reduce the study of degree sequences and subgraph counts to properties of sequences of independent and identically distributed random variables, thereby applying standard Chernoff bounds to obtain extremely tight results.