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 measures how economically a graph can be contracted while keeping adjacency disagreements locally bounded.
Merging true twins creates no new disagreement; non-twin merges mark mixed relations red in the evolving trigraph.
A sequence's width is its maximum red degree, and graph twin-width is the minimum across all complete sequences.
Structural Signature¶
Sig role-phrases:
- finite simple graph. Supplies vertices and adjacency. Constitutive input. If altered: Directed/multigraph variants need separate definitions.
- contraction sequence. Orders merges until one vertex remains. Constitutive witness. If altered: A partial sequence is insufficient.
- bags/merged vertices. Represent original vertex sets. State carrier. If altered: Bag membership affects adjacency histories.
- black adjacency. Marks unanimous edge/nonedge relation. Constitutive relation. If altered: Agreement must be distinguished from uncertainty.
- red disagreement edges. Record mixed adjacency after merging. Identity-bearing defect. If altered: Ignoring them trivializes every graph.
- maximum/minimization. Takes maximum red degree then minimum over sequences. Constitutive optimization. If altered: One sequence gives only an upper bound.
What It Is Not¶
- Not treewidth. Twin-width can handle dense structures differently.
- Not one merge. The whole sequence matters.
- Not red-edge total. Maximum red degree is controlled.
- Not a claimed value without witness/lower bound. A sequence alone proves an upper bound.
Scope of Application¶
The concept applies in graph algorithms and related work when its identity and evidence are explicit.
- 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.
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.
Abstract Reasoning¶
- Fix the finite simple graph.
- Choose and record a complete merge sequence.
- Update black and red adjacencies exactly.
- Measure maximum red degree.
- Minimize or provide separate lower-bound evidence.
Knowledge Transfer¶
Disagreement-bounded contraction transfers as a reasoning pattern, but literal twin-width requires the graph trigraph definition.
Examples¶
Canonical¶
A cograph repeatedly merges true twins, so no disagreement red edges are introduced and the sequence witnesses very small twin-width.
Mapped back: finite simple graph → cograph; contraction sequence → true-twin merges; bags/merged vertices → recursive modules; black adjacency → uniform external neighborhoods; red disagreement edges → none/newly bounded; maximum/minimization → sequence certificate.
Applied / In Practice¶
An algorithm receives a graph plus a d-sequence, verifies every red update, and uses d as its parameter without claiming the sequence is globally optimal.
Mapped back: finite simple graph → input graph; contraction sequence → supplied d-sequence; bags/merged vertices → tracked bags; black adjacency → unanimous relations; red disagreement edges → verified mixed relations; maximum/minimization → upper bound d.
Structural Tensions¶
T1: expressiveness vs. tractability. Broad graph classes remain algorithmically manageable when d is bounded. Diagnostic: Is a bounded sequence available?
T2: local merge vs. global optimum. Greedy similarity may not minimize later red degree. Diagnostic: What lower-bound or search evidence supports exactness?
Structural–Framed Character¶
Twin-width is structural-formal and measured. Individuation is graph-specific; agency/normativity/temporality are absent; robustness follows isomorphism but not rule changes. The portable controlled-contraction-defect skeleton is a future-prime candidate. Its character: minimax adjacency disagreement across graph contraction. A second source of difficulty is that contractions destroy the original vertex scale. Red degree belongs to current bags in the trigraph, not necessarily to any original vertex, and later merges inherit earlier uncertainty. Complementing a graph and relabeling vertices preserve the underlying kind of structural question, while changing the red-update convention does not. Exact lower bounds can require arguments that every possible early choice eventually produces enough disagreement. Thus computing twin-width is an optimization problem over histories, not a static count available from the original adjacency matrix. When an algorithm assumes a given contraction sequence, complexity guarantees should not be restated as efficient recognition of minimum twin-width.
Structural Core vs. Domain Accent¶
Skeletal core. Repeated aggregation introduces inconsistencies whose local maximum is minimized.
Domain-bound accent. Vertices, twins, trigraph red edges, contraction sequences, and graph algorithms specify twin-width.
Why not prime. Controlled aggregation travels, while twin-width is an exact graph invariant.
Instantiates / Related Primes¶
This entry is a kind of Graph Invariant.
- Related — cograph. True-twin reducibility motivates the parameter.
- Related — parameterized complexity. Algorithms use bounded twin-width.
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.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
Not to Be Confused With¶
- Treewidth. Tell: Separator tree or red contraction?
- Clique-width. Tell: Label construction or contraction disagreement?
- Contraction complexity. Tell: Which defect measure?
- d-sequence. Tell: Certificate or exact optimum?
References¶
- Frozen Wikipedia discovery revision: https://en.wikipedia.org/wiki/Twin-width (revision 1370533346).
- Preserved source candidate: http://www.graphclasses.org/classes/gc_151.html
- Preserved source candidate: http://www.graphclasses.org
The frozen Wikipedia revision is discovery provenance. The retained source set was reviewed for identity, formal or operational relation, and scope. The encyclopedia's structural synthesis is bounded to those claims; a thin authority surface is recorded as a nonblocking source-strengthening repair rather than concealed.