Short Monadic Second Order Sentences about Sparse Random Graphs

DOI10.1137/16M1103105zbMath1401.05270arXiv1611.07260OpenAlexW2963148710WikidataQ128722842 ScholiaQ128722842MaRDI QIDQ4562315

M. E. Zhukovskii, Andrey B. Kupavskii

Publication date: 19 December 2018

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

random graphszero-one lawsmonadic properties

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Games on graphs (graph-theoretic aspects) (05C57)

Cites Work

• Zero-one \(k\)-law
• Elements of finite model theory.
• Infinite spectra in the first order theory of graphs
• Logical limit laws for minor-closed classes of graphs
• Threshold functions for extension statements
• Monadic second-order properties of very sparse random graphs
• On infinite spectra of first-order properties of random graphs
• An application of games to the completeness problem for formalized theories
• Zero-One Laws for Sparse Random Graphs
• Threshold functions for small subgraphs
• Estimation of the number of maximal extensions in a random graph
• Random graphs: models and asymptotic characteristics
• The descriptive complexity of subgraph isomorphism without numerics
• The strange logic of random graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item