Near-Optimal Lower Bounds on Quantifier Depth and Weisfeiler-Leman Refinement Steps

Christoph Berkholz, Jakob Nordström

We prove near-optimal trade-offs for quantifier depth versus number of variables in first-order logic by exhibiting pairs of $n$-element structures that can be distinguished by a $…