The first order convergence law fails for random perfect graphs

Tobias Müller, Marc Noy

Research output: Contribution to journalArticleAcademicpeer-review

3 Downloads (Pure)

Abstract

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.

Original languageEnglish
Pages (from-to)717-727
Number of pages11
JournalRandom structures & algorithms
Volume53
Issue number4
DOIs
Publication statusPublished - Dec-2018
Event18th International Conference on Random Structures and Algorithms - Gniezno, Poland
Duration: 7-Aug-201711-Aug-2017

Keywords

  • logical limit laws
  • random perfect graphs

Cite this