Lemma 7 core: a haven yields the large tame cloud and balanced separation
ProvedDvorakNorin2018.haven_cloud_balanced_configurationLet be a finite graph, let , and suppose that every induced subgraph has a balanced separation of order at most . Let be a haven of order . Then there is a lexicographically minimum deletion set of size , a vertex set , and a tame -cloud on , of congestion at most and total supply greater than . The set consists exactly of its hungry or saturated vertices; all supply and incoming and outgoing flow vanish outside . Moreover, , , and is a separation of the induced graph on with intersection . There is a balanced three-part separation of this induced graph, with , satisfying
Here balanced means . In full-side notation , , the last inequality is precisely . This is the haven-based core of Dvorak--Norin Lemma 7, after obtaining the haven; the treewidth-to-haven duality is a separate dependency and is not asserted here.
import Definitions.Def_DvorakNorin2018_HavenCloudConfiguration set_option autoImplicit false open scoped Classical BigOperators open TreewidthApprox.Pushed StableMSR.Recovery StableMSR.Recovery.Havens
namespace DvorakNorin2018
theorem haven_cloud_balanced_configuration {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) (hk : 15*a < k) :
∃ (W X : Finset V) (p : TameCloud.Data V), IsMinimumCut β (14*a) W ∧
W.card = 14*a ∧ W ⊆ X ∧ Disjoint X (β W) ∧ X = activeVertices W p ∧
X ∩ (W ∪ β W) = W ∧ (W ∪ β W) \ W = β W ∧
IsPartition3 (X ∪ β W) (X \ W) W (β W) ∧ NoEdge G (X \ W) (β W) ∧
TameCloud.Cloud (outsideGraph G (β W)) W (14*(β W).card/(7*(a : ℝ))) p ∧
TameCloud.Tame W (14*(β W).card/(7*(a : ℝ))) p ∧
14*((β W).card : ℝ) < TameCloud.total p ∧
(∀ v ∉ X, p.1 v = 0 ∧ (∀ u, p.2 (u,v) = 0) ∧ ∀ u, p.2 (v,u) = 0) ∧
∃ L S R : Finset V, IsPartition3 (X ∪ β W) L S R ∧ NoEdge G L R ∧
S.card ≤ a ∧ 3*L.card ≤ 2*(X ∪ β W).card ∧
3*R.card ≤ 2*(X ∪ β W).card ∧ ((L ∩ W) ∪ (S ∩ X)).card ≤ a := by sorry
end DvorakNorin2018