Existential monadic second order convergence law fails on sparse random graphs

DOI10.1016/J.EJC.2019.103017MaRDI QIDQ2011137zbMATH OpenOpenAlexWikidataFDO

Authors Alena Egorova, M. E. Zhukovskii

Publication date 28 November 2019

Published in European Journal of Combinatorics (Search for Journal in Brave)

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

zbMATH Keywords

binomial random graph

Mathematics Subject Classification ID

Density (toughness, etc.) (05C42) Random graphs (graph-theoretic aspects) (05C80)

Abstract: In the paper, we prove that existential monadic second order convergence law fails for the binomial random graph $G(n,n^{-alpha})$ for every $alphain(0,1)$.

Cites work

• Counting extensions
• Elements of finite model theory.
• scientific article; zbMATH DE number 515748 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• scientific article; zbMATH DE number 2212141 (Why is no real title available?)
• Logical laws for existential monadic second-order sentences with infinite first-order parts
• Monadic second-order properties of very sparse random graphs
• On random models of finite power and monadic logic
• On the independence number of random graphs
• Paths in graphs
• Probabilities of Sentences about Very Sparse Random Graphs
• Probabilities on finite models
• 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.
• Zero-One Laws for Sparse Random Graphs

Cited in

(1)

• Limit points of spectra for first-order properties of random hypergraphs

This page was built for publication: Existential monadic second order convergence law fails on sparse random graphs

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