Saved in:
| Main Author: | |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | https://arxiv.org/abs/2602.21557 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866915853254000640 |
|---|---|
| author | Velilla, Eduar Castrillo |
| author_facet | Velilla, Eduar Castrillo |
| contents | DRESS is a deterministic, parameter-free framework that iteratively refines the structural similarity of edges in a graph to produce a canonical fingerprint: a real-valued edge vector, obtained by converging a non-linear dynamical system to its unique fixed point. $Δ^k$-DRESS extends the framework by running DRESS on every $k$-vertex-deleted subgraph of $G$; it was introduced and empirically evaluated in the companion paper, where the CFI staircase showed that $Δ^k$-DRESS matches $(k{+}2)$-WL for $k = 0, 1, 2, 3$. This paper provides the theoretical justification. The main contributions are: (i) an unconditional proof that $Δ^k$-DRESS distinguishes every CFI$(K_{k+3})$ pair for all $k \geq 0$ (CFI Staircase Theorem), established via a new CFI Deck Separation theorem and the Virtual Pebble Lemma; and (ii) a conditional proof that $Δ^k$-DRESS $\geq$ $(k{+}2)$-WL for all graphs and all $k \geq 0$, assuming a single structural conjecture about the WL hierarchy (WL-Deck Separation). |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2602_21557 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | DRESS and the WL Hierarchy: Climbing One Deletion at a Time Velilla, Eduar Castrillo Data Structures and Algorithms Discrete Mathematics DRESS is a deterministic, parameter-free framework that iteratively refines the structural similarity of edges in a graph to produce a canonical fingerprint: a real-valued edge vector, obtained by converging a non-linear dynamical system to its unique fixed point. $Δ^k$-DRESS extends the framework by running DRESS on every $k$-vertex-deleted subgraph of $G$; it was introduced and empirically evaluated in the companion paper, where the CFI staircase showed that $Δ^k$-DRESS matches $(k{+}2)$-WL for $k = 0, 1, 2, 3$. This paper provides the theoretical justification. The main contributions are: (i) an unconditional proof that $Δ^k$-DRESS distinguishes every CFI$(K_{k+3})$ pair for all $k \geq 0$ (CFI Staircase Theorem), established via a new CFI Deck Separation theorem and the Virtual Pebble Lemma; and (ii) a conditional proof that $Δ^k$-DRESS $\geq$ $(k{+}2)$-WL for all graphs and all $k \geq 0$, assuming a single structural conjecture about the WL hierarchy (WL-Deck Separation). |
| title | DRESS and the WL Hierarchy: Climbing One Deletion at a Time |
| topic | Data Structures and Algorithms Discrete Mathematics |
| url | https://arxiv.org/abs/2602.21557 |