EMSO(FO^2) 0-1 Law Fails for All Dense Random Graphs

DOI10.1137/21M1429655zbMATH Open1496.05174arXiv2106.13968OpenAlexW3174673542WikidataQ114847118 ScholiaQ114847118MaRDI QIDQ5096587FDOQ5096587

Authors: Margarita Akhmejanova, M. E. Zhukovskii 

Publication date: 18 August 2022

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: In this paper, we disprove EMSO(FO${}^2$) convergence law for the binomial random graph $G(n,p)$ for any constant probability $p$. More specifically, we prove that there exists an existential monadic second order sentence with 2 first order variables such that, for every $pin(0,1)$, the probability that it is true on $G(n,p)$ does not converge.

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

Recommendations

• Zero-one laws for \(k\)-variable first-order logic of sparse random graphs
• A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences
• Zero-one laws for sentences with \(k\) variables
• When Does the Zero-One Law Hold?
• Bounded quantifier depth spectra for random graphs
• Zero-one laws for graphs with edge probabilities decaying with distance. Part I
• Ups and downs of first order sentences on random graphs
• Spectra of short monadic sentences about sparse random graphs
• Short monadic second order sentences about sparse random graphs
• Failure of 0-1 law for sparse random graph in strong logics (Sh1062)

zbMATH Keywords

random graphs0-1 lawsconvergence lawsexistential monadic second order logic

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Density (toughness, etc.) (05C42) Classical first-order logic (03B10) Second- and higher-order model theory (03C85)

Cites Work

• 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.
• Elements of finite model theory.
• Title not available (Why is that?)
• 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

Cited In (10)

• Zero-one law and definability of linear order
• The 0-1 law fails for monadic existential second-order logic on undirected graphs
• A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences
• Logical limit laws for minor-closed classes of graphs
• Short monadic second order sentences about sparse random graphs
• Logical laws for short existential monadic second-order sentences about graphs
• On isomorphism-invariant antistochastic properties of random graphs
• On zero-one and convergence laws for graphs embeddable on a fixed surface
• Title not available (Why is that?)
• Existential monadic second order logic of undirected graphs: the Le Bars conjecture is false

This page was built for publication: EMSO(FO$^2$) 0-1 Law Fails for All Dense Random Graphs

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