Decomposition Profiles and Weisfeiler-Leman Dimension for Graphs of Bounded Rank Width

1 Introduction

• For linear rank width at most k, the result gives a (2k + 2)-dimensional identification bound; in counting logic, rank-width and linear-rank-width classes use 3k + 2 and 2k + 3 variables, respectively.Only the source graph is equipped with a rank decomposition; the target graph remains arbitrary.Source: §1 · p. 2
• The WL dimension also yields counting-logic definability bounds of 3k+2 variables for rank width and 2k+3 for linear rank width.The one-dimensional procedure identifies edgeless graphs.Source: §1 · pp. 1–2
• Common-round colour codes and component palettes synchronize information across the two graphs, enabling strict-child transitions without simultaneous markers for both children.Root, leaf, and finitary closure arguments complete the identification proof.Source: §1 · p. 2
• Uncoloured CFI constructions give linear lower bounds for both width parameters, making the upper bounds tight up to constant factors.The lower-bound analysis uses split grids; rook and Shrikhande graphs provide constant-three calibration.Source: §1 · pp. 2–3
• The rank-width-k isomorphism test runs in O(n^(3k+2) log n) time, improving the previous exponent by two.The width-sensitive analysis places the indistinguishable pairs inside the corresponding width-bounded classes.Source: §1 · p. 3
• For every r≥1 and q≥r+1, connected graphs can have rank width r and linear rank width q while their optimized profile remains bounded in terms of r.The construction gives ℓ⋆≤min{3r,2r+3} and 2r+2≤d⋆≤min{3r+1,2r+4}.Source: §1 · p. 3
• Optimized quantities obey exact maximum identities under disjoint union and nontrivial split composition; at rank width two, the possible profile pairs are (5,6) and (6,7).Thus global linear rank width alone does not determine the optimized profile pair, and optimization cannot lower the endpoint seven for rank width two.Source: §1 · p. 3
• The theorem addresses identification after unrestricted stabilization, not the number of refinement rounds, optimal dimension, or bounded-depth canonization.For rank width at most two, it gives a seven-dimensional upper bound without determining the class's exact dimension.Source: §1 · p. 3

2.1 Rank decompositions, split pairs, and flips

• A rank decomposition recursively partitions a nonempty graph along a full rooted binary tree, and its width is the maximum cut rank over the decomposition.Rank width minimizes this width over decompositions; linear rank width restricts the decomposition trees to caterpillars.Source: §2.1 · pp. 4–5
• Fork load is the largest sum of the parent and two child cut ranks at a decomposition fork, and it is at most three times the decomposition width.The paper compares its target with previous rank-width bounds of 3k+4 and 3k+3 dimensions [5, Theorem 4.4],.Source: §2.1 · pp. 4, 5, 8
• Split pairs provide bases for the two sides of a cut, while nice child split pairs support the shared-interface choices used at decomposition forks.The preliminaries record the existence of nice child split pairs from [5, Lemma 4.2].Source: §2.1 · pp. 5–7
• Canonical stable colours retain equality information for individualized anchors and admit graph-independent maps from finer anchor types to coarser ones.These maps retain, repeat, or reorder equality coordinates and aggregate neighbour counts over fibres.Source: §2.1 · pp. 5–6
• A flip changes edges according to vertex colours, while the cited invariance results preserve isomorphism and the stable colour-refinement partition under a common flip.The component structure after a split-pair flip is contained on one side of the cut.Source: §2.1 · pp. 6–7

2 Preliminaries

• The bijective pebble game, finite-variable counting logic, and Weisfeiler-Leman refinement characterize the same distinctions, with d-dimensional WL corresponding to d+1 pebbles and variables.Different-order graphs are separated by a one-variable counting sentence.Source: §2 · p. 4, §2.1 · p. 8

3.1 The shared carrier and remoteness

• At each fork, parent and child split-pair occurrences fit in a shared carrier whose size is bounded by the sum of the three incident cut ranks.The remoteness property and carrier acquisition keep at most the fork load plus one live roles, without decomposing the target graph.Source: §3.1 · pp. 8–9

3.2 Remote-union locality

• A stable colouring induces a single map on the union of flipped components that avoid the markers, with each vertex’s resulting colour determined by its original stable colour.The locality argument uses that the remote union is a union of full components and that the colouring is equitable after the flip.Source: §3.2 · p. 10

3.3 Preannounced common maps

• Pointwise preservation of the canonical palette and complete remote-component bit vector forces the source and target maps to agree on colours realized in either remote union.Separate marginal histograms do not suffice; the canonical factor and complete component-bit vector must occur in the same announcement.Source: §3.3 · p. 11

3.4 Common component palettes

• A common pointwise palette with singleton marker classes yields a shared component predicate, while equal stable-colour neighbour counts give the two flipped graphs the same weighted quotient on realized marked colours.The component predicate is obtained by quotient reachability from the marker colour.Source: §3.4 · p. 12

3.5 Canonical reducts and successive stabilization

• A fixed source occurrence map induces a graph-independent forgetful map from complete fine anchor types to coarse types, but not in the reverse direction.The map is built by retaining, repeating, and reordering equality coordinates, then summing neighbour counts over fibres.Source: §3.5 · p. 13
• Successive stabilization gives equivalent stable partitions whether the anchors are individualized together or through the stated sequence of refinements.The proof uses that stable colour refinement is the coarsest equitable refinement of its input colouring.Source: §3.5 · p. 13

4.1 Common-round colour-refinement types

• Round-2n types stabilize on the disjoint union of two n-vertex graphs, and each realized finite type has a unique complete continuation.Each type is definable in counting logic using the q anchor variables and x, y; a source-fixed finite table implements the totalized semantic flip on every order-n target.Source: §4.1 · pp. 14–16

4.2 Finite flip tables and their components

• Lifted-flip adjacency is definable using the anchors and x, y, while a predicate using at most q + 3 variable names identifies whether two vertices lie in the same component.The component recursion expresses walks of bounded length; since a simple path in an n-vertex graph has length at most n − 1, it captures connectedness.Source: §4.2 · p. 17

4.3 Enforcing a finite key

• Finite keys yield a dichotomy: a violating announced bijection lets Spoiler win with bounded pebbles, while a preserving bijection preserves every key fibre and joint key multiplicity.The key coordinates are defined by the same source-fixed formulas on both graphs; the dichotomy also applies to stable-type coordinates and lifted-flip component bits.Source: §4.3 · pp. 18–19

4.4 Application to the parameter bound

• At transition node t, the shared master occurrence has at most ℓD(t) distinct anchors; an ordered split-pair occurrence at s has 2rD(s) entries, and lifted-flip adjacency uses 2rD(s) + 2 names.A transition key probe occupies at most ℓD(t) + 2 roles, bounded by m.Source: §4.4 · p. 19
• Lemma 4.6, (4.18), and (4.19) close the passage from auxiliary transition palettes to the bijective m(D)-pebble game.Keys with many coordinates do not increase variable width: violated coordinates are handled separately with reusable local names, while shared variables and removal of duplicate pairs reduce distinct names and live roles.Source: §4.4 · p. 20

5 The two-palette strict-child transition

• At most m(D) pebble pairs suffice to acquire the carrier and reach a normalized state on a strict child shore, unless Spoiler wins during acquisition.The handoff is to either the F-child or T-child; Spoiler checks the full enlarged position after each reply.Source: §5 · p. 21
• When the selected component lies in X1 and contains the marker, the preserved palette coordinates force a mismatch on the strict first-child state.A mismatch after the F-flip is transferred to an induced component; common-function reductions then yield the child state.Source: §5 · pp. 22, 24
• When the selected component lies in X1 but excludes the marker, two locality applications likewise produce a mismatch on the strict first-child state.The fresh palette refines the F-palette; an isomorphism of the full components would preserve the original mismatch.Source: §5 · p. 24
• When the selected component lies in X2, the argument preserves a parent-component mismatch, reroots at the selected response, and transfers a flipped mismatch to selected cells.The available passage begins the second-child handoff but does not state its completed strict-child conclusion.Source: §5 · pp. 25–26
• When w ∈ D, three locality applications use common base palette βw and lifted flip fβw_T, with common reductions and K1-coordinates determined by βw.The applications use source and target remoteness, and the full-component isomorphism would contradict (5.49).Source: §5 · pp. 26–27
• When w ∉ D, four locality applications use base palette λT and lifted flip fT; their reductions are common, and second-key coordinates are functions of fresh palette λT,z or constants.Remoteness for the second application follows from w ∉ D and w′ ∉ D′; for the others it follows from the stated remoteness equations.Source: §5 · p. 27
• The first two branches descend to X1 and the last two to X2, using at most m(D)−1 predecessor pairs and at most m(D) pairs after the response.Predecessor positions are P, v, and additionally P, w in the second-child case; responses add w or z, respectively. A mismatched mate for an already-pebbled response violates equality immediately.Source: §5 · p. 27
• The transition strictly descends, and after obsolete roles are discarded its boundary retains one pair per distinct child value and the child marker.Duplicate pairs are removed first; pairs without a retained role are then removed.Source: §5 · p. 27

6 Closing the source-guided induction

• At an internal node, Spoiler either wins or descends to a strict child while using at most m pebble pairs.Top-down choices retain the child occurrence at the next boundary, and normalization removes obsolete pebble pairs only after establishing the successor mismatch.Source: §6 · p. 28

6.1 The root and the leaves

• Root initialization establishes a recursive boundary or wins immediately, and every boundary at a leaf yields a win within the same pebble bound.The root argument uses nonisomorphic vertex-coloured connected components; at leaves, a component-size or marked-type formula distinguishes the structures.Source: §6.1 · p. 29

6.2 Finitary closure and the main theorem

• The strategy has a finite winning horizon because its formulas, decomposition height, and announcement choices are finite.The game and Weisfeiler-Leman bounds are uniform over arbitrary finite initial colour maps, independent of how many labels occur.Source: §6.2 · pp. 29–30
• A rooted rank decomposition D gives a dimension-d(D) Weisfeiler-Leman test that identifies every finite nonempty vertex-coloured source graph over the fixed vocabulary.Equivalently, Spoiler wins with d(D)+1 pebble pairs against every same-order nonisomorphic target.Source: §6.2 · p. 29
• Rank-width-at-most-k graphs are identified by (3k + 1)-dimensional Weisfeiler-Leman, while rank-width-zero graphs are identified in dimension one.The rank-width bound follows from w(D) ≤ k and ℓ(D) ≤ 3k for a width-at-most-k decomposition.Source: §6.2 · p. 30
• Linear-rank-width-at-most-k graphs are identified by (2k + 2)-dimensional Weisfeiler-Leman, and edgeless graphs require only dimension one.A linear layout yields a rooted comb decomposition whose internal forks have two cut ranks at most k and one singleton cut rank at most one.Source: §6.2 · p. 30

Optimized bounds

• For every finite nonempty graph, 2rw(G) ≤ ℓ⋆(G) ≤ 3rw(G) and ℓ⋆(G)+1 ≤ d⋆(G) ≤ ℓ⋆(G)+2; odd ℓ⋆ gives d⋆=ℓ⋆+1, while ℓ⋆=2rw gives d⋆=ℓ⋆+2.The two endpoint cases follow from the fork-load sandwich; the dimension bound is the optimized identification bound.Source: §7 · p. 31

Stability

• For a nonempty induced subgraph H of G, rank width and optimized profile coordinates do not increase; adding a pendant vertex to connected G with at least three vertices preserves all three quantities.Restriction is achieved by pruning and suppressing the decomposition tree; pendant addition preserves rank width, ℓ⋆, and d⋆ exactly.Source: §7 · p. 32

Minimum trees

• The recursively constructed tree Rq has linear rank width q, and every tree of linear rank width at least q has at least |V(Rq)| vertices.Rq is formed from three copies of Rq−1 joined to a new central vertex, with R1=K2; path width equals linear rank width on forests.Source: §7 · pp. 32–33

Exact separation

• For connected G on at least three vertices and every q≥1, an induced connected extension Gq preserves rank width and optimized profiles while attaining lrw(Gq)=max{lrw(G),q}.The extension identifies G with Rq at layout endpoints; its attached tree has minimum order among trees of linear rank width at least q. The endpoint one-sum of A and B likewise has lrw equal to max{lrw(A),lrw(B)}.Source: §7 · pp. 32–33

Exact separation at every rank

• For integers r ≥ 1 and q ≥ r + 1, there is a connected graph G_{r,q} with linear rank width exactly q, and ℓ⋆ ≤ min{2r + 3, 3r}, d⋆ ≤ min{2r + 4, 3r + 1}.Source: §7 · p. 33

Split composition and atomic profiles

• Optimized fork load and dimension obey exact maximum identities under split composition and, across terminal split factors, equal the maximum factor profiles regardless of replacement order.The atomic factorization starts from connected components and repeatedly replaces factors with marker factors at nontrivial splits.Source: §7 · pp. 34–35

• The graph P is split-prime, has rank width two and linear rank width three, and has an optimized profile pair given by Proposition 7.13.Its rank width follows from a width-two decomposition and the rank-two shore in every binary decomposition; every layout has a three-vertex prefix of cut rank three.Source: §7 · p. 37
• The minimum orders for optimized profile pairs (5, 6) and (6, 7) are five and six, respectively, among graphs of rank width exactly two.Source: §7 · p. 37
• C5 attains the five-vertex minimum with rank width and linear rank width two and optimized profile pair (5, 6).Source: §7 · p. 37
• Every graph with optimized profile pair (6, 7) has at least six vertices, and the triangular prism attains that order.The lower bound follows because such a graph has a terminal factor of rank width two and linear rank width at least three.Source: §7 · p. 37

Optimized profiles

• At rank width two, the optimized profile pairs are (5, 6) and (6, 7), and the same (rw, lrw)=(2, q) can have either pair for every q ≥3.The endpoint seven is exact for this method, but does not establish that a graph requires seven-dimensional Weisfeiler-Leman.Source: §8 · p. 38

CFI layout bound

• For consecutive-fibre layouts, the coefficient two cannot be improved by a uniform per-edge estimate; a split-grid cut reaches rank 2n.A stronger bound would require additional global structure, an interleaved layout, or a different construction.Source: §8 · p. 40

Calibration

• The rook and Shrikhande graphs are nonisomorphic yet share a stable two-dimensional Weisfeiler-Leman colouring, so each has dimension at least three.Both are strongly regular with parameters (16, 6, 2, 2); the explicit layout gives each linear rank width at most five.Source: §8 · p. 40

Asymptotic ranges

• Dlrw(r) = Θ(r), with upper bound 2r + 2 for r ≥ 5; Drw(r) = Θ(r), with upper bound 3r + 1 for r ≥ 4.Source: §8 · pp. 41–42
• For r ≥6, linear rank width has lower bound ⌊r/2⌋−1; for r ≥4, rank width has lower bound ⌊r/2⌋.The CFI pairs used for these bounds have Weisfeiler-Leman dimension at least n under the respective width bounds.Source: §8 · pp. 41–42

Algorithmic consequences

• For linear rank width at most k, isomorphism testing and canonization have respective running times O(n^(2k+3) log n) and O(n^(2k+5) log n).The proof applies the dimension bound 2k + 2 and the generic canonization construction.Source: §8 · p. 42

Conclusion

• Theorem 6.5 gives dimensions 3k + 1 for rank width at most k and 2k + 2 for linear rank width at most k, improving prior unrestricted rank-width bounds.The stated improvements are two dimensions over the 3k + 3 estimate [17, Corollary 3.12] and three over the published 3k + 4 bound [5].Source: §9 · p. 42
• Optimized profile pairs contain information not captured by rank width or linear rank width alone, while CFI constructions give linear lower bounds for both width parameters.At rank width two, the only optimized pairs are (5, 6) and (6, 7); rook and Shrikhande graphs provide small-parameter calibration.Source: §9 · p. 42
• The bounds concern dimension after unrestricted stabilization, do not bound quantifier depth or yield fixed-point canonization, and leave the exact value of D2 open.The identified obstruction within the method is a fork with three large incident cut ranks.Source: §9 · p. 42

• verify_calculations.py checks the paper’s finite enumerations and calibration examples, but does not machine-check its general proofs.Source: Reproducibility materials · p. 43