Definitions with no quantifier alternation

Oleg Pikhurko, Joel Spencer, Oleg Verbitsky

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