Bounds for the quantifier depth in finite-variable logics: Alternation hierarchy

Given two structures $G$ and $H$ distinguishable in $\text{fo}k$ (first-order logic with $k$ variables), let $A^k(G,H)$ denote the minimum alternation depth of a $\text{fo}k$ formula distinguishing $G$ from $H$. Let $A^k(n)$ be the maximum value of $A^k(G,H)$ over $n$-element structures. We prove the strictness of the quantifier alternation hierarchy of $\text{fo}2$ in a strong quantitative form, namely $A^2(n)\ge n\mathrm{/}8-2$, which is tight up to a constant factor. For each $k\ge 2$, it holds that $A^k(n)>{\log }_{k+1}n-2$ even over colored trees, which is also tight up to a constant factor if $k\ge 3$. For $k\ge 3$ the last lower bound holds also over uncolored trees, while the alternation hierarchy of $\fo 2$ collapses even over all uncolored graphs. We also show examples of colored graphs $G$ and $H$ on $n$ vertices that can be distinguished in $\text{fo}2$ much more succinctly if the alternation number is increased just by one: while in ${\mathrm{\Sigma }}_i$ it is possible to distinguish $G$ from $H$ with bounded quantifier depth, in ${\mathrm{\Pi }}_i$ this requires quantifier depth $\mathrm{\Omega }(n^2)$. The quadratic lower bound is best possible here because, if $G$ and $H$ can be distinguished in $\text{fo}k$ with $i$ quantifier alternations, this can be done with quantifier depth $n^{2k-2}$.