Disproof of the zero-one law for existential monadic properties of a sparse binomial random graph

DOI10.1134/S1064562419010216zbMath1423.05153OpenAlexW2946696296WikidataQ114847313 ScholiaQ114847313MaRDI QIDQ2424392

M. E. Zhukovskii, Alena Egorova

Publication date: 24 June 2019

Published in: Doklady Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1134/s1064562419010216

zbMATH Keywords

Existential monadic second-order sentences

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Model theory of finite structures (03C13) Density (toughness, etc.) (05C42)

Related Items (3)

Cryptanalysis of the BBCRS System on Reed-Muller Binary Codes ⋮ The median of the number of simple paths on three vertices in the random graph ⋮ The size of a maximum subgraph of the random graph with a given number of edges

Cites Work

• Unnamed Item
• Unnamed Item
• When does the zero-one \(k\)-law fail?
• 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 laws for existential monadic second-order sentences with infinite first-order parts
• Zero-One Laws for Sparse Random Graphs
• First-order properties of bounded quantifier depth of very sparse random graphs
• Random graphs: models and asymptotic characteristics
• The strange logic of random graphs

This page was built for publication: Disproof of the zero-one law for existential monadic properties of a sparse binomial random graph