Bounded quantifier depth spectra for random graphs

DOI10.1016/J.DISC.2016.01.005MaRDI QIDQ267173zbMATH OpenOpenAlexFDO

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

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)

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

Cites work

• scientific article; zbMATH DE number 3168330 (Why is no real title available?)
• scientific article; zbMATH DE number 4041966 (Why is no real title available?)
• scientific article; zbMATH DE number 612169 (Why is no real title available?)
• scientific article; zbMATH DE number 1072414 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Counting extensions
• Extension of the zero-one \(k\)-law
• Infinite spectra in the first order theory of graphs
• On the zero-one 4-law for the Erdős-Rényi random graphs
• On the zero-one k-law extensions
• Paths in graphs
• Probabilities on finite models
• Random graphs: models and asymptotic characteristics
• The largest critical point in the zero-one k-law
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• The strange logic of random graphs
• Threshold functions for extension statements
• Threshold functions for small subgraphs
• Threshold spectra via the Ehrenfeucht game
• When does the zero-one k-law fail?
• Zero-One Laws for Sparse Random Graphs
• Zero-one \(k\)-law
• Zero-one laws for first-order formulas with a bounded quantifier depth

Cited in

(12)

• The complexity of random ordered structures
• EMSO(FO$^2$) 0-1 Law Fails for All Dense Random Graphs
• Zero-one laws for existential first-order sentences of bounded quantifier depth
• Zero-one laws for sentences with \(k\) variables
• Bounded quantifier depth spectrum for random uniform hypergraphs
• Theory of Cryptography
• Threshold spectra via the Ehrenfeucht game
• On the convergence of probabilities of the random graph properties expressed by first-order formulae with a bounded quantifier depth
• Limit points of spectra for first-order properties of random hypergraphs
• 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)