Monadic second-order properties of very sparse random graphs

DOI10.1016/J.APAL.2017.06.004MaRDI QIDQ2404656zbMATH OpenOpenAlexFDO

Authors M. E. Zhukovskii, L. B. Ostrovskii

Publication date 19 September 2017

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

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

zbMATH Keywords

Ehrenfeucht gamemonadic second-order languagerandom graphzero-one law

Mathematics Subject Classification ID

Model theory of finite structures (03C13) Second- and higher-order model theory (03C85) Random graphs (graph-theoretic aspects) (05C80) Zero-one laws (60F20)

Abstract: We study asymptotical probabilities of first order and monadic second order properties of Erdos-Renyi random graph G(n,n^{-a}). The random graph obeys FO (MSO) zero-one k-law if for any first order (monadic second order) formulae it is true for G(n,n^{-a}) with probability tending to 0 or to 1. Zero-one k-laws are well studied only for the first order language and a < 1. We obtain new zero-one k-laws (both for first order and monadic second order languages) when a > 1. Proofs of these results are based on the existed study of first order equivalence classes and our study of monadic second order equivalence classes. The respective results are of interest by themselves.

Review text

This article extends results about zero-one laws, in particular zero-one restricted to quantifier rank \(k\), for graphs to very sparse graphs and to monadic second-order logic (MSO). The main results give almost complete information about when such zero-one laws hold and when they do not. The Ehrenfeucht game is a major tool in the proofs. In order to prove the main results, the authors establish bounds on the number of equivalence classes of the relation ``the graphs \(G\) and \(H\) satisfy the same MSO-sentences of quantifier rank at most \(k\).

Recommendations

• First-order and monadic properties of highly sparse random graphs
• Short monadic second order sentences about sparse random graphs
• Zero-One Laws for Sparse Random Graphs
• Spectra of short monadic sentences about sparse random graphs
• First-order properties of bounded quantifier depth of very sparse random graphs

Cites work

• A logical approach to asymptotic combinatorics. II: Monadic second-order properties
• An application of games to the completeness problem for formalized theories
• Extension of the zero-one \(k\)-law
• 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 515748 (Why is no real title available?)
• scientific article; zbMATH DE number 1072414 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Paths in graphs
• Random Graphs
• Random graphs: models and asymptotic characteristics
• Succinct definitions in the first order theory of graphs
• The largest critical point in the zero-one k-law
• The strange logic of random graphs
• Threshold functions for small subgraphs
• Upper and lower bounds for first order expressibility
• Zero-one \(k\)-law
• Zero-One Laws for Sparse Random Graphs

Cited in

(18)

• Existential monadic second order convergence law fails on sparse random graphs
• On the 4-spectrum of first-order properties of random graphs
• MSO 0-1 law for recursive random trees
• The size of a maximum subgraph of the random graph with a given number of edges
• Spectra of short monadic sentences about sparse random graphs
• Zero-One Laws for Sparse Random Graphs
• Infinitary logics and very sparse random graphs
• Short monadic second order sentences about sparse random graphs
• MONOTONE INDEPENDENCE, COMB GRAPHS AND BOSE–EINSTEIN CONDENSATION
• Logical laws for short existential monadic second-order sentences about graphs
• First-order and monadic properties of highly sparse random graphs
• The Second-Moment Phenomenon for Monochromatic Subgraphs
• Probabilities of first-order sentences on sparse random relational structures: An application to definability on random CNF formulas
• Spectrum of FO logic with quantifier depth 4 is finite
• Combinatorial games on Galton-Watson trees involving several-generation-jump moves
• Maximum induced trees in sparse random graphs
• First order complexity of finite random structures
• On the validity of 0-1 law for shallow first order properties of very sparse random graphs

This page was built for publication: Monadic second-order properties of very sparse random graphs

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