Bounds for the quantifier rank in two-variable logic

Oleg Verbitsky

We show examples of colored graphs, both on n vertices, that in the existential two-variable logic can be distinguished only with quantifier rank more than n^2/11. This bound is tight up to a constant factor. It contrasts with the fact that, if graphs are distinguishable in the unrestricted two-variable logic, they can be distinguished with quantifier depth at most n. We also discuss extensions of these results to logics with more variables and/or with more quantifier alternations. In particular, we show that the quantifier alternation hierarchy for k-variable logic is strict over colored trees. Without colors, this result holds true if k>2.

This is an ongoing work with Christoph Berkholz and Andreas Krebs.