First order sentences about random graphs: small number of alternations

DOI10.1016/J.DAM.2017.10.017MaRDI QIDQ1693159zbMATH OpenOpenAlexFDO

Authors A. D. Matushkin, M. E. Zhukovskii

Publication date 11 January 2018

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

Full work available at URL https://arxiv.org/abs/1701.06517

zbMATH Keywords

first-order logicrandom graphsspectrum of first order sentenceszero-one laws

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60) Random graphs (graph-theoretic aspects) (05C80)

Abstract: Spectrum of a first order sentence is the set of all $alpha$ such that $G(n,n^{-alpha})$ does not obey zero-one law w.r.t. this sentence. We have proved that the minimal number of quantifier alternations of a first order sentence with an infinite spectrum equals 3. We have also proved that the spectrum of a first order sentence with a quantifier depth 4 has no limit points except possibly the points 1/2 and 3/5.

Recommendations

• Spectra of first-order formulas with a low quantifier depth and a small number of quantifier alternations
• Quantifier alternation in first-order formulas with infinite spectra
• On the spectra of first-order language properties for random graphs
• On the 4-spectrum of first-order properties of random graphs
• On limit points of spectra of first-order sentences with quantifier depth 4

Cites work

• Estimation of the number of maximal extensions in a random graph
• First-order and monadic properties of highly sparse random graphs
• 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 1324669 (Why is no real title available?)
• scientific article; zbMATH DE number 1540669 (Why is no real title available?)
• Infinite spectra in the first order theory of graphs
• On infinite spectra of first-order properties of random graphs
• Random graphs.
• Random graphs: models and asymptotic characteristics
• Succinct definitions in the first order theory of graphs
• 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
• Zero-one \(k\)-law
• Zero-One Laws for Sparse Random Graphs

Cited in

(16)

• Listing graphs that satisfy first-order sentences
• A disproof the Le Bars conjecture about the zero-one law for existential monadic second-order sentences
• On the 4-spectrum of first-order properties of random graphs
• Strictly balanced uniform hypergraphs and generalizations of zero-one law
• Quantifier alternation in first-order formulas with infinite spectra
• On limit points of spectra of first-order sentences with quantifier depth 4
• Infinite spectra of first-order properties for random hypergraphs
• Spectra of first-order formulas with a low quantifier depth and a small number of quantifier alternations
• The first order theory of \(G(n, c/n)\)
• Disproof of the zero-one law for existential monadic properties of a sparse binomial random graph
• Bounded quantifier depth spectra for random graphs
• Logical laws for short existential monadic second-order sentences about graphs
• Ups and downs of first order sentences on random graphs
• Spectrum of FO logic with quantifier depth 4 is finite
• Combinatorial games on Galton-Watson trees involving several-generation-jump moves
• On the spectra of first-order language properties for random graphs

This page was built for publication: First order sentences about random graphs: small number of alternations

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