Decomposition Profiles and Weisfeiler-Leman Dimension for Graphs of Bounded Rank Width
Abstract
The Weisfeiler-Leman (WL) algorithm tests graph isomorphism by assigning colours to d-tuples of vertices and iteratively refining the colouring according to neighbourhood configurations until it stabilizes. Increasing d allows the test to detect finer structural differences between graphs, but the computational cost grows exponentially with d. The central question is which dimension allows us to distinguish nonisomorphic graphs. We relate a sufficient such dimension to the structure of a graph G through a rank decomposition over 𝔽2. The two parameters governing the bound are the maximum cut rank w and the fork load ℓ, which is the largest sum of the parent and two child cut ranks at a fork in the decomposition tree. We prove that WL in dimension max{ℓ+1,2w+2} distinguishes every finite nonempty vertex-coloured graph G with such a decomposition from every graph not isomorphic to G. Consequently, for k≥1, graphs of rank width at most k can be distinguished from every nonisomorphic graph in dimension 3k+1, graphs of linear rank width at most k in dimension 2k+2, and edgeless graphs in dimension one. Uncoloured Cai-Fürer-Immerman (CFI) constructions give linear lower bounds for both width parameters, so the upper bounds are tight up to constant factors.
Related
- An infinite family of intransitive directed strongly regular graphs with rank 6 Weisfeiler--Leman closure
- Decomposition of functions of bounded variation in Ahlfors-regular PI spaces
- Bounded VC-dimension implies the Erdős--Rado sunflower conjecture
- Finite Borel asymptotic dimension of bounded-to-one commutative monoid actions
- Largest Sperner families with bounded VC-dimension
BibTeX
@misc{kalampakas2026decomposition,
title = {{Decomposition Profiles and Weisfeiler-Leman Dimension for Graphs of Bounded Rank Width}},
author = {Antonios Kalampakas},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.10800},
eprint = {2610.10800},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.10800},
}
RIS
TY - UNPB
TI - Decomposition Profiles and Weisfeiler-Leman Dimension for Graphs of Bounded Rank Width
AU - Antonios Kalampakas
PY - 2026
DA - 2026/10/07
PB - arXiv
DO - 10.48550/arxiv.2610.10800
UR - https://arxiv.org/abs/2610.10800
AB - The Weisfeiler-Leman (WL) algorithm tests graph isomorphism by assigning colours to d-tuples of vertices and iteratively refining the colouring according to neighbourhood configurations until it stabilizes. Increasing d allows the test to detect finer structural differences between graphs, but the computational cost grows exponentially with d. The central question is which dimension allows us to distinguish nonisomorphic graphs. We relate a sufficient such dimension to the structure of a graph G through a rank decomposition over 𝔽_2. The two parameters governing the bound are the maximum cut rank w and the fork load ℓ, which is the largest sum of the parent and two child cut ranks at a fork in the decomposition tree. We prove that WL in dimension max{ℓ+1,2w+2} distinguishes every finite nonempty vertex-coloured graph G with such a decomposition from every graph not isomorphic to G. Consequently, for k≥1, graphs of rank width at most k can be distinguished from every nonisomorphic graph in dimension 3k+1, graphs of linear rank width at most k in dimension 2k+2, and edgeless graphs in dimension one. Uncoloured Cai-Fürer-Immerman (CFI) constructions give linear lower bounds for both width parameters, so the upper bounds are tight up to constant factors.
ER -