First-order properties of bounded quantifier depth of very sparse random graphs

DOI10.1070/IM8557zbMath1406.03050OpenAlexW2779154920MaRDI QIDQ4605739

L. B. Ostrovskii, M. E. Zhukovskii

Publication date: 27 February 2018

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

Full work available at URL: https://doi.org/10.1070/im8557

zbMATH Keywords

zero-one lawfirst-order propertiesEhrenfeucht gameErdős-Renyi random graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Classical first-order logic (03B10) Zero-one laws (60F20) Model theory of finite structures (03C13) Basic properties of first-order languages and structures (03C07)

Related Items

Disproof of the zero-one law for existential monadic properties of a sparse binomial random graph ⋮ A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences ⋮ Zero-one laws for \(k\)-variable first-order logic of sparse random graphs ⋮ Zero-one laws for sentences with \(k\) variables

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• When does the zero-one \(k\)-law fail?
• Universal zero-one \(k\)-law
• Zero-one \(k\)-law
• Zero-one laws for first-order formulas with a bounded quantifier depth
• Threshold functions for extension statements
• On the zero-one 4-law for the Erdős-Rényi random graphs
• Succinct definitions in the first order theory of graphs
• An application of games to the completeness problem for formalized theories
• Zero-One Laws for Sparse Random Graphs
• Threshold functions for small subgraphs
• Random graphs: models and asymptotic characteristics
• The largest critical point in the zero-one k-law
• The strange logic of random graphs