The first order convergence law fails for random perfect graphs

Tobias Müller, Marc Noy

OnderzoeksoutputAcademicpeer review

10 Downloads (Pure)


We consider first order expressible properties of random perfect graphs. That is, we pick a graph G(n) uniformly at random from all (labeled) perfect graphs on n vertices and consider the probability that it satisfies some graph property that can be expressed in the first order language of graphs. We show that there exists such a first order expressible property for which the probability that G(n) satisfies it does not converge as n -> infinity.

Originele taal-2English
Pagina's (van-tot)717-727
Aantal pagina's11
TijdschriftRandom structures & algorithms
Nummer van het tijdschrift4
StatusPublished - dec-2018
Evenement18th International Conference on Random Structures and Algorithms - Gniezno, Poland
Duur: 7-aug-201711-aug-2017

Citeer dit