Random perfect graphs. Issue 1 (5th March 2018)

• Record Type: Journal Article
• Authors: McDiarmid, Colin; Yolov, Nikola
• Is Part Of: Random structures & algorithms. Volume 54:Issue 1(2019)
• Page Start: 148
• Page End: 186
• Publication Date: 2018-03-05
• Subjects: Clique‐coloring -- edge‐coloring -- graph limits -- Hamiltonian -- perfect graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20770
• Languages: English
• ISSNs: 1042-9832

Abstract

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 ] ) .