Monadic second-order properties of very sparse random graphs

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

zbMATH Keywords

random graphzero-one lawEhrenfeucht gamemonadic second-order language

Mathematics Subject Classification ID

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