ETH Zurich

In the past decades the $G_{n,p}$ model of random graphs has led to numerous beautiful and deep theorems. A key feature that is used in basically all proofs is that edges in $G_{n,p}$ appear independently.

The independence of the edges allows, for example, to obtain extremely tight bounds on the number of edges of $G_{n,p}$ and its degree sequence by straightforward applications of Chernoff bounds. This situation changes dramatically if one considers graph classes with structural side constraints. In this talk we show how recent progress in the construction of so-called Boltzmann samplers by Duchon, Flajolet, Louchard, and Schaeffer can be used to reduce the study of degree sequences and subgraph counts to properties of sequences of independent and identically distributed random variables -- to which we can then again apply Chernoff bounds to obtain extremely tight results. As proof of concept we study properties of random graphs that are drawn uniformly at random from the class consisting of the dissections of large convex polygons. We obtain 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.