Haven (Graph Theory)¶

Assign every deletion set smaller than a stated order to a surviving connected component in a nested or pairwise-touching way, certifying an evader's coherent refuge and dualizing bounded treewidth.

Version: v3 · 2026-09-19 · History
Domain-specific #: 1987
Domain group: Formal Sciences
Origin domain: Mathematics
Subdomain: Structural Graph Theory → Mathematics
Aliases: Graph haven, K-haven

Core Idea¶

Let \(G\) be an undirected graph. For a vertex set \(X\), an \(X\)-flap is a nonempty connected component of \(G-X\). A haven of order \(k\) is a function \(\beta\) assigning an \(X\)-flap \(\beta(X)\) to every \(X\subseteq V(G)\) with \(|X|<k\), subject to a coherence condition. In the monotone convention, \(X\subseteq Y\) implies \(\beta(Y)\subseteq\beta(X)\). In the original touching convention, every two selected flaps touch: they intersect or an edge joins them.

How would you explain it like I'm…

The Hider's Secret Rulebook

Picture a big maze of rooms joined by hallways, and a hide-and-seek game. A few seekers stand in some rooms, blocking them. A haven is a secret rulebook that always tells the hider which connected part of the maze to hide in. When one more seeker shows up, the rulebook only makes the hiding area smaller, so the hider never has to run past a seeker.

Always-Safe Hiding Piece

A graph is dots connected by lines. If you remove a few dots, the graph can break into separate pieces. A haven of order k is a rule that, for every way of removing fewer than k dots, picks one of the leftover pieces. It picks them consistently, always pointing toward the same tough-to-split region. Think of fewer than k seekers standing on dots while a hider stays in the chosen piece. Adding a seeker only shrinks the hider's safe piece. How big a haven a graph can have tells you how hard the graph is to break into a tree-like shape.

Haven: Treewidth Escape Strategy

In a graph G, delete a vertex set X. Each nonempty connected piece left over is called an X-flap. A haven of order k assigns an X-flap β(X) to every X with fewer than k vertices, and it does so coherently. In one convention, adding vertices to X only shrinks the chosen flap. In another, any two chosen flaps touch: they overlap or an edge joins them. This acts as an escape strategy for a robber against fewer than k cops, always pointing toward one region that can't be cut off. For finite graphs, the largest haven order is exactly the treewidth plus one. That makes a haven a certificate that a graph cannot be decomposed in a narrow, tree-like way.

Let G be an undirected graph. For X ⊆ V(G), an X-flap is a nonempty connected component of G − X. A haven of order k is a function β that assigns to each X with |X| < k an X-flap β(X), subject to a coherence condition. In the monotone version, X ⊆ Y implies β(Y) ⊆ β(X). In the original touching version, every two selected flaps intersect or are joined by an edge. In pursuit–evasion terms, fewer than k pursuers occupy X and the evader stays in β(X). Monotonicity guarantees that adding a pursuer narrows the safe region without forcing the evader through an occupied vertex. For finite graphs, G has a haven of order k if and only if tw(G) ≥ k − 1, so the maximal haven order equals treewidth plus one. Touching havens match brambles in order; a bramble is a family of pairwise-touching connected subgraphs that needs at least k vertices to hit. A haven is thus a min–max obstruction to narrow tree decompositions. The finite theorem does not transfer to infinite graphs: a ray has treewidth one yet supports a haven of countable order.

Scope of Application¶

Havens are literal in structural and algorithmic graph theory when one needs a functional certificate that no deletion set below a given size can eliminate every coherent connected refuge.

Treewidth characterization. Certifying lower bounds and proving the finite treewidth min–max theorem.
Graph searching. Describing winning evader strategies against a bounded number of pursuers.
Bramble duality. Converting between functional and hitting-set certificates of width.
Separator theorems. Showing that absence of a small balanced separator induces a high-order haven.
Graph minor theory. Relating large coherent regions, treewidth, grid-like structure, and excluded minors.
Algorithmic certificates. Supplying independently checkable witnesses that a proposed narrow decomposition cannot exist.
Infinite graph ends. Associating countable-order havens with equivalence classes of rays under the appropriate theorem.
Infinite clique minors. Studying uncountable haven orders under results distinct from the finite treewidth equivalence.

Clarity¶

State whether the graph is finite, the exact order \(k\), and whether order means the function accepts sets of size less than \(k\). Define \(X\)-flap as a connected component of \(G-X\). State the monotone or touching convention and do not use their formulas interchangeably, although finite existence at a given order agrees. When invoking treewidth, retain the offset: order \(k\) corresponds to treewidth at least \(k-1\).

Manages Complexity¶

A haven compresses exponentially many possible small cuts into one coherent function. It provides a local response—choose this remaining component—for every adversarial deletion while certifying one global fact: the graph cannot be organized into a tree decomposition below the corresponding width. This functional view can be easier to use in game and separator arguments than manipulating all decompositions. The compression is still difficult computationally because its domain can be huge, and an informal rule for choosing a large component may fail coherence.

Abstract Reasoning¶

Fix an undirected graph, an order, and the monotone or touching convention.
Enumerate conceptually all vertex deletion sets smaller than the order.
For each set, identify the connected components of the remaining graph.
Propose a selection rule for one nonempty component at every input.
Prove nesting under inclusion or pairwise touching, according to convention.
Translate the selection into an evader response while respecting the game's move rules.

Knowledge Transfer¶

The strict parent is Function Mapping: a haven assigns each admissible vertex set exactly one connected component of the corresponding deletion graph. Connectedness, Hierarchy, and Network supply essential context, while Treewidth and Bramble are domain-specific peers. The haven name transfers only when the mapping is total on all small deletion sets and satisfies its global coherence condition.

Relationships to Other Abstractions¶

Current abstraction Haven (Graph Theory) Domain-specific

Parents (1) — outgoing typed relations

Haven (Graph Theory) is a kind of Function (Mapping) Prime

Function Mapping is the strict parent because a haven is formally a total single-valued assignment from every small vertex subset to one eligible connected component.

Hierarchy path (1) — routes to 1 parentless root

Haven (Graph Theory) → is a kind of Function (Mapping)

Neighborhood in Abstraction Space¶

Haven (Graph Theory) sits in a sparse region of the domain-specific corpus (78^th percentile for distinctiveness): few abstractions share its structure, so a faithful description tends to retrieve it precisely.

Family — Graph Classes & Invariants (40 abstractions)

Nearest neighbors

Computed from structural-signature embeddings · 2026-10-25