Threshold spectra via the Ehrenfeucht game

DOI10.1016/0166-218X(91)90048-2zbMATH Open0722.90095WikidataQ127740781 ScholiaQ127740781MaRDI QIDQ757267FDOQ757267

Joel Spencer

Publication date: 1991

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

zbMATH Keywords

Ehrenfeucht gamethreshold spectrumZero-One Law

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) 2-person games (91A05) Games involving graphs (91A43)

Cites Work

• Probabilities on finite models
• Counting extensions
• Zero-One Laws for Sparse Random Graphs
• Infinite spectra in the first order theory of graphs

Cited In (23)

• The tenacity of zero-one laws
• On limit points of spectra of the random graph first-order properties
• Bounded quantifier depth spectra for random graphs
• Infinitary logics and 0-1 laws
• \(\gamma\)-variable first-order logic of uniform attachment random graphs
• Zero-one laws for sentences with \(k\) variables
• MSO 0-1 law for recursive random trees
• On the spectra of first-order language properties for random graphs
• Strictly balanced uniform hypergraphs and generalizations of zero-one law
• Zero-one laws for random \(k\)-partite graphs
• \( \gamma \)-variable first-order logic of preferential attachment random graphs
• On the 4-spectrum of first-order properties of random graphs
• A game for linear-time-branching-time spectroscopy
• Logical laws for short existential monadic second-order sentences about graphs
• Random graph orders do not satisfy a 0–1 law
• A zero‐one law for a random subset
• Spectrum of FO logic with quantifier depth 4 is finite
• Zero-one laws with variable probability
• First order sentences about random graphs: small number of alternations
• Zero-one laws for \(k\)-variable first-order logic of sparse random graphs
• Probabilities of Sentences about Very Sparse Random Graphs
• Logical laws for existential monadic second-order sentences with infinite first-order parts
• Combinatorial games on Galton-Watson trees involving several-generation-jump moves

   Recommendations

• First-order properties of bounded quantifier depth of very sparse random graphs 👍 👎
• Ups and downs of first order sentences on random graphs 👍 👎
• A zero‐one law for a random subset 👍 👎
• Bounded quantifier depth spectra for random graphs 👍 👎
• On infinite spectra of first-order properties of random graphs 👍 👎

This page was built for publication: Threshold spectra via the Ehrenfeucht game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q757267)