Zero-one laws for existential first order sentences of bounded quantifier depth
The first order language on graphs consists of sentences, or graph properties,
that are expressible using the relations of vertex equality $(x = y)$
and vertex adjacency $(x \sim y)$. In their 1988 paper, Shelah and
Spencer showed that when $0 < \alpha < 1$ is an irrational number,
the Erdös-Rényi random graph $G(n, n^{-\alpha})$ satisfies
the zero-one law for the first order language on graphs, i.e. for
any first order sentence $A$, the limit
$\lim_{n \rightarrow \infty} \mathbb{P}\left[G(n, n^{-\alpha}) \text{ satisfies } A\right]$
exists and equals either $0$ or $1$.
It has been a long-standing question in mathematical logic as to whether
the existential fragment of a given logic is less expressive compared to the
full logic. In particular, one may consider whether, for certain edge probability
functions, the random graph $G(n, p(n))$ satisfies the zero-one law for the
existential fragment but not for the entire logic. In his 2012 paper, Zhukovskii
showed that the minimum $0 < \alpha < 1$ such that $G(n, n^{-\alpha})$ satisfies
the zero-one law for all first order sentences of quantifier depth at most $k$,
is $\frac{1}{k-2}$. At first glance, it seems that this bound can be moved
significantly for existential first order sentences of quantifier depth at most $k$,
but this is not true, since we show that the minimum positive $\alpha$ such that the
zero-one law fails for the existential fragment is $\frac{1}{k - 2 - O(k^{-2})}$.
Joint with Maksim Zhukovskii, Department of Discrete Mathematics, Moscow
Institute of Physics and Technology