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

DOI10.1137/21M1429655MaRDI QIDQ5096587zbMATH OpenOpenAlexWikidataFDO

Authors Margarita Akhmejanova, M. E. Zhukovskii

Publication date 18 August 2022

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

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

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)

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.

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)

Cites work

• scientific article; zbMATH DE number 3005966 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Elements of finite model theory.
• Existential monadic second order logic of undirected graphs: the Le Bars conjecture is false
• On random models of finite power and monadic logic
• Probabilities on finite models
• Random graphs.
• 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

Cited in

(10)

• Zero-one law and definability of linear order
• scientific article; zbMATH DE number 1552348 (Why is no real title available?)
• A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences
• On isomorphism-invariant antistochastic properties of random graphs
• Logical laws for short existential monadic second-order sentences about graphs
• Short monadic second order sentences about sparse random graphs
• 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
• The 0-1 law fails for monadic existential second-order logic on undirected graphs
• Logical limit laws for minor-closed classes of graphs

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)