Zero-one \(k\)-law

DOI10.1016/j.disc.2012.01.018zbMath1238.03035MaRDI QIDQ418871

M. E. Zhukovskii

Publication date: 30 May 2012

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

Full work available at URL: https://doi.org/10.1016/j.disc.2012.01.018

zbMATH Keywords

extension; random graph; zero-one law; Ehrenfeucht game

Mathematics Subject Classification ID

05C80: Random graphs (graph-theoretic aspects)

60F20: Zero-one laws

03C13: Model theory of finite structures

Related Items

Short Monadic Second Order Sentences about Sparse Random Graphs, First-order properties of bounded quantifier depth of very sparse random graphs, The descriptive complexity of subgraph isomorphism without numerics, On limit points of spectra of the random graph first-order properties, Bounded quantifier depth spectra for random graphs, When does the zero-one \(k\)-law fail?, Universal zero-one \(k\)-law, On the zero-one \(k\)-law extensions, Extension of the zero-one \(k\)-law, First-order and monadic properties of highly sparse random graphs, On first-order definitions of subgraph isomorphism properties, On the spectra of first-order language properties for random graphs, First order sentences about random graphs: small number of alternations, Logical laws for existential monadic second-order sentences with infinite first-order parts, Quantifier alternation in first-order formulas with infinite spectra, Zero-one laws for \(k\)-variable first-order logic of sparse random graphs, Infinite spectra of first-order properties for random hypergraphs, On the zero-one 4-law for the Erdős-Rényi random graphs, Monadic second-order properties of very sparse random graphs, Spectra of first-order formulas with a low quantifier depth and a small number of quantifier alternations

Cites Work

• The weak zero-one laws for the random distance graphs
• On winning Ehrenfeucht games and monadic NP
• On the probability of the occurrence of a copy of a fixed graph in a random distance graph
• Counting extensions
• A geometric zero-one law
• K l+1 -Free Graphs: Asymptotic Structure and a 0-1 Law
• Zero-One Laws for Sparse Random Graphs
• Probabilities of Sentences about Very Sparse Random Graphs
• Probabilities on finite models
• Paths in graphs
• The strange logic of random graphs
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item