Zero-one laws for existential first order sentences of bounded quantifier depth

Abstract

For any fixed positive integer $k$, let ${\alpha }_k$ denote the smallest $\alpha \in (0,1)$ such that the random graph sequence $\left\{G\left(n,n^{-\alpha }\right)\right\}$ does not satisfy the zero-one law for the set ${\mathcal{E}}_k$ of all existential first order sentences that are of quantifier depth at most $k$. This paper finds upper and lower bounds on ${\alpha }_k$, showing that as $k\to \infty$, we have ${\alpha }_k={\left(k-2-t(k)\right)}^{-1}$ for some function $t(k)=\Theta (k^{-2})$. We also establish the precise value of ${\alpha }_k$ when $k=4$.

43 Pages in total, 25 Pages without Appendix, 16 figures. In this new version, further literature discussion, including a recent development in this direction, added