First order sentences about random graphs: small number of alternations

Aleksandr Matushkin, Maksim Zhukovskii

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 quantif…