EMSO(FO$^2$) 0-1 Law Fails for All Dense Random Graphs

DOI10.1137/21M1429655zbMath1496.05174arXiv2106.13968OpenAlexW3174673542WikidataQ114847118 ScholiaQ114847118MaRDI QIDQ5096587

M. E. Zhukovskii, Margarita Akhmejanova

Publication date: 18 August 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2106.13968

zbMATH Keywords

random graphs0-1 lawsconvergence lawsexistential monadic second order logic

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Classical first-order logic (03B10) Second- and higher-order model theory (03C85) Density (toughness, etc.) (05C42)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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
• Existential monadic second order logic of undirected graphs: the Le Bars conjecture is false
• Probabilities on finite models
• The strange logic of random graphs