Bounded quantifier depth spectra for random graphs

DOI10.1016/j.disc.2016.01.005zbMath1333.05189OpenAlexW2278358334MaRDI QIDQ267173

M. E. Zhukovskii, J. H. Spencer

Publication date: 8 April 2016

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

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

zbMATH Keywords

first-order logicrandom graphszero-one lawsspectra

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Games involving graphs (91A43) Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Games on graphs (graph-theoretic aspects) (05C57)

Related Items (3)

Limit points of spectra for first-order properties of random hypergraphs ⋮ Bounded quantifier depth spectrum for random uniform hypergraphs ⋮ Zero-one laws for sentences with \(k\) variables

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• When does the zero-one \(k\)-law fail?
• On the zero-one \(k\)-law extensions
• Extension of the zero-one \(k\)-law
• Zero-one \(k\)-law
• Zero-one laws for first-order formulas with a bounded quantifier depth
• Threshold spectra via the Ehrenfeucht game
• Infinite spectra in the first order theory of graphs
• Threshold functions for extension statements
• On the zero-one 4-law for the Erdős-Rényi random graphs
• Counting extensions
• Zero-One Laws for Sparse Random Graphs
• Threshold functions for small subgraphs
• Probabilities on finite models
• Paths in graphs
• Random graphs: models and asymptotic characteristics
• The largest critical point in the zero-one k-law
• The strange logic of random graphs

This page was built for publication: Bounded quantifier depth spectra for random graphs