Zero-one laws for first-order formulas with a bounded quantifier depth

DOI10.1134/S1064562411010054zbMath1238.03034OpenAlexW2095258643MaRDI QIDQ656220

M. E. Zhukovskii

Publication date: 17 January 2012

Published in: Doklady Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1064562411010054

zbMATH Keywords

asymptotic behavior of probabilities of properties of random graphs

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Zero-one laws (60F20) Model theory of finite structures (03C13)

Related Items

On limit points of spectra of the random graph first-order properties, Bounded quantifier depth spectra for random graphs, When does the zero-one \(k\)-law fail?, Universal zero-one \(k\)-law, On the zero-one \(k\)-law extensions, On the spectra of first-order language properties for random graphs, First-order properties of bounded quantifier depth of very sparse random graphs, First-order and monadic properties of highly sparse random graphs, On the zero-one 4-law for the Erdős-Rényi random graphs

Cites Work

• The weak zero-one laws for the random distance graphs
• On winning Ehrenfeucht games and monadic NP
• Counting extensions
• Unnamed Item
• Unnamed Item