Combinatorial Properties of the Weisfeiler-Leman Algorithm
summary
Proves a full combinatorial classification: a graph is identified by 1-dimensional Weisfeiler-Leman exactly if it flips to a bouquet forest, and this yields a polynomial-time test and an extension to finite relational structures with only eight exceptional color-class types. For 2-WL the iteration number is bounded by O(n^2 / log n); the proof builds a two-player game plus auxiliary graphs and a potential function, gives linear bounds when color-class size is fixed (matching Fürer’s lower bound), and so tightens quantifier-depth limits.
AI-written summary · about