pith. sign in

arxiv: 1701.06517 · v3 · pith:NPSLAXWKnew · submitted 2017-01-23 · 🧮 math.CO

First order sentences about random graphs: small number of alternations

classification 🧮 math.CO
keywords firstordersentencespectrumalphaalternationsnumberpoints
0
0 comments X
read the original 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.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.