The first order convergence law fails for random perfect graphs. Issue 4 (29th October 2018)

• Record Type: Journal Article
• Authors: Müller, Tobias; Noy, Marc
• Is Part Of: Random structures & algorithms. Volume 53:Issue 4(2018)
• Page Start: 717
• Page End: 727
• Publication Date: 2018-10-29
• Subjects: logical limit laws -- random perfect graphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20823
• Languages: English
• ISSNs: 1042-9832

Abstract

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 → ∞ .