Limiting probabilities of first order properties of random sparse graphs and hypergraphs. Issue 3 (18th August 2021)

• Record Type: Journal Article
• Authors: Larrauri, Alberto; Müller, Tobias; Noy, Marc
• Is Part Of: Random structures & algorithms. Volume 60:Issue 3(2022)
• Page Start: 506
• Page End: 526
• Publication Date: 2021-08-18
• Subjects: first order logic -- logical limit laws -- sparse random graphs and hypergraphs; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.21041
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: Let G n be the binomial random graph G ( n, p = c / n ) in the sparse regime, which as is well‐known undergoes a phase transition at c = 1 . Lynch ( R a n d o m S t r u c t u r e s a n d A l g o r i t h m s, 1992) showed that for every first order sentence ϕ, the limiting probability that G n satisfies ϕ as n → ∞ exists, and moreover it is an analytic function of c . In this paper we consider the closure L c ‾ in the interval [ 0, 1 ] of the set L c of all limiting probabilities of first order sentences in G n . We show that there exists a critical value c 0 ≈ 0 . 93 such that L c ‾ = [ 0, 1 ] when c ≥ c 0, whereas L c ‾ misses at least one subinterval when c < c 0 . We extend these results to random sparse d ‐uniform hypergraphs, where the probability of a d ‐edge is p = c / n d − 1 .