Monadic second-order properties of very sparse random graphs
From MaRDI portal
Publication:2404656
DOI10.1016/j.apal.2017.06.004zbMath1377.03022arXiv1609.01102OpenAlexW2963657400MaRDI QIDQ2404656
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
Random graphs (graph-theoretic aspects) (05C80) Zero-one laws (60F20) Model theory of finite structures (03C13) Second- and higher-order model theory (03C85)
Related Items (6)
Short Monadic Second Order Sentences about Sparse Random Graphs ⋮ Logical laws for short existential monadic second-order sentences about graphs ⋮ MSO 0-1 law for recursive random trees ⋮ Existential monadic second order convergence law fails on sparse random graphs ⋮ The size of a maximum subgraph of the random graph with a given number of edges ⋮ On the 4-spectrum of first-order properties of random graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Extension of the zero-one \(k\)-law
- Zero-one \(k\)-law
- Upper and lower bounds for first order expressibility
- Succinct definitions in the first order theory of graphs
- A logical approach to asymptotic combinatorics. II: Monadic second-order properties
- An application of games to the completeness problem for formalized theories
- Zero-One Laws for Sparse Random Graphs
- Threshold functions for small subgraphs
- Paths in graphs
- Random graphs: models and asymptotic characteristics
- The largest critical point in the zero-one k-law
- Random Graphs
- The strange logic of random graphs
This page was built for publication: Monadic second-order properties of very sparse random graphs