Limiting probabilities of first order properties of random sparse graphs and hypergraphs. Issue 3 (18th August 2021) - Larrauri, Alberto; Müller, Tobias; Noy, Marc
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 .