Limiting probabilities of first order properties of random sparse graphs and hypergraphs

LetG nbe 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 thatG nsatisfies ϕ as n → ∞ exists, and moreover it is an analytic function of c . In this paper we consider the closureL c‾in the interval [ 0 , 1 ] of the setL cof all limiting probabilities of first order sentences inG n. We show that there exists a critical valuec 0 ≈ 0 . 93 such thatL c‾ = [ 0 , 1 ] when c ≥ c 0, whereasL 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.