Twin-width¶
A graph parameter equal to the least possible maximum red degree over all complete vertex-contraction sequences that mark adjacency disagreements.
Core Idea¶
Twin-width is the minimum possible maximum red disagreement degree over complete contraction sequences of a finite simple graph. Twin-width minimizes the maximum red disagreement degree over complete vertex-contraction sequences. True-twin merges introduce no disagreement, while other merges create red edges where adjacency histories conflict. A certificate is the whole sequence with red updates, not the final vertex or one good merge. Twin-width differs from treewidth, clique-width, and rank-width, and algorithmic benefits generally require a bounded-width sequence or a method to find one.
Scope of Application¶
The concept applies in graph algorithms and related work when its identity and evidence are explicit. Use it with the trigraph update rule, entire sequence, maximum red degree, and exact-versus-upper-bound status explicit; distinguish treewidth, clique-width, and informal graph similarity.
- Graph algorithms. Parameterizes complexity.
- Structural graph theory. Classifies graph families.
- Model theory. Supports definability algorithms.
- Combinatorics. Studies contraction orders.
- Certification. Checks bounded-width sequences.
Clarity¶
State graph convention, complete contraction order, trigraph update rule, maximum red degree, and whether the value is exact or only bounded. The closest near miss sets the boundary: Clique-width is the closest miss: both study algorithmically tame dense graphs but use different construction certificates.
Manages Complexity¶
Twin-width compresses global adjacency structure into local disagreement accumulated during contraction, enabling tractability without requiring graph sparsity. Twin-width is defined through a whole contraction sequence, not by one favorable pair of vertices. At each merge, adjacency disagreements are marked red in the evolving trigraph; the width of the sequence is its maximum red degree, and graph twin-width is the minimum over all sequences. True twins create no new disagreement, which explains cographs' especially low values, but bounded twin-width allows carefully controlled non-twin mergers. A certificate therefore contains the sequence and its red-edge updates, not merely the final one-vertex graph. The parameter is distinct from treewidth, clique-width, and rank-width: classes can behave differently under each measure. Its algorithmic value comes from parameterized tractability results when a bounded-width contraction sequence is available or constructible; a small claimed number without such evidence is not enough. The central expressiveness–tractability tradeoff is this: Broad graph classes remain algorithmically manageable when d is bounded. A second local merge–global optimum tension matters because Greedy similarity may not minimize later red degree.
Abstract Reasoning¶
Use three linked moves: fix the finite simple graph; choose and record a complete merge sequence; update black and red adjacencies exactly. As a collapse test, identity collapses when disagreement tracking or minimization over complete sequences is removed. A fourth check is to measure maximum red degree.
Knowledge Transfer¶
Disagreement-bounded contraction transfers as a reasoning pattern, but literal twin-width requires the graph trigraph definition. No canonical parent prime is currently asserted; broader structural comparisons remain related-prime analogies until separately adjudicated in the DAG. True-twin reducibility motivates the parameter.
Relationships to Other Abstractions¶
Current abstraction Twin-width Domain-specific
Parents (1) — more general patterns this builds on
-
Twin-width is a kind of Graph Invariant Domain-specific
Twin-width satisfies the defining boundary of Graph Invariant: A graph invariant is a value, polynomial, sequence, multiset, or other mathematical object assigned to a graph such that isomorphic graphs receive the same result, with its definition, graph category, and distinguishing power explicitly stated.
Hierarchy path (1) — routes to 1 parentless root
- Twin-width → Graph Invariant
Neighborhood in Abstraction Space¶
Twin-width sits in a moderately populated region (45th percentile for distinctiveness): it has near-neighbors but no dense thicket of look-alikes.
Family — Formal Grammars & Parsing Complexity (7 abstractions)
Nearest neighbors
- Edge Covering Number — 0.88
- Chordal bipartite graph — 0.86
- Sierpiński Graph — 0.86
- Induced Path — 0.86
- Total graph — 0.86
Computed from structural-signature embeddings · 2026-10-08