First order sentences about random graphs: small number of alternations
classification
🧮 math.CO
keywords
firstordersentencespectrumalphaalternationsnumberpoints
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.