A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences

DOI10.1134/S1064562418070311zbMath1484.03072OpenAlexW2909770914WikidataQ114847316 ScholiaQ114847316MaRDI QIDQ1732077

Xianqiang Yang

Publication date: 15 March 2019

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

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

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Zero-one laws (60F20) Model theory of finite structures (03C13) Second- and higher-order model theory (03C85)

Cites Work

• Unnamed Item
• Unnamed Item
• When does the zero-one \(k\)-law fail?
• Elements of finite model theory.
• On random models of finite power and monadic logic
• The 0-1 law fails for monadic existential second-order logic on undirected graphs
• First order sentences about random graphs: small number of alternations
• Logical laws for existential monadic second-order sentences with infinite first-order parts
• Probabilities on finite models
• First-order properties of bounded quantifier depth of very sparse random graphs
• Random graphs: models and asymptotic characteristics
• The strange logic of random graphs

This page was built for publication: A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences