Definitions with no quantifier alternation

Abstract

Let $D(G)$ be the minimum quantifier depth of a first order sentence $\Phi$ that defines a graph $G$ up to isomorphism. Let $D_0(G)$ be the version of $D(G)$ where we do not allow quantifier alternations in $\Phi$. Define $q_0(n)$ to be the minimum of $D_0(G)$ over all graphs $G$ of order $n$. We prove that for all $n$ we have ${\log }^{\ast }n-{\log }^{\ast }{\log }^{\ast }n-1\le q_0(n)\le {\log }^{\ast }n+22$, where ${\log }^{\ast }n$ is equal to the minimum number of iterations of the binary logarithm needed to bring $n$ to 1 or below. The upper bound is obtained by constructing special graphs with modular decomposition of very small depth.

24 pages, we complement the lower bound proved in the first version with a tight upper bound. The title of the paper has been changed