  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$
[Lichter et al., LICS 2019].
  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)}$ [Berkholz,
Nordstr\"{o}m, LICS 2016].
  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 $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 $C_{k+1}$, as well as tradeoffs between
variable number and quantifier rank.
