Weisfeiler-Lehman Refinement Requires at Least a Linear Number of Iterations

Let L _k , _m be the set of formulas of first order logic containing only variables from x₁, x₂, . . . , x _K and having quantifier depth at most m. Let C_k,_m be the extension of L _k,m obtained by allowing counting quantifiers ∃ix _j , meaning that there are at least i distinct x _j ’s.It is shown that for constants h ≥ 1, there are pairs of graphs such that h-dimensional Weisfeiler-Lehman refinement (h-dim W-L) can distinguish the two graphs, but requires at least a linear number of iterations. Despite of this slow progress, 2h-dim W-L only requires O(√n) iterations, and 3h—1-dim W-L only requires O(log n) iterations. In terms of logic, this means that there is a c > 0 AND A CLASS OF NON-ISOMORPHIC PAIRS $$ (\mathop G\nolimits_{n,}^h \mathop H\nolimits_n^h ) $$ of graphs with $$ \mathop G\nolimits_n^h and \mathop H\nolimits_n^h $$ having O(n) vertices such that the same sentences of L_h+1,cn and C_h+1,cn hold (h + 1 variables, depth cn), even though $$ \mathop G\nolimits_n^h and \mathop H\nolimits_n^h $$ can already be distinguished by a sentence of L _k,m and thus C _k,m for some k > h and m = O(log n).