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

random graphzero-one lawEhrenfeucht gamemonadic second-order language

Mathematics Subject Classification ID

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

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.

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

• 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?)
• 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
• 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 Laws for Sparse Random Graphs
• Zero-one \(k\)-law

Cited in

(15)

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