Logical laws for short existential monadic second-order sentences about graphs

DOI10.1142/S0219061320500075zbMATH Open1485.03084arXiv1712.06168OpenAlexW2976815386WikidataQ114847092 ScholiaQ114847092MaRDI QIDQ5118048FDOQ5118048

M. E. Zhukovskii

Publication date: 4 September 2020

Published in: Journal of Mathematical Logic (Search for Journal in Brave)

Abstract: In this paper, we study existential monadic second order (EMSO) properties of undirected graphs. In 2001, J.-M. Le Bars proved that there exists an EMSO sentence about undirected graphs such that the probability that it is true does not converge (here, the probability distribution is uniform over the set of all graphs on the fixed set of vertices). In the same paper, he conjectured that, for EMSO sentences with 2 first order variables, the 0-1 law holds (every sentence is either true asymptotically almost surely (a.a.s.), or false a.a.s.). We give an example of EMSO sentence with 1 monadic variable without convergence and an example of EMSO sentence with 3 first order variables without convergence.

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

zbMATH Keywords

random graphszero-one lawsconvergence lawsexistential monadic second-order language

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Probabilities on finite models
• The strange logic of random graphs
• Random graphs.
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Random graphs: models and asymptotic characteristics
• Elements of finite model theory.
• Threshold spectra via the Ehrenfeucht game
• Title not available (Why is that?)
• A logical approach to asymptotic combinatorics. II: Monadic second-order properties
• Almost sure theories
• 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 limit laws for minor-closed classes of graphs
• Monadic second-order properties of very sparse random graphs

Cited In (6)

• The 0-1 law fails for monadic existential second-order logic on undirected graphs
• Bounded quantifier depth spectrum for random uniform hypergraphs
• MSO 0-1 law for recursive random trees
• Limit points of spectra for first-order properties of random hypergraphs
• Logical laws for existential monadic second-order sentences with infinite first-order parts
• Combinatorial games on Galton-Watson trees involving several-generation-jump moves

This page was built for publication: Logical laws for short existential monadic second-order sentences about graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5118048)