Lemma 6: every bounded-congestion cloud admits tame normalization
ProvedDvorakNorin2018.tame_cloud_normalizationflowsgraph-theorytreewidth
Let be a finite undirected graph, let be a sink set, and let . If a -cloud has congestion at most and total supply exactly , then there exists an -tame -cloud with the same total supply. A tame cloud has no incoming flow at hungry vertices, at most one hungry predecessor at each saturated vertex, and, when , has zero edge flow with active vertex set exactly . This is the complete statement of Lemma 6, with source terminology specified by the imported definitions.
Preamble
import Definitions.Def_DvorakNorin2018_CloudNormalization set_option autoImplicit false open scoped Classical BigOperators open StableMSR.Recovery.TameCloud
Formal statement
namespace DvorakNorin2018
theorem tame_cloud_normalization {V : Type} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) (W : Finset V) (α s : ℝ) (hα : 0 < α) (hs : 0 < s)
(p : Data V) (hp : Cloud G W α p) (ht : total p = s) :
∃ q : Data V, Cloud G W α q ∧ Tame W α q ∧ total q = s := by sorry
end DvorakNorin2018
Source
Dvorak–Norin, Treewidth of graphs with balanced separations, https://arxiv.org/pdf/1408.3869v2, Section 2.2, definitions preceding Lemma 6 and its proof (PDF pp. 5–6).