On the convergence of probabilities of the random graphs' properties expressed by first-order formulae with a bounded quantifier depth

2013/04/03 by Maksim Zhukovskii, Zhukovskii, Maksim
Decision Sciences · Mathematics · #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #Limits and Structures in Graph Theory #Probability and Risk Models #Stochastic processes and statistical mechanics #math.CO

paper · pdf · doi:10.48550/arxiv.1304.0896

arxiv created 2013/04/03 · openalex publication_date 2013/04/03 · arxiv updated 2013/04/04 · openalex created_date 2022/10/02 · openalex updated_date 2026/07/28

Abstract

An asymptotic behavior of the probabilities of first-order properties of Erdos-Renyi random graph G(N,p), lnp=-alnN, is studied in the article. We prove the covergence law for formulae with quantifier depth bounded by k when a=1/(k-2).

Related

• On infinite spectra of first order properties of random graphs
• Bounded quantifier depth spectrum for random uniform hypegraphs
• Spectrum for first-order properties of random hypergraphs
• How Complex are Random Graphs in First Order Logic?
• On the probability that a random subtree is spanning