The Iteration Number of the Weisfeiler-Leman Algorithm

We prove new upper and lower bounds on the number of iterations the \(k\) -dimensional Weisfeiler-Leman algorithm ( \(k\) -WL) requires until stabilization. For \(k\geq 3\) , we show that \(k\) -WL stabilizes after at most \(O(kn^{k-1}\log n)\) iterations (where \(n\) denotes the number of vertices of the input structures), obtaining the first improvement over the trivial upper bound of \(n^{k}-1\) and extending a previous upper bound of \(O(n\log n)\) for \(k=2\) . We complement our upper bounds by constructing \(k\) -ary relational structures on which \(k\) -WL requires at least \(n^{\Omega(k)}\) iterations to stabilize. This improves over a previous lower bound of \(n^{\Omega(k/\log k)}\) . We also investigate tradeoffs between the dimension and the iteration number of WL, and show that \(d\) -WL, where \(d=\lceil\frac{3(k + 1)}{2}\rceil\) , can simulate the \(k\) -WL algorithm using only \(O(k^{2}\cdot n^{\lfloor k/2\rfloor+1}\log n)\) many iterations, but still requires at least \(n^{\Omega(k)}\) iterations for any \(d\) (that is sufficiently smaller than \(n\) ). The number of iterations required by \(k\) -WL to distinguish two structures corresponds to the quantifier rank of a sentence distinguishing them in the \((k + 1)\) -variable fragment \(\mathsf{C}_{k + 1}\) of first-order logic with counting quantifiers. Hence, our results also imply new upper and lower bounds on the quantifier rank required in the logic \(\mathsf{C}_{k + 1}\) , as well as tradeoffs between variable number and quantifier rank.