Existential monadic second order convergence law fails on sparse random graphs

DOI10.1016/j.ejc.2019.103017zbMath1428.05281arXiv1808.03970OpenAlexW2973069220WikidataQ127284202 ScholiaQ127284202MaRDI QIDQ2011137

Alena Egorova, M. E. Zhukovskii

Publication date: 28 November 2019

Published in: European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

binomial random graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Density (toughness, etc.) (05C42)

Related Items

Limit points of spectra for first-order properties of random hypergraphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Elements of finite model theory.
• On the independence number of random graphs
• On random models of finite power and monadic logic
• The 0-1 law fails for monadic existential second-order logic on undirected graphs
• Logical laws for existential monadic second-order sentences with infinite first-order parts
• Monadic second-order properties of very sparse random graphs
• Counting extensions
• Zero-One Laws for Sparse Random Graphs
• Probabilities of Sentences about Very Sparse Random Graphs
• Probabilities on finite models
• Paths in graphs
• Random graphs: models and asymptotic characteristics