Monadic second-order properties of very sparse random graphs
From MaRDI portal
Publication:2404656
DOI10.1016/J.APAL.2017.06.004zbMATH Open1377.03022arXiv1609.01102OpenAlexW2963657400MaRDI QIDQ2404656FDOQ2404656
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)
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.
Full work available at URL: https://arxiv.org/abs/1609.01102
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
Random graphs (graph-theoretic aspects) (05C80) Model theory of finite structures (03C13) Zero-one laws (60F20) Second- and higher-order model theory (03C85)
Cites Work
- Random Graphs
- Title not available (Why is that?)
- Title not available (Why is that?)
- The strange logic of random graphs
- Zero-One Laws for Sparse Random Graphs
- Threshold functions for small subgraphs
- Extension of the zero-one \(k\)-law
- Zero-one \(k\)-law
- Title not available (Why is that?)
- Paths in graphs
- Random graphs: models and asymptotic characteristics
- The largest critical point in the zero-one k-law
- An application of games to the completeness problem for formalized theories
- Title not available (Why is that?)
- Succinct definitions in the first order theory of graphs
- A logical approach to asymptotic combinatorics. II: Monadic second-order properties
- Upper and lower bounds for first order expressibility
- Title not available (Why is that?)
Cited In (14)
- Spectra of short monadic sentences about sparse random graphs
- Maximum induced trees in sparse random graphs
- MSO 0-1 law for recursive random trees
- Existential monadic second order convergence law fails on sparse random graphs
- MONOTONE INDEPENDENCE, COMB GRAPHS AND BOSE–EINSTEIN CONDENSATION
- On the 4-spectrum of first-order properties of random graphs
- Short monadic second order sentences about sparse random graphs
- Logical laws for short existential monadic second-order sentences about graphs
- Spectrum of FO logic with quantifier depth 4 is finite
- Zero-One Laws for Sparse Random Graphs
- The Second-Moment Phenomenon for Monochromatic Subgraphs
- The size of a maximum subgraph of the random graph with a given number of edges
- First-order and monadic properties of highly sparse random graphs
- Combinatorial games on Galton-Watson trees involving several-generation-jump moves
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)
