Balanced separators bound haven order by 15a
ProvedDvorakNorin2018.haven_order_boundflowsgraph-theorytreewidth
Let be a finite graph and let be an integer. Suppose every induced subgraph of has a balanced separation of order at most : in a partition into exclusive parts with no edge from to , one has and . Then every haven of has order at most . A haven of order chooses a nonempty component of for every , and any two chosen components touch. This is the haven-order conclusion obtained by the complete tame-cloud counting contradiction in the proof of Dvorak--Norin Theorem 1. The separate treewidth/bramble duality converts this to the treewidth bound; that duality is not an assumption or conclusion of this theorem.
Preamble
import Definitions.Def_DvorakNorin2018_HavenCloudConfiguration set_option autoImplicit false open StableMSR.Recovery.Havens
Formal statement
namespace DvorakNorin2018
theorem haven_order_bound {V : Type} [Fintype V] [DecidableEq V]
{G : SimpleGraph V} {a k : ℕ} {β : Finset V → Finset V}
(hβ : Haven G k β) (hsep : HasBalancedSeparations G a) (ha : 1 ≤ a) : k ≤ 15*a := by sorry
end DvorakNorin2018
Source
Dvorak and Norin, Treewidth of graphs with balanced separations, https://arxiv.org/pdf/1408.3869v2, Lemma 7 and Section 3, proof of Theorem 1, PDF pp. 6-9.