Random Perfect Graphs

We investigate the asymptotic structure of a random perfect graph $P_n$ sampled uniformly from the perfect graphs on vertex set $\{1,\dots ,n\}$. Our approach is based on the result of Pr"omel and Steger that almost all perfect graphs are generalised split graphs, together with a method to generate such graphs almost uniformly. We show that the distribution of the maximum of the stability number $\alpha (P_n)$ and clique number $\omega (P_n)$ is close to a concentrated distribution $L(n)$ which plays an important role in our generation method. We also prove that the probability that $P_n$ contains any given graph $H$ as an induced subgraph is asymptotically $0$ or $\frac{1}{2}$ or $1$. Further we show that almost all perfect graphs are $2$-clique-colourable, improving a result of Bacs'o et al from 2004; they are almost all Hamiltonian; they almost all have connectivity $\kappa (P_n)$ equal to their minimum degree; they are almost all in class one (edge-colourable using $\mathrm{\Delta }$ colours, where $\mathrm{\Delta }$ is the maximum degree); and a sequence of independently and uniformly sampled perfect graphs of increasing size converges almost surely to the graphon $W_P(x, y) = \frac12($\mathbb{1}$[x \le 1/2] + $\mathbb{1}$[y \le 1/2])$.