Zero-one \(k\)-law
From MaRDI portal
Publication:418871
DOI10.1016/j.disc.2012.01.018zbMath1238.03035OpenAlexW86998899MaRDI QIDQ418871
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
Random graphs (graph-theoretic aspects) (05C80) Zero-one laws (60F20) Model theory of finite structures (03C13)
Related Items (25)
On limit points of spectra of the random graph first-order properties ⋮ Bounded quantifier depth spectra for random graphs ⋮ Strictly balanced uniform hypergraphs and generalizations of zero-one law ⋮ When does the zero-one \(k\)-law fail? ⋮ Universal zero-one \(k\)-law ⋮ On the zero-one \(k\)-law extensions ⋮ Short Monadic Second Order Sentences about Sparse Random Graphs ⋮ Limit points of spectra for first-order properties of random hypergraphs ⋮ 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 ⋮ On the spectra of first-order language properties for random graphs ⋮ Extension of the zero-one \(k\)-law ⋮ Quantifier alternation in first-order formulas with infinite spectra ⋮ First order sentences about random graphs: small number of alternations ⋮ Bounded quantifier depth spectrum for random uniform hypergraphs ⋮ First-order properties of bounded quantifier depth of very sparse random graphs ⋮ Logical laws for existential monadic second-order sentences with infinite first-order parts ⋮ On limit points of spectra of first-order sentences with quantifier depth 4 ⋮ On first-order definitions of subgraph isomorphism properties ⋮ First-order and monadic properties of highly sparse random graphs ⋮ The descriptive complexity of subgraph isomorphism without numerics ⋮ 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 ⋮ On the 4-spectrum of first-order properties of random graphs
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- 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
This page was built for publication: Zero-one \(k\)-law
