Bounded quantifier depth spectra for random graphs

DOI10.1016/J.DISC.2016.01.005zbMATH Open1333.05189OpenAlexW2278358334MaRDI QIDQ267173FDOQ267173

Authors: M. E. Zhukovskii, Joel 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

Recommendations

• First-order properties of bounded quantifier depth of very sparse random graphs
• On the 4-spectrum of first-order properties of random graphs
• Zero-one laws for existential first-order sentences of bounded quantifier depth
• Spectra of short monadic sentences about sparse random graphs
• First order sentences about random graphs: small number of alternations

zbMATH Keywords

first-order logicrandom graphsspectrazero-one laws

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Probabilities on finite models
• The strange logic of random graphs
• Threshold functions for extension statements
• On the zero-one 4-law for the Erdős-Rényi random graphs
• Counting extensions
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• When does the zero-one \(k\)-law fail?
• On the zero-one \(k\)-law extensions
• Title not available (Why is that?)
• Zero-One Laws for Sparse Random Graphs
• Threshold functions for small subgraphs
• Extension of the zero-one \(k\)-law
• Zero-one \(k\)-law
• Title not available (Why is that?)
• Title not available (Why is that?)
• Paths in graphs
• Random graphs: models and asymptotic characteristics
• The largest critical point in the 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

Cited In (12)

• EMSO(FO$^2$) 0-1 Law Fails for All Dense Random Graphs
• The complexity of random ordered structures
• Zero-one laws for existential first-order sentences of bounded quantifier depth
• Bounded quantifier depth spectrum for random uniform hypergraphs
• Theory of Cryptography
• Zero-one laws for sentences with \(k\) variables
• Threshold spectra via the Ehrenfeucht game
• Limit points of spectra for first-order properties of random hypergraphs
• On the convergence of probabilities of the random graph properties expressed by first-order formulae with a bounded quantifier depth
• First-order properties of bounded quantifier depth of very sparse random graphs
• How complex are random graphs in first order logic?
• Spectrum of FO logic with quantifier depth 4 is finite

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

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