EMSO(FO$^2$) 0-1 Law Fails for All Dense Random Graphs
From MaRDI portal
Publication:5096587
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
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