Theorem 1: balanced separators bound treewidth by 15a
ProvedDvorakNorin2018.balanced_separators_treewidthgraph-theorytreewidth
Let be a finite graph and let be an integer. Suppose every induced subgraph has a separation into three disjoint parts with no edge from to , with and . Then has treewidth at most : there exists a finite tree decomposition in which every bag has size at most . This is the balanced-separator theorem needed to convert the clustering interaction graph separator estimates into a tree decomposition. The zero-parameter and empty-graph cases are included.
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 DvorakNorin2018
theorem balanced_separators_treewidth {V : Type} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (a : ℕ) (hsep : HasBalancedSeparations G a) :
TreewidthLE G (15*a) := by sorry
end DvorakNorin2018
Source
Dvorak and Norin, Treewidth of graphs with balanced separations, https://arxiv.org/pdf/1408.3869v2, Theorem 1 (PDF p. 2), with proof in Section 3, PDF pp. 8-9. Using every induced subgraph is equivalent here to every subgraph, since deleting edges preserves separators.