Random perfect graphs

We investigate the asymptotic structure of a random perfect graph P n sampled uniformly from the set of perfect graphs on vertex set { 1 , … , n } . Our approach is based on the result of Prömel 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 α ( P n ) and clique number ω ( 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 or1 2or 1. Further we show that almost all perfect graphs are 2‐clique‐colorable, improving a result of Bacsó et al. from 2004; they are almost all Hamiltonian; they almost all have connectivity κ ( P n ) equal to their minimum degree; they are almost all in class one (edge‐colorable using Δ colors, where Δ is the maximum degree); and a sequence of independently and uniformly sampled perfect graphs of increasing size converges almost surely to the graphonW P ( x , y ) = 1 2 ( 1 [ x ≤ 1 / 2 ] +   1 [ y ≤ 1 / 2 ] ) .