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: v2 · 2026-09-06 · History
Domain-specific #: 1987
Origin domain: mathematics
Subdomain: structural graph theory
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.^[1]

The function encodes a globally consistent answer to every small vertex deletion. Rather than selecting a different arbitrary component after each cut, it keeps pointing toward one inseparable region of the graph. In a pursuit–evasion interpretation, fewer than \(k\) pursuers occupy the deletion set and an evader remains in the component selected by \(\beta\). Monotonicity guarantees that adding a pursuer narrows the safe region without forcing the evader to cross an occupied vertex.

For finite graphs the maximal haven order is exactly treewidth plus one: \(G\) has a haven of order \(k\) if and only if \(\operatorname{tw}(G)\ge k-1\). Touching havens are equivalent in order to brambles, families of connected subgraphs that pairwise touch and require at least \(k\) vertices to hit. Thus a haven is both a strategy certificate and a min–max obstruction to narrow tree decomposition. Infinite graphs require separate care: a ray induces a countable-order haven even though the ray has treewidth one, so the finite theorem cannot be transferred unchanged.^[1]^[2]

Structural Signature¶

Undirected graph. The carrier graph and its vertex set are fixed.
Order parameter. A cardinal or integer specifies which deletion sets are in scope.
Deletion-set domain. The function is defined for every vertex set of size below the order.
Flap codomain. Each output is a nonempty connected component of the graph after deleting that input set.
Component validity. The selected safe region contains no deleted vertex and is maximal connected in the remainder.
Monotone coherence. Under one standard convention, larger deletion sets yield nested selected flaps.
Touching coherence. Under the original convention, all selected flaps pairwise intersect or are joined by an edge.
Convention declaration. The theorem or application states which condition is used.
Evasion interpretation. The output identifies where an evader can remain against a bounded pursuer set.
Treewidth duality. In finite graphs, the largest order is treewidth plus one.
Bramble correspondence. A touching haven and a bramble yield one another at the same order.
Infinite-graph boundary. Rays, ends, and uncountable orders require distinct results and hypotheses.

What It Is Not¶

Not a vertex separator. A separator is one deletion set; a haven coherently answers every sufficiently small deletion set.
Not one connected component. Its output changes with the deleted set while satisfying a global constraint.
Not a tree decomposition. A tree decomposition certifies an upper bound; a haven certifies the complementary obstruction/lower bound.
Not a bramble. A bramble is a family of connected subgraphs; a haven is a function from deletion sets to flaps, though their orders correspond.
Not the graph's end in the finite case. Ends describe equivalence classes of rays in infinite graphs.
Not a safe vertex chosen independently at each move. Coherence across deletion sets is load-bearing.
Not the ordinary-language refuge. The term is a formal graph-theoretic homonym.
Not an unrestricted directed-graph notion. The core definition here uses undirected connectivity.

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\). Define the pursuit–evasion move rules before claiming a winning strategy. For infinite graphs, state cardinality, ray/end assumptions, and the exact theorem; do not reuse finite duality automatically.

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. Proofs must establish the function on every in-scope set.

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.
Convert the haven into a bramble, or construct it from a bramble, when useful.
Apply the finite min–max theorem to infer the exact treewidth lower bound with the correct offset.
Compare with a tree decomposition upper bound to pin down treewidth when available.
Rebuild the argument under ray/end/cardinal hypotheses before extending it to infinite graphs.

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.

Examples¶

Canonical¶

For the \(3\times3\) grid, define \(\beta(X)\) for every \(|X|<4\) by choosing the unique largest \(X\)-flap when it exists and resolving the remaining cases consistently toward the six-vertex side rather than an isolated corner. The selections can be shown monotone, yielding a haven of order four. No haven of order five exists, so the finite min–max theorem gives treewidth three.

Mapped back: all deletion sets of fewer than four vertices → coherently selected surviving grid component → order-four haven → treewidth lower bound three.

Applied / In Practice¶

Suppose an \(n\)-vertex graph has no separator of at most \(k\) vertices whose removal leaves every component with at most two-thirds of the vertices. For each deletion set \(X\) of size at most \(k\), choose the unique component larger than two-thirds of the graph. Two such large components must overlap appropriately, and the selection supplies a haven of order \(k+1\). This converts failure of balanced separation into a width certificate.^[3]

Mapped back: absence of small balanced separator → unique large flap after every small deletion → coherent haven → structural width/minor consequences.

Structural Tensions¶

Local component choice vs. global coherence. A plausible choice at each cut may fail collectively. Diagnostic: Is monotonicity or touching proved for every pair?
Monotone vs. touching definition. The conventions differ pointwise. Diagnostic: Which theorem licenses their finite order equivalence?
Lower-bound certificate vs. upper-bound decomposition. Havens and tree decompositions face opposite directions. Diagnostic: Is the order offset correct?
Strategy intuition vs. game specification. Capture power depends on movement rules. Diagnostic: Are pursuer and evader moves stated?
Finite duality vs. infinite behavior. Rays break naive treewidth correspondence. Diagnostic: Are cardinal and end hypotheses explicit?
Autonomous function vs. generic connectedness. Connectedness travels; the deletion-indexed coherent choice defines the residual. Diagnostic: Is the full function present?

Structural–Framed Character¶

The finite definition and min–max theorem are structural after graph, order, and convention are fixed. Choice of a convenient haven is proof-framed but constrained by totality and coherence. Game interpretations depend on precise rules. Infinite extensions are theorem-framed rather than automatic analogies. A haven certifies width and evasion structure; it does not by itself compute an optimal decomposition efficiently.

Structural Core vs. Domain Accent¶

The skeleton is a coherent function from disturbances to surviving regions. The domain accent is vertex deletion, connected components, order, monotonicity or touching, graph searching, brambles, and treewidth. Removing those yields Function Mapping, Robustness, or Connectedness rather than Haven.

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. Function Mapping spans domains far beyond graph deletion and adds none of the coherence or treewidth consequences.

The prospective workspace queue contains one strict upward edge to prime:function_mapping. No live DAG mutation is authorized.

Relationships to Other Abstractions¶

Current abstraction Haven (Graph Theory) Domain-specific

Parents (1) — more general patterns this builds on

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) → Function (Mapping)

Neighborhood in Abstraction Space¶

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

Family — Unclustered & Miscellaneous (1565 abstractions)

Nearest neighbors

Factor-critical graph — 0.83
Closure problem — 0.82
Clique graph — 0.82
Intersection number (graph theory) — 0.82
Reconstruction conjecture — 0.82

Computed from structural-signature embeddings · 2026-09-08

Not to Be Confused With¶

Bramble. A pairwise-touching family of connected subgraphs with an order defined by minimum hitting-set size.
Tree decomposition. A tree-indexed bag cover measuring graph width from above.
Treewidth. A numerical graph invariant characterized by maximal haven order minus one for finite graphs.
Tangle. An orientation of low-order separations toward a coherent highly connected region.
Vertex separator. A set whose deletion disconnects or balances a graph.
Graph end. An equivalence class of rays in an infinite graph.
Connected component. One output at one deletion set, not the haven function.

References¶

[1] P. D. Seymour and Robin Thomas, “Graph Searching and a Min-Max Theorem for Tree-Width,” Journal of Combinatorial Theory, Series B 58, no. 1 (1993): 22–33, https://doi.org/10.1006/jctb.1993.1027. registry ↩a ↩b

[2] Neil Robertson, Paul Seymour, and Robin Thomas, “Excluding Infinite Minors,” Discrete Mathematics 95, nos. 1–3 (1991): 303–319, https://doi.org/10.1016/0012-365X(91)90343-Z. registry ↩

[3] Noga Alon, Paul Seymour, and Robin Thomas, “A Separator Theorem for Nonplanar Graphs,” Journal of the American Mathematical Society 3, no. 4 (1990): 801–808, https://doi.org/10.1090/S0894-0347-1990-1065053-0. registry ↩