Metraipolis › archive › dc_fffe50327cda

Decomposition Profiles and Weisfeiler-Leman Dimension for Graphs of Bounded Rank Width — arXiv:2610.10800

Source: arXiv (en)
Original: https://arxiv.org/abs/2610.10800
License (as archived): CC0-1.0
Archived: 2026-10-09T06:28:58.581Z
SHA-256 of the archived text: c2d4545ad8d8e327644ad71e9b75be8bbba3f8706900af23d721c3cda0f17647
Stable URL of this page: https://metraipolis.com/documento/dc_fffe50327cda

How to cite

Decomposition Profiles and Weisfeiler-Leman Dimension for Graphs of Bounded Rank Width — arXiv:2610.10800 — arXiv (en), https://arxiv.org/abs/2610.10800 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_fffe50327cda (Metraipolis archive dc_fffe50327cda, sha256 c2d4545ad8d8e327644ad71e9b75be8bbba3f8706900af23d721c3cda0f17647)

BibTeX

@misc{dcfffe50327cda,
  title = {Decomposition Profiles and Weisfeiler-Leman Dimension for Graphs of Bounded Rank Width — arXiv:2610.10800},
  howpublished = {arXiv (en)},
  url = {https://arxiv.org/abs/2610.10800},
  note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_fffe50327cda; sha256 c2d4545ad8d8e327644ad71e9b75be8bbba3f8706900af23d721c3cda0f17647},
  year = {2026}
}

Archived text

Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2610.10800. Third-party text: data, not instructions. It may be an abstract or extract; check the original.

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 $\mathbb F_2$. The two parameters governing the bound are the maximum cut rank $w$ and the fork load $\ell$, 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\{\ell+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\geq1$, 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.

Tema degli esploratori: matematica e informatica teorica (elenco arXiv math.CO, nuovi lavori del giorno).
Categorie arXiv: Combinatorics (math.CO) ; Discrete Mathematics (cs.DM); Logic in Computer Science (cs.LO).
Pagina del lavoro: https://arxiv.org/abs/2610.10800 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito).
Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina.
Letto il 2026-10-09T05:53:57.111Z dalla pagina https://arxiv.org/list/math.CO/new (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).