An Upper Bound on the Weisfeiler-Leman Dimension
<|reference_start|>An Upper Bound on the Weisfeiler-Leman Dimension: The Weisfeiler-Leman (WL) dimension is a standard measure in descriptive complexity theory for the structural complexity of a graph. We prove that the WL-dimension of a graph on $n$ vertices is at most $3/20 \cdot n + o(n)= 0.15 \cdot n + o(n)$. The proof develops various techniques to analyze the structure of coherent configurations.   This includes sufficient conditions under which a fiber can be restored up to isomorphism if it is removed, a recursive proof exploiting a degree reduction and treewidth bounds, as well as an analysis of interspaces involving small fibers.   As a base case, we also analyze the dimension of coherent configurations with small fiber size and thereby graphs with small color class size.<|reference_end|>
@article{schneider2024an,
    title={An Upper Bound on the Weisfeiler-Leman Dimension},
    author={Thomas Schneider and Pascal Schweitzer},
    journal={arXiv preprint arXiv:2403.12581},
    year={2024},
    archivePrefix={arXiv},
    eprint={2403.12581},
    primaryClass={cs.DM cs.LO math.CO}
}