Treewidth–haven duality: large treewidth gives a haven
ProvedSeymourThomas1993.haven_of_not_treewidth_ledualitygraph-theorytreewidth
Let be a finite graph and an integer. If has no tree decomposition of width at most , then has a haven of order . Thus for every vertex set with one can choose a nonempty component of , such that every two chosen components touch. Tree decompositions have a finite nonempty tree, cover vertices and edges, satisfy the running-intersection property, and have bags of size at most . This is the large-treewidth direction of the treewidth/bramble min-max theorem, followed by the standard passage from a bramble to its haven.
Preamble
import Definitions.Def_DvorakNorin2018_HavenCloudConfiguration import Definitions.Def_RobertsonSeymour1986_GM5_TreewidthLE set_option autoImplicit false open StableMSR.Recovery.Havens RobertsonSeymour1986.GM5
Formal statement
namespace SeymourThomas1993
theorem haven_of_not_treewidth_le {V : Type} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (w : ℕ) (hwidth : ¬ TreewidthLE G w) :
∃ β : Finset V → Finset V, Haven G (w+2) β := by sorry
end SeymourThomas1993
Source
Seymour and Thomas, Graph searching and a min-max theorem for tree-width, J. Combin. Theory Ser. B 58 (1993), pp. 22-33. As stated and converted from brambles to havens in Dvorak--Norin, https://arxiv.org/pdf/1408.3869v2, Theorem 2 and the following two paragraphs, PDF p. 3.