Publication

The first order convergence law fails for random perfect graphs

Müller, T. & Noy, M., Dec-2018, In : Random structures & algorithms. 53, 4, p. 717-727 11 p.

Research output: Contribution to journalArticleAcademicpeer-review

Copy link to clipboard

Documents

  • The first order convergence law fails for random perfect graphs

    Final publisher's version, 267 KB, PDF document

    Request copy

DOI

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
Publication statusPublished - Dec-2018
Event18th International Conference on Random Structures and Algorithms - Gniezno, Poland
Duration: 7-Aug-201711-Aug-2017

Event

18th International Conference on Random Structures and Algorithms

07/08/201711/08/2017

Gniezno, Poland

Event: Conference

    Keywords

  • logical limit laws, random perfect graphs

View graph of relations

ID: 76340969