First order sentences about random graphs: Small number of alternations

The spectrum of a first order sentence is the set of all α such that G(n,n−α) does not obey zero–one law with respect to this sentence. In this paper, we prove that the minimal number of quantifier alternations of a first order sentence with infinite spectrum equals 3. We have also proved that the spectrum of a first-order sentence with quantifier depth 4 has no limit points except possibly the points 1∕2 and 3∕5. © 2017 Elsevier B.V.

Authors
Matushkin A.D.1 , Zhukovskii M.E. 2
Publisher
Elsevier B.V.
Language
English
Pages
329-346
Status
Published
Volume
236
Year
2018
Organizations
  • 1 Moscow Institute of Physics and Technology, Laboratory of Advanced Combinatorics and Network Applications, Russian Federation
  • 2 Moscow Institute of Physics and Technology, Laboratory of Advanced Combinatorics and Network Applications, RUDN University, Russian Federation
Keywords
First order logic; Random graphs; Spectrum of first order sentences; Zero–one laws
Share

Other records