Combinatorial Properties of the Weisfeiler-Leman Algorithm

The Weisfeiler-Leman algorithm is a combinatorial procedure that plays a crucial role both in theoretical and practical research on the graph isomorphism problem. For every k there is a k-dimensional version of the algorithm, which repeatedly refines a partition of the set of k-tuples of vertices of the input graph. The final partition can often be used to distinguish non-isomorphic graphs and for every pair of graphs, there is some dimension of the algorithm that decides isomorphism of the two graphs. We have established upper bounds on this dimension for some graph classes. 

By the famous correspondence by Cai, Fürer and Immerman, a graph is identified by the k-dimensional Weisfeiler-Leman algorithm if and only if it is definable in C^(k+1), first order logic with counting and restricted to k+1 variables. Thus, our dimension bounds also yield bounds on the logical complexity of the graph classes.

In order to gain a better understanding of its dynamics and precise complexity, we have also studied the number of iterations of the algorithm until stabilization, which corresponds to the quantifier depth of the corresponding counting logic. 

In this talk, I give an introduction to the mechanisms of the algorithm, present some of our results in this field and relate them to open questions for future work.