The first order convergence law fails for random perfect graphs

Tobias Müller, Marc Noy

Onderzoeksoutput: ArticleAcademicpeer review

1 Citaat (Scopus)
97 Downloads (Pure)

Samenvatting

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
Volume53
Nummer van het tijdschrift4
DOI's
StatusPublished - dec.-2018
Evenement18th International Conference on Random Structures and Algorithms - Gniezno, Poland
Duur: 7-aug.-201711-aug.-2017

Vingerafdruk

Duik in de onderzoeksthema's van 'The first order convergence law fails for random perfect graphs'. Samen vormen ze een unieke vingerafdruk.

Citeer dit