Existential monadic second order logic of undirected graphs: the Le Bars conjecture is false

DOI10.1016/j.apal.2018.12.001zbMath1477.03157arXiv1807.01794OpenAlexW2903902999WikidataQ122899678 ScholiaQ122899678MaRDI QIDQ1715478

Erdal Karapınar

Publication date: 4 February 2019

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

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

zbMATH Keywords

zero-one lawbinomial random graphexistential monadic second-order logicLe Bars conjecture

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Model theory of finite structures (03C13) Second- and higher-order model theory (03C85)

Related Items (3)

Limit points of spectra for first-order properties of random hypergraphs ⋮ EMSO(FO$^2$) 0-1 Law Fails for All Dense Random Graphs ⋮ Bounded quantifier depth spectrum for random uniform hypergraphs

Cites Work

• 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
• Logical laws for existential monadic second-order sentences with infinite first-order parts
• Probabilities on finite models
• Random graphs: models and asymptotic characteristics
• The strange logic of random graphs

This page was built for publication: Existential monadic second order logic of undirected graphs: the Le Bars conjecture is false