Random perfect graphs. Issue 1 (5th March 2018) - McDiarmid, Colin; Yolov, Nikola
Abstract : We investigate the asymptotic structure of a random perfect graph Pn 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 Pn contains any given graph H as an induced subgraph is asymptotically 0 or 1 2 or 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 graphon W P ( x, y ) = 1 2 ( 1 [ x ≤ 1 / 2 ] +   1 [ y ≤ 1 / 2 ] ) .