Logical laws for short existential monadic second-order sentences about graphs

DOI10.1142/S0219061320500075zbMath1485.03084arXiv1712.06168OpenAlexW2976815386WikidataQ114847092 ScholiaQ114847092MaRDI QIDQ5118048

M. E. Zhukovskii

Publication date: 4 September 2020

Published in: Journal of Mathematical Logic (Search for Journal in Brave)

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

zbMATH Keywords

random graphszero-one lawsconvergence lawsexistential monadic 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 (3)

Limit points of spectra for first-order properties of random hypergraphs ⋮ Bounded quantifier depth spectrum for random uniform hypergraphs ⋮ MSO 0-1 law for recursive random trees

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Elements of finite model theory.
• Threshold spectra via the Ehrenfeucht game
• On random models of finite power and monadic logic
• The 0-1 law fails for monadic existential second-order logic on undirected graphs
• First order sentences about random graphs: small number of alternations
• Logical limit laws for minor-closed classes of graphs
• Monadic second-order properties of very sparse random graphs
• A logical approach to asymptotic combinatorics. II: Monadic second-order properties
• Almost sure theories
• Probabilities on finite models
• Random graphs: models and asymptotic characteristics
• The strange logic of random graphs

This page was built for publication: Logical laws for short existential monadic second-order sentences about graphs