一句话：给出 k-WL 稳定迭代次数的上界 O(k n^{k-1} log n) 与下界 n^{Ω(k)}，并揭示维数与迭代次数的权衡。
本文研究 k 维 Weisfeiler-Leman 算法（k-WL）稳定所需的迭代次数。此前仅有 k=2 的 O(n log n) 上界、n^k-1 的平凡上界，以及 n^{Ω(k/log k)} 的下界。作者证明 k≥3 时 k-WL 至多经 O(k n^{k-1} log n) 次迭代稳定，并构造 k 元关系结构使其至少需要 n^{Ω(k)} 次。作者还研究维数与迭代次数的权衡：d=ceil(3(k+1)/2) 维 WL 可用 O(k^2 n^{floor(k/2)+1} log n) 次迭代模拟 k-WL，但对足够小的 d 仍有 n^{Ω(k)} 下界。由于 k-WL 的迭代次数对应带计数量词一阶逻辑 (k+1)-变量片段 C_{k+1} 中句子的量词秩，这些结果同时给出该逻辑量词秩的新上下界及变量数与量词秩的权衡。
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 ≥ 3, we show that k-WL stabilizes after at most O(knk−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 nk − 1 and extending a previous upper bound of O(n log n) for k = 2 [Lichter et al., LICS 2019].We complement our upper bounds by constructing k-ary relational structures on which k-WL requires at least nΩ(k) iterations to stabilize. This improves over a previous lower bound of nΩ(k/logk) [Berkholz, Nordström, LICS 2016].We also investigate tradeoffs between the dimension and the iteration number of WL, and show that d-WL, where $d = \left\lceil {\frac{{3(k + 1)}}{2}} \right\rceil $, can simulate the k-WL algorithm using only O(k2 • n⌊k/2⌋+1 log n) many iterations, but still requires at least nΩ(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 ${{\mathcal{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 ${{\mathcal{C}}_k}_{ + 1}$, as well as tradeoffs between variable number and quantifier rank.