Zero-One Laws for Sparse Random Graphs
From MaRDI portal
Publication:3791190
DOI10.2307/1990968zbMath0647.05051OpenAlexW4206755919MaRDI QIDQ3791190
Publication date: 1988
Full work available at URL: https://doi.org/10.2307/1990968
Random graphs (graph-theoretic aspects) (05C80) Graph theory (including graph drawing) in computer science (68R10) Zero-one laws (60F20) Quantifier elimination, model completeness, and related topics (03C10)
Related Items (71)
Spectra of short monadic sentences about sparse random graphs ⋮ 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 ⋮ Continuous phase transitions on Galton–Watson trees ⋮ Expansions of geometries ⋮ \( \gamma \)-variable first-order logic of preferential attachment random graphs ⋮ Quasi-Random Set Systems ⋮ A zero‐one law for a random subset ⋮ Undecidable statements and random graphs ⋮ When does the zero-one \(k\)-law fail? ⋮ Universal zero-one \(k\)-law ⋮ Probabilities of Sentences about Very Sparse Random Graphs ⋮ Counting extensions ⋮ 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 ⋮ Stable generic structures ⋮ Spectra of first-order formulas with a low quantifier depth and a small number of quantifier alternations ⋮ Convergence in homogeneous random graphs ⋮ The Ehrenfeucht-Fraïssé Method and the Planted Clique Conjecture ⋮ Evolving Shelah‐Spencer graphs ⋮ On the spectra of first-order language properties for random graphs ⋮ Extension of the zero-one \(k\)-law ⋮ Counting extensions revisited ⋮ Quantifier alternation in first-order formulas with infinite spectra ⋮ The first order theory of \(G(n, c/n)\) ⋮ Asymptotic elimination of partially continuous aggregation functions in directed graphical models ⋮ Disproof of the zero-one law for existential monadic properties of a sparse binomial random graph ⋮ First order sentences about random graphs: small number of alternations ⋮ Bounded quantifier depth spectrum for random uniform hypergraphs ⋮ Zero-one \(k\)-law ⋮ First-order properties of bounded quantifier depth of very sparse random graphs ⋮ The metamathematics of random graphs ⋮ First-order zero-one law for the uniform model of the random graph ⋮ On limit points of spectra of first-order sentences with quantifier depth 4 ⋮ Conditional probability logic, lifted Bayesian networks, and almost sure quantifier elimination ⋮ Ab initio generic structures which are superstable but not \(\omega \)-stable ⋮ Keisler's order is not simple (and simple theories may not be either) ⋮ The theories of Baldwin-Shi hypergraphs and their atomic models ⋮ Universal elements and the complexity of certain classes of infinite graphs ⋮ Logical limit laws for minor-closed classes of graphs ⋮ Infinitary logics and 0-1 laws ⋮ First-order and monadic properties of highly sparse random graphs ⋮ MSO 0-1 law for recursive random trees ⋮ Finite-model theory -- A personal perspective ⋮ The complexity of random ordered structures ⋮ Zero-one laws for random distance graphs with vertices in \(\{0,1\}^n\) ⋮ A simpler axiomatization of the Shelah-Spencer almost sure theories ⋮ Modular statistics for subgraph counts in sparse random graphs ⋮ Zero-one law for random distance graphs with vertices in \(\{-1,0,1\}^n\) ⋮ Existential monadic second order convergence law fails on sparse random graphs ⋮ Query evaluation on a database given by a random graph ⋮ Determined theories and limit laws ⋮ Vapnik-Chervonenkis density in some theories without the independence property, I ⋮ The first order convergence law fails for random perfect graphs ⋮ Random graph orders do not satisfy a 0–1 law ⋮ Zero-one laws for \(k\)-variable first-order logic of sparse random graphs ⋮ Threshold spectra via the Ehrenfeucht game ⋮ Infinite spectra of first-order properties for random hypergraphs ⋮ On a sequence of random distance graphs subject to the zero-one law ⋮ Zero-one laws for random \(k\)-partite graphs ⋮ In the random graph \(G(n,p), p=n^{-a}\): If \(\psi\) has probability \(O(n^{-\varepsilon})\) for every \(\varepsilon >0\) then it has probability \(O(e^{-n^ \varepsilon})\) for some \(\varepsilon >0\) ⋮ Zero-one laws for sentences with \(k\) variables ⋮ Randomness and semigenericity ⋮ Infinite spectra in the first order theory of graphs ⋮ Zero-one laws for random graphs with vertices in a Boolean cube ⋮ \(\gamma\)-variable first-order logic of uniform attachment random graphs ⋮ 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
- On random models of finite power and monadic logic
- Threshold functions
- Minimal models of theories of one function symbol
- Intersection Theorems for Systems of Sets
- Probabilities on finite models
- A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the sum of Observations
This page was built for publication: Zero-One Laws for Sparse Random Graphs
