Premium
Limiting probabilities of first order properties of random sparse graphs and hypergraphs
Author(s) -
Larrauri Alberto,
Müller Tobias,
Noy Marc
Publication year - 2022
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.21041
Subject(s) - mathematics , limiting , random graph , combinatorics , closure (psychology) , hypergraph , interval (graph theory) , order (exchange) , binomial (polynomial) , discrete mathematics , graph , statistics , mechanical engineering , finance , economics , engineering , market economy
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.