First-order and monadic properties of highly sparse random graphs

DOI10.1134/S1064562416050240zbMath1357.05140OpenAlexW2549896219MaRDI QIDQ512509

L. B. Ostrovskii, M. E. Zhukovskii

Publication date: 27 February 2017

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

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

zbMATH Keywords

monadic zero-one \(k\)-law

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Zero-one laws (60F20) Model theory of finite structures (03C13) Density (toughness, etc.) (05C42)

Related Items (3)

Spectra of first-order formulas with a low quantifier depth and a small number of quantifier alternations ⋮ Quantifier alternation in first-order formulas with infinite spectra ⋮ First order sentences about random graphs: small number of alternations

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Extension of the zero-one \(k\)-law
• Zero-one \(k\)-law
• Zero-one laws for first-order formulas with a bounded quantifier depth
• On the zero-one 4-law for the Erdős-Rényi random graphs
• Succinct definitions in the first order theory of graphs
• A logical approach to asymptotic combinatorics. II: Monadic second-order properties
• Zero-One Laws for Sparse Random Graphs
• Random graphs: models and asymptotic characteristics
• The largest critical point in the zero-one k-law

This page was built for publication: First-order and monadic properties of highly sparse random graphs