Short monadic second order sentences about sparse random graphs

DOI10.1137/16M1103105MaRDI QIDQ4562315zbMATH OpenOpenAlexWikidataFDO

Authors M. E. Zhukovskii, Andrey B. Kupavskii

Publication date 19 December 2018

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

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

zbMATH Keywords

random graphszero-one lawsmonadic properties

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Games on graphs (graph-theoretic aspects) (05C57)

Abstract: In this paper, we study zero-one laws for the ErdH{o}s--R'{e}nyi random graph model $G(n,p)$ in the case when $p=n^{-alpha}$ for $alpha>0$. For a given class $mathcalK$ of logical sentences about graphs and a given function $p=p(n)$, we say that $G(n,p)$ obeys the zero-one law (w.r.t. the class $mathcalK$) if each sentence $varphiinmathcalK$ either a.a.s. true or a.a.s. false for $G(n,p)$. In this paper, we consider first order properties and monadic second order properties of bounded extit{quantifier depth} $k$, that is, the length of the longest chain of nested quantifiers in the formula expressing the property. Zero-one laws for properties of quantifier depth $k$ we call the extit{zero-one $k$-laws}. The main results of this paper concern the zero-one $k$-laws for monadic second order properties (MSO properties). We determine all values $alpha>0$, for which the zero-one $3$-law for MSO properties does not hold. We also show that, in contrast to the case of the $3$-law, there are infinitely many values of $alpha$ for which the zero-one $4$-law for MSO properties does not hold. To this end, we analyze the evolution of certain properties of $G(n,p)$ that may be of independent interest.

Recommendations

• Monadic second-order properties of very sparse random graphs
• Spectra of short monadic sentences about sparse random graphs
• First-order and monadic properties of highly sparse random graphs
• Zero-one laws for first-order formulas with a bounded quantifier depth
• EMSO(FO^2) 0-1 Law Fails for All Dense Random Graphs

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 3769673 (Why is no real title available?)
• scientific article; zbMATH DE number 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 515748 (Why is no real title available?)
• scientific article; zbMATH DE number 568785 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• An application of games to the completeness problem for formalized theories
• Elements of finite model theory.
• Estimation of the number of maximal extensions in a random graph
• Infinite spectra in the first order theory of graphs
• Logical limit laws for minor-closed classes of graphs
• Monadic second-order properties of very sparse random graphs
• On infinite spectra of first-order properties of random graphs
• Random graphs.
• Random graphs: models and asymptotic characteristics
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The strange logic of random graphs
• Threshold functions for extension statements
• Threshold functions for small subgraphs
• Zero-One Laws for Sparse Random Graphs
• Zero-one \(k\)-law

Cited in

(7)

• EMSO(FO^2) 0-1 Law Fails for All Dense Random Graphs
• Spectra of short monadic sentences about sparse random graphs
• Logical limit laws for minor-closed classes of graphs
• Monadic second-order properties of very sparse random graphs
• First-order and monadic properties of highly sparse random graphs
• Probabilities of Sentences about Very Sparse Random Graphs
• Combinatorial games on Galton-Watson trees involving several-generation-jump moves

This page was built for publication: Short monadic second order sentences about sparse random graphs

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