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

DOI10.1142/S0219061320500075MaRDI QIDQ5118048zbMATH OpenOpenAlexWikidataFDO

Authors M. E. Zhukovskii

Publication date 4 September 2020

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

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)

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.

Recommendations

• Existential monadic second order logic of undirected graphs: the Le Bars conjecture is false
• Monadic second-order properties of very sparse random graphs
• EMSO(FO$^2$) 0-1 Law Fails for All Dense Random Graphs
• Logical laws for existential monadic second-order sentences with infinite first-order parts
• A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• A logical approach to asymptotic combinatorics. II: Monadic second-order properties
• Almost sure theories
• Elements of finite model theory.
• 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
• On random models of finite power and monadic logic
• Probabilities on finite models
• Random graphs.
• Random graphs: models and asymptotic characteristics
• The 0-1 law fails for monadic existential second-order logic on undirected graphs
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The strange logic of random graphs
• Threshold spectra via the Ehrenfeucht game

Cited in

(9)

• A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences
• Combinatorial games on Galton-Watson trees involving several-generation-jump moves
• Bounded quantifier depth spectrum for random uniform hypergraphs
• Existential monadic second order logic of undirected graphs: the Le Bars conjecture is false
• On zero-one and convergence laws for graphs embeddable on a fixed surface
• Logical laws for existential monadic second-order sentences with infinite first-order parts
• MSO 0-1 law for recursive random trees
• The 0-1 law fails for monadic existential second-order logic on undirected graphs
• Limit points of spectra for first-order properties of random hypergraphs

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)