Introduction
Multiway Cut is the problem of separating k k k G = ( V , E ) G=(V,E) G = ( V , E ) w u v w_{uv} w uv k k k t 1 , … , t k ∈ V t_1,\ldots,t_k\in V t 1 , … , t k ∈ V k k k C : V → [ k ] C:V\to[k] C : V → [ k ] C ( t i ) = i C(t_i)=i C ( t i ) = i i ∈ [ k ] i\in[k] i ∈ [ k ]
cost ( C ) = ∑ u v ∈ E w u v 1 [ C ( u ) ≠ C ( v ) ] . (1) \operatorname{cost}(C)=\sum_{uv\in E}w_{uv}\,1[C(u)\ne C(v)]. \tag*{(1)} cost ( C ) = uv ∈ E ∑ w uv 1 [ C ( u ) = C ( v )] . (1) We write OPT for the minimum cost of a k k k
When k = 2 k=2 k = 2 s s s t t t [12 , 13 ] showed that the problem is APX-hard for every fixed k ≥ 3 k\ge3 k ≥ 3 ( 2 − 2 / k ) (2-2/k) ( 2 − 2/ k ) [10 ] , who introduced a geometric approach to Multiway Cut based on linear programming. Their relaxation, now commonly known as the CKR relaxation, is defined as follows:
minimize ∑ u v ∈ E w u v d ( x u , x v ) subject to x u ∈ Δ k for every u ∈ V , x t i = e i for every i ∈ [ k ] . (2) \begin{aligned}
\text{minimize}\quad&\sum_{uv\in E}w_{uv}d(x^u,x^v)\\
\text{subject to}\quad&x^u\in\Delta_k &&\text{for every }u\in V,\\
&x^{t_i}=e_i &&\text{for every }i\in[k]. \tag*{(2)}
\end{aligned} minimize subject to uv ∈ E ∑ w uv d ( x u , x v ) x u ∈ Δ k x t i = e i for every u ∈ V , for every i ∈ [ k ] . (2) Here Δ k = { x ∈ R ≥ 0 k : x 1 + ⋯ + x k = 1 } \Delta_k=\{x\in\mathbb{R}_{\ge0}^k:x_1+\cdots+x_k=1\} Δ k = { x ∈ R ≥ 0 k : x 1 + ⋯ + x k = 1 } e i e_i e i i i i ℓ 1 \ell_1 ℓ 1 1 / 2 1/2 1/2 d ( x , y ) = 1 2 ∥ x − y ∥ 1 d(x,y)=\frac{1}{2}\lVert x-y\rVert_1 d ( x , y ) = 2 1 ∥ x − y ∥ 1 k k k C C C x u = e C ( u ) x^u=e_{C(u)} x u = e C ( u ) (2) is at most OPT. Călinescu, Karloff, and Rabani rounded their relaxation to obtain a ( 3 / 2 − 1 / k ) (3/2 - 1/k) ( 3/2 − 1/ k ) [15 , 6 , 18 , 4 ] . In particular, Karger, Klein, Stein, Thorup, and Young [15 ] settled the case of k = 3 k = 3 k = 3 12 / 11 12/11 12/11 1.3438 1.3438 1.3438 k k k [6 ] introduced the method of exponential clocks and designed a rounding scheme with ratio 1.3239 1.3239 1.3239 [18 ] obtain a 1.2965 1.2965 1.2965 [8 ] gave a simpler rounding scheme nearly matching the approximation guarantee of [18 ] . The current best approximation ratio for large k k k 1.2787 1.2787 1.2787 [4 ] .
Recall that the integrality gap of an instance is the ratio OPT/LP. Let G k G_k G k k k k [17 ] showed that, assuming the Unique Games Conjecture, the best approximation ratio achievable in polynomial time for Minimum Multiway Cut with k k k G k G_k G k
Compared to algorithmic results, lower bounds on the integrality gap are much less developed. The gap is known exactly only for k = 3 k = 3 k = 3 12 / 11 12/11 12/11 [15 , 11 ] . For general k k k Δ k \Delta_k Δ k d d d d d d Δ k \Delta_k Δ k d + 1 d + 1 d + 1 [14 ] analyzed the one-dimensional skeleton and gave an asymptotic lower bound of 8 / 7 8/7 8/7 [2 ] introduced the technique of non-opposite cuts, which makes it possible to analyze a low-dimensional skeleton of Δ k \Delta_k Δ k 1.2 1.2 1.2 1.20016 1.20016 1.20016 [3 ] .
Our contribution. We obtain the following asymptotic lower bound on the integrality gap for large k k k
Theorem 1.1. Let G k G_k G k (2) over all instances with k k k 3
lim k → ∞ G k ≥ 159389999561650025 129321858575204877 > 1.2325. \lim_{k \to\infty} G_k \ge\frac{159389999561650025}{129321858575204877} > 1.2325. k → ∞ lim G k ≥ 129321858575204877 159389999561650025 > 1.2325. Equivalently, for every η > 0 \eta> 0 η > 0 k k k k k k η \eta η
This result combined with the hardness result of [17 ] , immediately yields the following corollary.
Corollary 1.2. Assuming the Unique Games Conjecture, for every ϵ > 0 \epsilon> 0 ϵ > 0 k k k k k k 1.2325 − ϵ 1.2325 - \epsilon 1.2325 − ϵ
The gap in Theorem 1.1 is in part obtained with a computer-assisted search via linear programming. However, we can get the slightly weaker gap of 1.22376 1.22376 1.22376 Theorem 3.5 ). This is still better than the previous best lower bound of 1.20016 1.20016 1.20016 [3 ] .
Our approach. A rounding scheme for (2) is a random k k k [15 ] the gap G k G_k G k k k k Δ k \Delta_k Δ k k k k [2 ] and restrict the cut to a face with a fixed number q q q k k k non-opposite cut of Δ q \Delta_q Δ q ∗ \ast ∗ ∗ \ast ∗ Δ q \Delta_q Δ q lim k → ∞ G k \lim_{k\to\infty} G_k lim k → ∞ G k
On the faces of Δ q \Delta_q Δ q
Hence, a random non-opposite cut with finite approximation factor costs, in expectation, nearly as much as the cut that labels every point by ∗ \ast ∗ Theorem 3.4 ). We prove this for every q q q Theorems 1.1 and 3.5 is a single flow instance, on Δ 11 \Delta_{11} Δ 11 Δ 10 \Delta_{10} Δ 10
Roadmap. We introduce the notion of label flows and give an overview of our approach in § 3 . In § 4 we exhibit a flow instance for q = 3 q=3 q = 3 § 5 proves the lower bound formally. § 6 and § 7 give the two flow instances on Δ 10 \Delta_{10} Δ 10 Δ 11 \Delta_{11} Δ 11
Preliminaries on Non-Opposite Cuts
In this section we give an overview of the non-opposite cuts of [2 ] , and explain why we can restrict our attention to them.
A solution of (2) places each vertex u u u x u ∈ Δ k x^u\in\Delta_k x u ∈ Δ k k k k C : Δ k → [ k ] C:\Delta_k\to[k] C : Δ k → [ k ] C ( e i ) = i C(e_i)=i C ( e i ) = i i ∈ [ k ] i\in[k] i ∈ [ k ] u u u C ( x u ) C(x^u) C ( x u ) approximation factor α \alpha α
P [ C ( x ) ≠ C ( y ) ] ≤ α d ( x , y ) for all x , y ∈ Δ k . (3) \mathbb{P}[C(x)\ne C(y)]\le\alpha d(x,y)\quad\text{for all }x,y\in\Delta_k. \tag*{(3)} P [ C ( x ) = C ( y )] ≤ α d ( x , y ) for all x , y ∈ Δ k . (3) Then every edge u v uv uv α d ( x u , x v ) \alpha d(x^u,x^v) α d ( x u , x v ) α \alpha α G k ≤ α G_k\le\alpha G k ≤ α [15 ] showed that some random k k k Δ k \Delta_k Δ k G k G_k G k
To remove the dependence on k k k [2 Lemma 13 of full version] restrict the cut to the face spanned by q q q Δ q \Delta_q Δ q ∗ \ast ∗ ∗ \ast ∗ ∗ \ast ∗ x x x supp ( x ) = { i : x i > 0 } \operatorname{supp}(x)=\{i:x_i>0\} supp ( x ) = { i : x i > 0 } ∗ \ast ∗ k → ∞ k\to\infty k → ∞
Definition 2.1 (Non-opposite cuts). A non-opposite cut of Δ q \Delta_q Δ q C : Δ q → [ q ] ∪ { ∗ } C:\Delta_q\to[q]\cup\{\ast\} C : Δ q → [ q ] ∪ { ∗ } C ( e i ) = i C(e_i)=i C ( e i ) = i i ∈ [ q ] i\in[q] i ∈ [ q ] C ( x ) ∈ supp ( x ) ∪ { ∗ } C(x)\in\operatorname{supp}(x)\cup\{\ast\} C ( x ) ∈ supp ( x ) ∪ { ∗ } x ∈ Δ q x\in\Delta_q x ∈ Δ q random non-opposite cut is a probability distribution over non-opposite cuts.
For example, the side x 1 = 0 x_1=0 x 1 = 0 Δ 3 \Delta_3 Δ 3 2 2 2 3 3 3 ∗ \ast ∗ 1 1 1 e 1 e_1 e 1 Δ q \Delta_q Δ q Δ k \Delta_k Δ k k → ∞ k \to\infty k → ∞
Lemma 2.2 (Non-opposite reduction). Fix q ≥ 2 q \ge2 q ≥ 2 β > 0 \beta> 0 β > 0 Δ q \Delta_q Δ q α \alpha α α ≥ β \alpha\ge\beta α ≥ β lim k → ∞ G k ≥ β \lim_{k\to\infty} G_k \ge\beta lim k → ∞ G k ≥ β η > 0 \eta> 0 η > 0 k k k k k k β − η \beta- \eta β − η
Technical Overview of the Approach
By Lemma 2.2 , it suffices to fix q q q Δ q \Delta_q Δ q β \beta β q q q Theorem 1.1 is the case q = 11 q = 11 q = 11
Let C C C Δ q \Delta_q Δ q α \alpha α Δ q \Delta_q Δ q e 1 , … , e q e_1,\ldots,e_q e 1 , … , e q C C C d d d α d \alpha d α d C C C α L \alpha L α L L L L C C C M M M α ≥ M / L \alpha\ge M/L α ≥ M / L M M M M / L M/L M / L flow instance .
A flow instance determines three quantities: (1) L L L B B B ∗ \ast ∗ R R R Theorem 3.4 , states that every random non-opposite cut of Δ q \Delta_q Δ q α \alpha α B − R ≤ E [ cost ( C ) ] ≤ α L B-R \le\mathbb{E}[\operatorname{cost}(C)] \le\alpha L B − R ≤ E [ cost ( C )] ≤ α L α ≥ ( B − R ) / L \alpha\ge(B-R)/L α ≥ ( B − R ) / L ∗ \ast ∗ § 3.1 ), where the argument cannot give a bound above one, because it also applies to the fractional solution. We then move to the faces of the simplex (§ 3.2 ), where it can. Finally, we state Theorem 3.4 and reduce it to three lemmas (§ 3.3 ), and describe the two flow instances behind Theorems 1.1 and 3.5 (§ 3.4 ).
Flow Instances on a Graph
Let H H H Δ q \Delta_q Δ q w u v ≥ 0 w_{uv} \ge0 w uv ≥ 0 v v v g v , i ≥ 0 g_{v,i} \ge0 g v , i ≥ 0 e i e_i e i i ∈ supp ( v ) i \in\operatorname{supp}(v) i ∈ supp ( v ) C C C Δ q \Delta_q Δ q v v v A ( v ) = supp ( v ) ∪ { ∗ } A(v) = \operatorname{supp}(v) \cup\{\ast\} A ( v ) = supp ( v ) ∪ { ∗ } allowed at v v v i ∉ A ( v ) i \notin A(v) i ∈ / A ( v ) v i = 0 v_i = 0 v i = 0 forbidden at v v v C C C
cost ( C ) = ∑ u , v w u v 1 [ C ( u ) ≠ C ( v ) ] + ∑ v , i g v , i 1 [ C ( v ) ≠ i ] . (4) \operatorname{cost}(C) = \sum_{u,v} w_{uv}\mathbf{1}[C(u) \ne C(v)] + \sum_{v,i} g_{v,i}\mathbf{1}[C(v) \ne i]. \tag*{(4)} cost ( C ) = u , v ∑ w uv 1 [ C ( u ) = C ( v )] + v , i ∑ g v , i 1 [ C ( v ) = i ] . (4) Labeling every vertex of H H H ∗ \ast ∗ B = ∑ v , i g v , i B = \sum_{v,i} g_{v,i} B = ∑ v , i g v , i H H H L = ∑ u v w u v d ( u , v ) + ∑ v , i g v , i ( 1 − v i ) L = \sum_{uv} w_{uv}d(u,v) + \sum_{v,i} g_{v,i}(1-v_i) L = ∑ uv w uv d ( u , v ) + ∑ v , i g v , i ( 1 − v i ) ℓ \ell ℓ φ ℓ \varphi_\ell φ ℓ H H H φ ℓ ( v → u ) = − φ ℓ ( u → v ) \varphi_\ell(v \to u) = -\varphi_\ell(u \to v) φ ℓ ( v → u ) = − φ ℓ ( u → v ) φ ∗ = 0 \varphi_\ast= 0 φ ∗ = 0 in ℓ ( v ) \operatorname{in}_\ell(v) in ℓ ( v ) φ ℓ \varphi_\ell φ ℓ v v v
We say that label flows together with allowances ϵ v ≥ 0 \epsilon_v \ge0 ϵ v ≥ 0 flow instance on H H H
(Capacity ) On every edge u v uv uv
∣ φ ℓ ( u → v ) − φ m ( u → v ) ∣ ≤ w u v for all ℓ , m ∈ A ( u ) ∪ A ( v ) . (5) \lvert\varphi_\ell(u \to v) - \varphi_m(u \to v)\rvert\le w_{uv}\quad\text{for all }\ell,m \in A(u) \cup A(v). \tag*{(5)} ∣ φ ℓ ( u → v ) − φ m ( u → v )∣ ≤ w uv for all ℓ , m ∈ A ( u ) ∪ A ( v ) . (5) (Conservation) At every vertex v v v ℓ ∈ A ( v ) \ell\in A(v) ℓ ∈ A ( v ) in ℓ ( v ) ≥ g v , ℓ − ϵ v \operatorname{in}_{\ell}(v) \ge g_{v,\ell} - \epsilon_v in ℓ ( v ) ≥ g v , ℓ − ϵ v R = ∑ v ϵ v R = \sum_v \epsilon_v R = ∑ v ϵ v
Lemma 3.1 (Flow lower bound on a graph). Every non-opposite cut of H H H B − R B - R B − R L > 0 L > 0 L > 0 Δ q \Delta_q Δ q α \alpha α α ≥ ( B − R ) / L \alpha\ge(B - R)/L α ≥ ( B − R ) / L
Summing the inflow of the label C ( v ) C(v) C ( v ) v v v C C C R R R v v v i i i v i v_i v i L L L
Proposition 3.2. Every flow instance on a finite graph has B − R ≤ L B - R \le L B − R ≤ L ( B − R ) / L ≤ 1 (B - R)/L \le1 ( B − R ) / L ≤ 1 α ≥ ( B − R ) / L \alpha\ge(B - R)/L α ≥ ( B − R ) / L α ≥ 1 \alpha\ge1 α ≥ 1
We prove Lemma 3.1 and Proposition 3.2 in Section B.
Flow Instances on the Simplex
We replace the finite graph by the truncated faces of Δ q \Delta_q Δ q
Fix a threshold T ∈ ( 1 / 2 , 1 ) T \in(1/2, 1) T ∈ ( 1/2 , 1 ) S ⊆ [ q ] S \subseteq[q] S ⊆ [ q ] ∣ S ∣ ≥ 2 |S| \ge2 ∣ S ∣ ≥ 2 Δ S = { x ∈ Δ q : supp ( x ) ⊆ S } \Delta_S = \{x \in\Delta_q : \operatorname{supp}(x) \subseteq S\} Δ S = { x ∈ Δ q : supp ( x ) ⊆ S } Δ q \Delta_q Δ q e i e_i e i i ∈ S i \in S i ∈ S Ω S = { x ∈ Δ S : max i ∈ S x i ≤ T } \Omega_S = \{x \in\Delta_S : \max_{i \in S} x_i \le T\} Ω S = { x ∈ Δ S : max i ∈ S x i ≤ T } truncated face for S S S Ω S \Omega_S Ω S terminal facet Φ i S = { x ∈ Ω S : x i = T } \Phi_i^S = \{x \in\Omega_S : x_i = T\} Φ i S = { x ∈ Ω S : x i = T } i ∈ S i \in S i ∈ S i i i Ω S \Omega_S Ω S e i e_i e i ∣ S ∣ ≥ 3 |S| \ge3 ∣ S ∣ ≥ 3 coordinate facet { x ∈ Ω S : x j = 0 } \{x \in\Omega_S : x_j = 0\} { x ∈ Ω S : x j = 0 } j ∈ S j \in S j ∈ S Ω S ∖ { j } \Omega_{S\setminus\{j\}} Ω S ∖ { j }
A weighting of Δ q \Delta_q Δ q w i j S : Ω S → R ≥ 0 w_{ij}^S : \Omega_S \to\mathbb{R}_{\ge0} w ij S : Ω S → R ≥ 0 S S S i < j i < j i < j S S S g i S : Φ i S → R ≥ 0 g_i^S : \Phi_i^S \to\mathbb{R}_{\ge0} g i S : Φ i S → R ≥ 0 S S S i ∈ S i \in S i ∈ S H H H Ω S \Omega_S Ω S e i − e j e_i - e_j e i − e j w i j S w_{ij}^S w ij S y ∈ Φ i S y \in\Phi_i^S y ∈ Φ i S e i e_i e i d ( y , e i ) = 1 − T d(y,e_i) = 1 - T d ( y , e i ) = 1 − T g i S g_i^S g i S Figure 1 a shows the case q = 3 q = 3 q = 3 Ω [ 3 ] \Omega_{[3]} Ω [ 3 ] Ω { i , j } \Omega_{\{i,j\}} Ω { i , j } x i > T x_i > T x i > T
Figure 1. The geometry and a cut for q = 3 q = 3 q = 3
Restricted to Ω S \Omega_S Ω S C C C Δ q \Delta_q Δ q S ∪ { ∗ } S \cup\{*\} S ∪ { ∗ } allowed on Ω S \Omega_S Ω S j ∉ S j \notin S j ∈ / S forbidden on Ω S \Omega_S Ω S j j j x j = 0 x_j = 0 x j = 0 Δ q \Delta_q Δ q x j = 0 x_j = 0 x j = 0 Ω S \Omega_S Ω S Ω S ∖ { j } \Omega_{S\setminus\{j\}} Ω S ∖ { j }
cost ( C ) = ∑ S ∑ i < j ∫ Ω S w i j S d μ i j S ( C ) + ∑ S ∑ i ∈ S ∫ Φ i S g i S ( y ) 1 [ C ( y ) ≠ i ] d σ ( y ) . (6) \operatorname{cost}(C) = \sum_S \sum_{i<j} \int_{\Omega_S} w_{ij}^S \, \mathrm{d}\mu_{ij}^S(C) + \sum_S \sum_{i \in S} \int_{\Phi_i^S} g_i^S(y) \mathbf{1}[C(y) \ne i] \, \mathrm{d}\sigma(y). \tag*{(6)} cost ( C ) = S ∑ i < j ∑ ∫ Ω S w ij S d μ ij S ( C ) + S ∑ i ∈ S ∑ ∫ Φ i S g i S ( y ) 1 [ C ( y ) = i ] d σ ( y ) . (6) where the crossing measure μ i j S ( C ) ( A ) \mu_{ij}^{S}(C)(A) μ ij S ( C ) ( A ) A ⊆ Ω S A \subseteq\Omega_S A ⊆ Ω S C C C e i − e j e_i-e_j e i − e j A A A Lemma 5.3 computes it for a cut whose label regions, the sets on which the cut takes one label, are polytopes, and § 5.3 makes it precise for measurable C C C ∗ \ast ∗
B = ∑ S ∑ i ∈ S ∫ Φ i S g i S ( y ) d σ ( y ) , (7) B = \sum_S \sum_{i\in S} \int_{\Phi_i^S} g_i^S(y)\,\mathrm{d}\sigma(y), \tag*{(7)} B = S ∑ i ∈ S ∑ ∫ Φ i S g i S ( y ) d σ ( y ) , (7) and the solution of (2) that places every point at itself has the fractional cost
L = ∑ S ∑ i < j ∫ Ω S w i j S ( x ) d x + ( 1 − T ) B . (8) L = \sum_S \sum_{i<j} \int_{\Omega_S} w_{ij}^S(x)\,\mathrm{d}x + (1-T)B. \tag*{(8)} L = S ∑ i < j ∑ ∫ Ω S w ij S ( x ) d x + ( 1 − T ) B . (8) For every S S S ℓ ∈ S ∪ { ∗ } \ell\in S \cup\{\ast\} ℓ ∈ S ∪ { ∗ } label flow is a vector field F ℓ S F_\ell^S F ℓ S Ω S \Omega_S Ω S F ∗ S = 0 F_\ast^S = 0 F ∗ S = 0 φ ℓ \varphi_\ell φ ℓ F ℓ S F_\ell^S F ℓ S φ ℓ ( u → v ) \varphi_\ell(u \to v) φ ℓ ( u → v ) − div F ℓ S -\operatorname{div} F_\ell^S − div F ℓ S in ℓ ( v ) \operatorname{in}_\ell(v) in ℓ ( v ) Ω S \Omega_S Ω S F ℓ S F_\ell^S F ℓ S normal continuity , and make it precise in § 5.1 . The flow leaving Ω S \Omega_S Ω S x j = 0 x_j = 0 x j = 0 − F ℓ , j S -F_{\ell,j}^S − F ℓ , j S Φ i S \Phi_i^S Φ i S F ℓ , i S F_{\ell,i}^S F ℓ , i S Ω S \Omega_S Ω S
What a label flow does. The flow of label j j j Ω S \Omega_S Ω S x j = 0 x_j = 0 x j = 0 j j j Φ j S \Phi_j^S Φ j S g j S g_j^S g j S x i = 0 x_i = 0 x i = 0 j j j C ( y ) = j C(y) = j C ( y ) = j Φ j S \Phi_j^S Φ j S j j j x j = 0 x_j = 0 x j = 0 j j j Figure 1 b). The three conditions below make this precise.
Definition 3.3 (Flow instance on the simplex). A flow instance on Δ q \Delta_q Δ q F ℓ S F_\ell^S F ℓ S S ⊆ [ q ] S \subseteq[q] S ⊆ [ q ] ∣ S ∣ ≥ 2 |S| \ge2 ∣ S ∣ ≥ 2 ℓ ∈ S ∪ { ∗ } \ell\in S \cup\{\ast\} ℓ ∈ S ∪ { ∗ } ϵ S : Ω S → R ≥ 0 \epsilon_S : \Omega_S \to\mathbb{R}_{\ge0} ϵ S : Ω S → R ≥ 0 S S S S S S
(Capacity) Summed over any set of coordinates I I I e i − e j e_i-e_j e i − e j i ∈ I i \in I i ∈ I j ∉ I j \notin I j ∈ / I x x x Ω S \Omega_S Ω S ℓ , m ∈ S ∪ { ∗ } \ell,m \in S \cup\{\ast\} ℓ , m ∈ S ∪ { ∗ } I ⊂ S I \subset S I ⊂ S
∣ ∑ i ∈ I ( F ℓ , i S ( x ) − F m , i S ( x ) ) ∣ ≤ ∑ i ∈ I , j ∈ S ∖ I w i j S ( x ) . (9) \left|\sum_{i\in I}\left(F_{\ell,i}^S(x)-F_{m,i}^S(x)\right)\right| \le\sum_{i\in I,\,j\in S\setminus I}w_{ij}^S(x). \tag*{(9)} i ∈ I ∑ ( F ℓ , i S ( x ) − F m , i S ( x ) ) ≤ i ∈ I , j ∈ S ∖ I ∑ w ij S ( x ) . (9) (Terminal condition) Through the terminal facet Φ i S \Phi_i^S Φ i S i i i F ℓ , i S = g i S 1 [ ℓ = i ] F_{\ell,i}^S=g_i^S\mathbf{1}[\ell=i] F ℓ , i S = g i S 1 [ ℓ = i ] Φ i S \Phi_i^S Φ i S i ∈ S i \in S i ∈ S ℓ \ell ℓ
(Conservation) On Ω S \Omega_S Ω S ℓ ∈ S ∪ { ∗ } \ell\in S \cup\{\ast\} ℓ ∈ S ∪ { ∗ }
div F ℓ S ≤ − ∑ j ∉ S F ℓ , j S ∪ { j } + ϵ S . (10) \operatorname{div} F_\ell^S \le-\sum_{j\notin S}F_{\ell,j}^{S\cup\{j\}}+\epsilon_S. \tag*{(10)} div F ℓ S ≤ − j ∈ / S ∑ F ℓ , j S ∪ { j } + ϵ S . (10) We use R = ∑ S ∫ Ω S ϵ S d x R=\sum_S\int_{\Omega_S}\epsilon_S\,\mathrm{d}x R = ∑ S ∫ Ω S ϵ S d x ( B − R ) / L (B-R)/L ( B − R ) / L
The Main Technical Result
Theorem 3.4 (Flow lower bound). Let a flow instance on Δ q \Delta_q Δ q L > 0 L>0 L > 0 C C C Δ q \Delta_q Δ q α \alpha α
B − R ≤ E [ cost ( C ) ] ≤ α L . B-R \le\mathbb{E}[\operatorname{cost}(C)] \le\alpha L. B − R ≤ E [ cost ( C )] ≤ α L . Consequently, α ≥ ( B − R ) / L \alpha\ge(B-R)/L α ≥ ( B − R ) / L lim k → ∞ G k ≥ ( B − R ) / L \lim_{k\to\infty}G_k \ge(B-R)/L lim k → ∞ G k ≥ ( B − R ) / L
We rewrite the cost ((5)) as cost ( C ) = ∑ S cost S ( C ) + cost t e r m ( C ) \operatorname{cost}(C)=\sum_S\operatorname{cost}_S(C)+\operatorname{cost}_{\mathrm{term}}(C) cost ( C ) = ∑ S cost S ( C ) + cost term ( C ) cost S ( C ) \operatorname{cost}_S(C) cost S ( C ) Ω S \Omega_S Ω S cost t e r m ( C ) \operatorname{cost}_{\mathrm{term}}(C) cost term ( C ) x x x Ω S \Omega_S Ω S F C ( x ) S ( x ) F_{C(x)}^S(x) F C ( x ) S ( x ) C C C flux jump Λ S ( C ) \Lambda_S(C) Λ S ( C ) Ω S \Omega_S Ω S
Λ S ( C ) = ∑ i ∈ S ∫ Φ i S F C ( y ) , i S ( y ) d σ ( y ) − ∑ j ∈ S ∫ Ω S ∖ { j } F C ( x ) , j S ( x ) d x − ∫ Ω S div F C ( x ) S ( x ) d x . (11) \Lambda_S(C)=\sum_{i\in S}\int_{\Phi_i^S}F_{C(y),i}^S(y)\,\mathrm{d}\sigma(y)-\sum_{j\in S}\int_{\Omega_{S\setminus\{j\}}}F_{C(x),j}^S(x)\,\mathrm{d}x-\int_{\Omega_S}\operatorname{div}F_{C(x)}^S(x)\,\mathrm{d}x. \tag*{(11)} Λ S ( C ) = i ∈ S ∑ ∫ Φ i S F C ( y ) , i S ( y ) d σ ( y ) − j ∈ S ∑ ∫ Ω S ∖ { j } F C ( x ) , j S ( x ) d x − ∫ Ω S div F C ( x ) S ( x ) d x . (11) where div F C ( x ) S ( x ) \operatorname{div}F_{C(x)}^S(x) div F C ( x ) S ( x ) x x x F ℓ S F_\ell^S F ℓ S ℓ = C ( x ) \ell=C(x) ℓ = C ( x ) C C C ∣ S ∣ = 2 |S|=2 ∣ S ∣ = 2 C C C Ω S \Omega_S Ω S Λ S ( C ) = 0 \Lambda_S(C)=0 Λ S ( C ) = 0 Λ S ( C ) \Lambda_S(C) Λ S ( C )
Proof of Theorem 3.4 , assuming Lemmas 5.2 , 5.9 and 5.10 . Let C C C Δ q \Delta_q Δ q α \alpha α Λ S ( C ) \Lambda_S(C) Λ S ( C ) cost t e r m ( C ) \operatorname{cost}_{\mathrm{term}}(C) cost term ( C )
B − R ≤ ∑ S E [ Λ S ( C ) ] + E [ cost t e r m ( C ) ] (Lemma 5.2, for every realization of C ) ≤ ∑ S E [ cost S ( C ) ] + E [ cost t e r m ( C ) ] = E [ cost ( C ) ] (Lemma 5.9, on every face) ≤ α L (Lemma 5.10). \begin{aligned}
B-R &\le\sum_S \mathbb{E}[\Lambda_S(C)] + \mathbb{E}[\operatorname{cost}_{\mathrm{term}}(C)] &&\text{(Lemma 5.2, for every realization of } C\text{)}\\
&\le\sum_S \mathbb{E}[\operatorname{cost}_S(C)] + \mathbb{E}[\operatorname{cost}_{\mathrm{term}}(C)] = \mathbb{E}[\operatorname{cost}(C)] &&\text{(Lemma 5.9, on every face)}\\
&\le\alpha L &&\text{(Lemma 5.10).}
\end{aligned} B − R ≤ S ∑ E [ Λ S ( C )] + E [ cost term ( C )] ≤ S ∑ E [ cost S ( C )] + E [ cost term ( C )] = E [ cost ( C )] ≤ α L (Lemma 5.2, for every realization of C ) (Lemma 5.9, on every face) (Lemma 5.10). Dividing by L > 0 L>0 L > 0 α ≥ ( B − R ) / L \alpha\ge(B-R)/L α ≥ ( B − R ) / L B − R ≤ 0 B-R\le0 B − R ≤ 0 lim k → ∞ G k ≥ ( B − R ) / L \lim_{k\to\infty}G_k\ge(B-R)/L lim k → ∞ G k ≥ ( B − R ) / L G k ≥ 1 G_k\ge1 G k ≥ 1 Lemma 2.2 with β = ( B − R ) / L \beta=(B-R)/L β = ( B − R ) / L
We now explain intuitively why the three inequalities hold, and defer formal proofs to § 5 . The first inequality holds for every cut and uses only the terminal condition and conservation. By the terminal condition, the selected flow leaving through the terminal facets has the weight of the terminal edges that C C C R R R B − R B-R B − R
The second inequality uses the geometry of the cut, and unlike the first, it holds only in expectation. We call the surfaces where the label of C C C interfaces . At an interface the selected flow jumps from one label flow to another, and capacity says that the cost of the interface is at least this jump, so the flux jump of a face is at most its cost. When the label regions are polytopes, this follows from the divergence theorem applied to each region (Lemma 5.3 ). A measurable cut need not have interfaces in any usable sense, and this is where the approximation factor enters. It implies that the label regions have finite perimeter almost surely (Lemma 5.6 ), so that their interfaces form a surface of finite area along which exactly two labels meet almost everywhere (Fact 5.7 ), and it recovers in expectation the labels on the boundary of a face from the labels nearby (Lemma 5.8 ).
The third inequality is the approximation factor applied edge by edge to the weighting.
Two Flow Instances
The simplest flow instances have constant weights and affine label flows on every face, i.e., on every face the flow of label i i i e i e_i e i x x x B B B R R R L L L q q q T T T q = 10 q=10 q = 10 T = 3 / 5 T=3/5 T = 3/5
Theorem 3.5 (Explicit flow instance). There is a flow instance on Δ 10 \Delta_{10} Δ 10 T = 3 / 5 T=3/5 T = 3/5
B − R L = 9999320418500 8180229294583 = 1.222376 … \frac{B-R}{L}=\frac{9999320418500}{8180229294583}=1.222376\ldots L B − R = 8180229294583 9999320418500 = 1.222376 … See § 6 for further details.
The conditions of Definition 3.3 are linear in the weights, terminal densities, label flows, and allowances, and the value is invariant under scaling them, so with L = 1 L=1 L = 1 cells , and takes quadratic label flows and weights on every cell, in a basis whose nonnegativity turns inequalities between coefficients into inequalities at every point. resulting flow instance is given by a table of integers. Normal continuity and the terminal condition follow from two boundary rules on the table, capacity from finitely many integer inequalities, and conservation from the definition of the allowance, so none of them depends on how the table was found (Proposition 7.5).
Proposition 3.6 (Computer-aided flow instance). There is a flow instance on Δ 11 \Delta_{11} Δ 11 T = 249 / 400 T = 249/400 T = 249/400
B − R L = 159389999561650025 129321858575204877 = 1.2325 … \frac{B-R}{L}=\frac{159389999561650025}{129321858575204877}=1.2325\ldots L B − R = 129321858575204877 159389999561650025 = 1.2325 … Theorem 1.1 follows from Lemma 2.2 , Theorem 3.4 , and Proposition 3.6 . See § 7 and § 7.8 for further details.
An Example on the Triangle
For q = 3 q = 3 q = 3 T = 2 / 3 T = 2/3 T = 2/3 Δ 3 \Delta_3 Δ 3 § 3 . Then we explain why and how the three flow conditions hold, and compute the value of the flow instance. The geometry is that of Figure 1 , and Figure 2 shows the flow of label 2.
Figure 2. Label 2 and its flow into the interval Ω { 2 , 3 } \Omega_{\{2,3\}} Ω { 2 , 3 } x 1 = 0 x_1 = 0 x 1 = 0 − F 2 , 1 [ 3 ] = 2 / 3 -F_{2,1}^{[3]} = 2/3 − F 2 , 1 [ 3 ] = 2/3 x 1 = 0 x_1 = 0 x 1 = 0
The geometry. We measure the hexagon in the coordinates ( x 1 , x 2 ) (x_1,x_2) ( x 1 , x 2 ) x 3 = 1 − x 1 − x 2 x_3 = 1-x_1-x_2 x 3 = 1 − x 1 − x 2 Ω { i , j } \Omega_{\{i,j\}} Ω { i , j } x i x_i x i ( 0 , 0 ) (0,0) ( 0 , 0 ) ( 1 , 0 ) (1,0) ( 1 , 0 ) ( 0 , 1 ) (0,1) ( 0 , 1 ) 1 / 2 1/2 1/2 1 / 3 1/3 1/3 1 / 18 1/18 1/18 1 / 2 − 3 ⋅ ( 1 / 18 ) = 1 / 3 1/2-3\cdot(1/18)=1/3 1/2 − 3 ⋅ ( 1/18 ) = 1/3 Ω { i , j } \Omega_{\{i,j\}} Ω { i , j } x i x_i x i 1 / 3 1/3 1/3 2 / 3 2/3 2/3 1 / 3 1/3 1/3 Φ i [ 3 ] \Phi_i^{[3]} Φ i [ 3 ] x i = 2 / 3 x_i = 2/3 x i = 2/3 x j + x s = 1 / 3 x_j+x_s = 1/3 x j + x s = 1/3 1 / 3 1/3 1/3 x j x_j x j
The flow instance. On the hexagon we take every weight to be w s t [ 3 ] = 1 / 2 w_{st}^{[3]} = 1/2 w s t [ 3 ] = 1/2 g i [ 3 ] = 1 g_i^{[3]} = 1 g i [ 3 ] = 1 ϵ [ 3 ] = 2 \epsilon_{[3]} = 2 ϵ [ 3 ] = 2 i i i
F i [ 3 ] ( x ) = e i − p [ 3 ] ( x ) with p s [ 3 ] ( x ) = 2 3 − x s for s ∈ [ 3 ] , F_i^{[3]}(x)=e_i-p^{[3]}(x)\text{ with }p_s^{[3]}(x)=\frac{2}{3}-x_s\text{ for }s\in[3], F i [ 3 ] ( x ) = e i − p [ 3 ] ( x ) with p s [ 3 ] ( x ) = 3 2 − x s for s ∈ [ 3 ] , and F ∗ [ 3 ] = 0 F_*^{[3]}=0 F ∗ [ 3 ] = 0 p [ 3 ] ( x ) p^{[3]}(x) p [ 3 ] ( x ) p [ 3 ] ( x ) p^{[3]}(x) p [ 3 ] ( x ) i i i x x x e i e_i e i Ω { i , j } \Omega_{\{i,j\}} Ω { i , j } w i j { i , j } = 2 / 9 w_{ij}^{\{i,j\}} = 2/9 w ij { i , j } = 2/9 g i { i , j } = g j { i , j } = 2 / 9 g_i^{\{i,j\}} = g_j^{\{i,j\}} = 2/9 g i { i , j } = g j { i , j } = 2/9 ϵ { i , j } = 0 \epsilon_{\{i,j\}} = 0 ϵ { i , j } = 0
F i { i , j } ( x ) = 2 3 ( x i − 1 3 ) ( e i − e j ) and F j { i , j } ( x ) = 2 3 ( x j − 1 3 ) ( e j − e i ) , F_i^{\{i,j\}}(x) = \frac{2}{3}\left(x_i-\frac{1}{3}\right)(e_i-e_j) \text{ and } F_j^{\{i,j\}}(x) = \frac{2}{3}\left(x_j-\frac{1}{3}\right)(e_j-e_i), F i { i , j } ( x ) = 3 2 ( x i − 3 1 ) ( e i − e j ) and F j { i , j } ( x ) = 3 2 ( x j − 3 1 ) ( e j − e i ) , with F ∗ { i , j } = 0 F_*^{\{i,j\}} = 0 F ∗ { i , j } = 0 2 / 3 2/3 2/3
Proposition 4.1 (A flow instance on the triangle). The given flow instance on Δ 3 \Delta_3 Δ 3 B = 7 / 3 B = 7/3 B = 7/3 R = 2 / 3 R = 2/3 R = 2/3 L = 3 / 2 L = 3/2 L = 3/2 Δ 3 \Delta_3 Δ 3 α \alpha α α ≥ 10 / 9 \alpha\ge10/9 α ≥ 10/9
Figure 2 shows what the flow of label 2 does on the hexagon. On the side x 2 = 0 x_2 = 0 x 2 = 0 F 2 [ 3 ] F_2^{[3]} F 2 [ 3 ] 1 − 2 / 3 = 1 / 3 1 - 2/3 = 1/3 1 − 2/3 = 1/3 1 / 3 1/3 1/3 Φ 2 [ 3 ] \Phi_2^{[3]} Φ 2 [ 3 ] p 2 [ 3 ] = 0 p_2^{[3]} = 0 p 2 [ 3 ] = 0 F 2 [ 3 ] F_2^{[3]} F 2 [ 3 ] g 2 [ 3 ] = 1 g_2^{[3]} = 1 g 2 [ 3 ] = 1 F 1 [ 3 ] F_1^{[3]} F 1 [ 3 ] F 3 [ 3 ] F_3^{[3]} F 3 [ 3 ] F ∗ [ 3 ] F_*^{[3]} F ∗ [ 3 ]
On the side x 1 = 0 x_1 = 0 x 1 = 0 F 2 [ 3 ] F_2^{[3]} F 2 [ 3 ] − p 1 [ 3 ] = − 2 / 3 -p_1^{[3]} = -2/3 − p 1 [ 3 ] = − 2/3 2 / 3 2/3 2/3 Ω { 2 , 3 } \Omega_{\{2,3\}} Ω { 2 , 3 } F 2 { 2 , 3 } F_2^{\{2,3\}} F 2 { 2 , 3 } 2 / 3 2/3 2/3 ϵ [ 3 ] = 2 \epsilon_{[3]} = 2 ϵ [ 3 ] = 2 x 3 = 0 x_3 = 0 x 3 = 0 Ω { 1 , 2 } \Omega_{\{1,2\}} Ω { 1 , 2 } 2 / 3 2/3 2/3
1 3 ⋅ 1 3 + 2 ⋅ 1 3 = 7 9 = 1 ⋅ 1 3 + 2 ⋅ 2 3 ⋅ 1 3 , \frac{1}{3}\cdot\frac{1}{3}+2\cdot\frac{1}{3}=\frac{7}{9}=1\cdot\frac{1}{3}+2\cdot\frac{2}{3}\cdot\frac{1}{3}, 3 1 ⋅ 3 1 + 2 ⋅ 3 1 = 9 7 = 1 ⋅ 3 1 + 2 ⋅ 3 2 ⋅ 3 1 , which is Λ [ 3 ] ( C ) = 0 \Lambda_{[3]}(C)=0 Λ [ 3 ] ( C ) = 0 C ≡ 2 C\equiv2 C ≡ 2 § 3.3 . Figure 1 b shows a region labeled 1 bounded by a cut. On the cut the selected flow jumps from F 1 [ 3 ] F_1^{[3]} F 1 [ 3 ]
Capacity on the hexagon is a check of the sums over the singletons I = { i } I=\{i\} I = { i } i i i F ℓ [ 3 ] F_\ell^{[3]} F ℓ [ 3 ] 1 − p i [ 3 ] 1-p_i^{[3]} 1 − p i [ 3 ] ℓ = i \ell=i ℓ = i − p i [ 3 ] -p_i^{[3]} − p i [ 3 ] ∗ * ∗ 0 ≤ p i [ 3 ] ≤ 2 / 3 0\le p_i^{[3]}\le2/3 0 ≤ p i [ 3 ] ≤ 2/3 { i } \{i\} { i } 1 / 2 + 1 / 2 = 1 1/2+1/2=1 1/2 + 1/2 = 1 i i i ( 2 / 3 ) ( x i − 1 / 3 ) (2/3)(x_i-1/3) ( 2/3 ) ( x i − 1/3 ) ( 2 / 3 ) ( x i − 2 / 3 ) (2/3)(x_i-2/3) ( 2/3 ) ( x i − 2/3 ) 2 / 9 2/9 2/9 ∗ * ∗
The value of the flow instance. The hexagon has three terminal facets of length 1 / 3 1/3 1/3 3 ⋅ ( 1 / 3 ) ⋅ 1 = 1 3\cdot(1/3)\cdot1=1 3 ⋅ ( 1/3 ) ⋅ 1 = 1 B B B 2 / 9 2/9 2/9 6 ⋅ ( 2 / 9 ) = 4 / 3 6\cdot(2/9)=4/3 6 ⋅ ( 2/9 ) = 4/3 B = 7 / 3 B=7/3 B = 7/3 1 / 3 1/3 1/3 R = 2 / 3 R=2/3 R = 2/3 R R R i < j i<j i < j w i j S w_{ij}^{S} w ij S 1 / 3 1/3 1/3 B B B
L = 3 ⋅ 1 2 ⋅ 1 3 ⏟ hexagon + 3 ⋅ 2 9 ⋅ 1 3 ⏟ intervals + 1 3 ⋅ 7 3 ⏟ terminal edges = 3 2 . L=3\cdot\underbrace{\frac{1}{2}\cdot\frac{1}{3}}_{\text{hexagon}+3\cdot\underbrace{\frac{2}{9}\cdot\frac{1}{3}}_{\text{intervals}}+\underbrace{\frac{1}{3}\cdot\frac{7}{3}}_{\text{terminal edges}}=\frac{3}{2}.} L = 3 ⋅ hexagon + 3 ⋅ intervals 9 2 ⋅ 3 1 + terminal edges 3 1 ⋅ 3 7 = 2 3 . 2 1 ⋅ 3 1 The value of the flow instance is ( B − R ) / L = ( 5 / 3 ) / ( 3 / 2 ) = 10 / 9 (B-R)/L=(5/3)/(3/2)=10/9 ( B − R ) / L = ( 5/3 ) / ( 3/2 ) = 10/9
Why the hexagon flows are not graph flows. On the hexagon any two terminal flows differ by F i [ 3 ] − F j [ 3 ] = e i − e j F_i^{[3]}-F_j^{[3]}=e_i-e_j F i [ 3 ] − F j [ 3 ] = e i − e j 1 / 2 1/2 1/2 e s − e t e_s-e_t e s − e t 1 / 2 1/2 1/2 a ( e 1 − e 2 ) + b ( e 1 − e 3 ) + c ( e 2 − e 3 ) a(e_1-e_2)+b(e_1-e_3)+c(e_2-e_3) a ( e 1 − e 2 ) + b ( e 1 − e 3 ) + c ( e 2 − e 3 ) ∣ a ∣ , ∣ b ∣ , ∣ c ∣ ≤ 1 / 2 |a|,|b|,|c|\le1/2 ∣ a ∣ , ∣ b ∣ , ∣ c ∣ ≤ 1/2 e 1 − e 2 = ( e 1 − e 3 ) − ( e 2 − e 3 ) e_1-e_2=(e_1-e_3)-(e_2-e_3) e 1 − e 2 = ( e 1 − e 3 ) − ( e 2 − e 3 ) e 1 − e 2 e_1-e_2 e 1 − e 2 a = b = 1 / 2 a=b=1/2 a = b = 1/2 c = − 1 / 2 c=-1/2 c = − 1/2 e 1 − e 3 e_1-e_3 e 1 − e 3 a = b = c = 1 / 2 a=b=c=1/2 a = b = c = 1/2 e 2 − e 3 e_2-e_3 e 2 − e 3 Proposition 3.2 ruled out on the graph.
Proof of the Flow Lower Bound
§ 3.3 derived Theorem 3.4 from three lemmas, one for each inequality of its chain, and this section states and proves them. § 5.1 fixes what § 3 left informal, namely the measures and normals on the faces, the regularity of the label flows, and the form of capacity that holds for every normal. § 5.2 proves Lemma 5.2 , the first inequality, and Lemma 5.3 , the second inequality for a cut whose label regions are polytopes. § 5.3 makes the crossing measure of § 3.2 precise and derives from the approximation factor the regularity that a measurable cut lacks, and § 5.4 recovers the labels on the boundary of a face. § 5.5 then proves Lemma 5.9 and Lemma 5.10 .
Throughout, a random non-opposite cut is a map C : Ξ × Δ q → [ q ] ∪ { ∗ } C:\Xi\times\Delta_q\to[q]\cup\{\ast\} C : Ξ × Δ q → [ q ] ∪ { ∗ } Ξ \Xi Ξ C ( ξ , ⋅ ) C(\xi,\mathord\cdot) C ( ξ , ⋅ ) σ \sigma σ Ξ \Xi Ξ Δ q \Delta_q Δ q Definition 2.1 , and the cuts of Lemma 2.2 are of this kind (Section A). Probabilities and expectations are over Ξ \Xi Ξ
Conventions and Precise Definitions
Fix q ≥ 2 q\ge2 q ≥ 2 T ∈ ( 1 / 2 , 1 ) T\in(1/2,1) T ∈ ( 1/2 , 1 ) 1 / ∣ S ∣ ≤ 1 / 2 < T 1/|S|\le1/2<T 1/∣ S ∣ ≤ 1/2 < T Ω S \Omega_S Ω S Δ S \Delta_S Δ S ∣ S ∣ − 1 |S|-1 ∣ S ∣ − 1 T < 1 T<1 T < 1 T > 1 / 2 T>1/2 T > 1/2 ∣ S ∣ ≥ 3 |S|\ge3 ∣ S ∣ ≥ 3 x j = 0 x_j=0 x j = 0 Ω S \Omega_S Ω S Ω S ∖ { j } \Omega_{S\setminus\{j\}} Ω S ∖ { j } max i ∈ S x i ≤ T \max_{i\in S}x_i\le T max i ∈ S x i ≤ T x j = 0 x_j=0 x j = 0 Ω { i , j } \Omega_{\{i,j\}} Ω { i , j } x i = T x_i=T x i = T x j = T x_j=T x j = T
For U = S ∖ { j } U=S\setminus\{j\} U = S ∖ { j } ∣ U ∣ ≥ 2 |U|\ge2 ∣ U ∣ ≥ 2 S = U ∪ { j } S=U\cup\{j\} S = U ∪ { j } U U U U U U S S S U U U r r r q − r q-r q − r j ∉ U j\notin U j ∈ / U r r r q = 4 q=4 q = 4 Ω { 1 , 2 } \Omega_{\{1,2\}} Ω { 1 , 2 } { 1 , 2 , 3 } \{1,2,3\} { 1 , 2 , 3 } { 1 , 2 , 4 } \{1,2,4\} { 1 , 2 , 4 } Δ q \Delta_q Δ q (14) below.
The tangent space of Δ S \Delta_S Δ S V S = { v ∈ R S : ∑ i ∈ S v i = 0 } V_S=\{v\in\mathbb{R}^S:\sum_{i\in S}v_i=0\} V S = { v ∈ R S : ∑ i ∈ S v i = 0 } Δ S \Delta_S Δ S d x dx d x ± 1 \pm1 ± 1 d x dx d x d d d d ( x , x + h ( e i − e j ) ) = ∣ h ∣ d(x,x+h(e_i-e_j))=|h| d ( x , x + h ( e i − e j )) = ∣ h ∣ A A A d σ \mathrm{d}\sigma d σ ν A ( F ) \nu_A(F) ν A ( F ) F F F ∂ A \partial A ∂ A A A A
The divergence div F \operatorname{div} F div F F F F F F F A A A
∫ A div F d x = ∫ ∂ A ν A ( F ) d σ . (12) \int_A \operatorname{div} F\,\mathrm{d}x=\int_{\partial A}\nu_A(F)\,\mathrm{d}\sigma. \tag*{(12)} ∫ A div F d x = ∫ ∂ A ν A ( F ) d σ . (12) The normal and the surface measure must use matching coordinates. Although they separately depend on which coordinate is deleted, their product in this formula does not, and we always change the two together when rewriting a boundary integral. Represent a normal covector by ν ∈ R S \nu\in\mathbb{R}^S ν ∈ R S ν ( e i − e j ) = ν i − ν j \nu(e_i-e_j)=\nu_i-\nu_j ν ( e i − e j ) = ν i − ν j
On a coordinate facet x j = 0 x_j=0 x j = 0 Ω S \Omega_S Ω S x j x_j x j x i = T x_i=T x i = T x i x_i x i x j x_j x j x i x_i x i
ν Ω S ( F ) = − F j on x j = 0 and ν Ω S ( F ) = F i on x i = T . (13) \nu_{\Omega_S}(F)=-F_j\ \text{ on }x_j=0\text{ and }\nu_{\Omega_S}(F)=F_i\ \text{ on }x_i=T. \tag*{(13)} ν Ω S ( F ) = − F j on x j = 0 and ν Ω S ( F ) = F i on x i = T . (13) With this choice the surface measure of the coordinate facet x j = 0 x_j=0 x j = 0 Ω S ∖ { j } \Omega_{S\setminus\{j\}} Ω S ∖ { j } x i = T x_i=T x i = T d σ \mathrm{d}\sigma d σ σ ( J ) \sigma(J) σ ( J ) J J J (13) the flux jump (11) is
Λ S ( C ) = ∫ ∂ Ω S ν Ω S ( F C ( y ) S ( y ) ) d σ ( y ) − ∫ Ω S div F C ( x ) S ( x ) d x , \Lambda_S(C)=\int_{\partial\Omega_S}\nu_{\Omega_S}\left(F^S_{C(y)}(y)\right)\,\mathrm{d}\sigma(y)-\int_{\Omega_S}\operatorname{div}F^S_{C(x)}(x)\,\mathrm{d}x, Λ S ( C ) = ∫ ∂ Ω S ν Ω S ( F C ( y ) S ( y ) ) d σ ( y ) − ∫ Ω S div F C ( x ) S ( x ) d x , the selected outward flux through the whole boundary of Ω S \Omega_S Ω S
A label flow F ℓ S F^S_\ell F ℓ S § 3.2 is a bounded tangent vector field F ℓ S : Ω S → V S F^S_\ell:\Omega_S\to V_S F ℓ S : Ω S → V S Ω S \Omega_S Ω S P S \mathcal{P}_S P S ∣ S ∣ − 1 |S|-1 ∣ S ∣ − 1 Z S Z_S Z S Ω S \Omega_S Ω S F ℓ , i S F^S_{\ell,i} F ℓ , i S i i i Normal continuity means that on every facet shared by two cells P P P P ′ P' P ′ ν P ( F ℓ S ) \nu_P(F^S_\ell) ν P ( F ℓ S ) P P P − ν P ′ ( F ℓ S ) -\nu_{P'}(F^S_\ell) − ν P ′ ( F ℓ S ) P ′ P' P ′ ℓ \ell ℓ w i j S = w j i S w^S_{ij}=w^S_{ji} w ij S = w j i S Ω S \Omega_S Ω S g i S g^S_i g i S Φ i S \Phi^S_i Φ i S ϵ S \epsilon_S ϵ S R R R
For a parent S = U ∪ { j } S=U\cup\{j\} S = U ∪ { j } U U U ℓ ∈ U ∪ { ∗ } \ell\in U\cup\{*\} ℓ ∈ U ∪ { ∗ } supply of ℓ \ell ℓ S S S U U U
b ℓ S → U ( x ) = − F ℓ , j S ( x ) for x ∈ Ω U . (14) b^{S\to U}_\ell(x)=-F^S_{\ell,j}(x)\quad\text{for }x\in\Omega_U. \tag*{(14)} b ℓ S → U ( x ) = − F ℓ , j S ( x ) for x ∈ Ω U . (14) By (13) it is the outward normal component of F ℓ S F^S_\ell F ℓ S x j = 0 x_j=0 x j = 0 Ω S \Omega_S Ω S (10) on Ω U \Omega_U Ω U
div F ℓ U ≤ ∑ j ∉ U b ℓ U ∪ { j } → U + ϵ U almost everywhere on Ω U \operatorname{div}F^U_\ell\leq\sum_{j\notin U}b^{U\cup\{j\}\to U}_\ell+\epsilon_U\quad\text{almost everywhere on }\Omega_U div F ℓ U ≤ j ∈ / U ∑ b ℓ U ∪ { j } → U + ϵ U almost everywhere on Ω U for every ℓ ∈ U ∪ { ∗ } \ell\in U \cup\{\ast\} ℓ ∈ U ∪ { ∗ } U = [ q ] U = [q] U = [ q ]
The capacity condition (9) bounds the difference of two label flows across coordinate subsets I I I S S S Lemmas 5.3 and 5.9 apply at the interface.
Lemma 5.1 (Cut condition). Let z ∈ R S z \in\mathbb{R}^{S} z ∈ R S ∑ i ∈ S z i = 0 \sum_{i\in S} z_i = 0 ∑ i ∈ S z i = 0 w i j = w j i ≥ 0 w_{ij} = w_{ji} \ge0 w ij = w j i ≥ 0 i ≠ j i \ne j i = j S S S I ⊂ S I \subset S I ⊂ S
∣ ∑ i ∈ I z i ∣ ≤ ∑ i ∈ I , j ∈ S ∖ I w i j . \left|\sum_{i\in I} z_i\right| \le\sum_{i\in I,j\in S\setminus I} w_{ij}. i ∈ I ∑ z i ≤ i ∈ I , j ∈ S ∖ I ∑ w ij . Then for every v ∈ R S v \in\mathbb{R}^{S} v ∈ R S
∣ v ⋅ z ∣ ≤ ∑ i < j ∈ S w i j ∣ v i − v j ∣ . |v \cdot z| \le\sum_{i<j\in S} w_{ij}|v_i-v_j|. ∣ v ⋅ z ∣ ≤ i < j ∈ S ∑ w ij ∣ v i − v j ∣. Proof. Let I θ = { i : v i > θ } I_\theta= \{i : v_i > \theta\} I θ = { i : v i > θ } θ \theta θ min i v i \min_i v_i min i v i max i v i \max_i v_i max i v i ∑ i z i = 0 \sum_i z_i = 0 ∑ i z i = 0 i , j i,j i , j I θ I_\theta I θ θ \theta θ ∣ v i − v j ∣ |v_i-v_j| ∣ v i − v j ∣
∣ v ⋅ z ∣ = ∣ ∫ ∑ i ∈ I θ z i d θ ∣ |v \cdot z| = \left|\int\sum_{i\in I_\theta} z_i\,\mathrm{d}\theta\right| ∣ v ⋅ z ∣ = ∫ i ∈ I θ ∑ z i d θ ≤ ∫ ∑ i ∈ I θ , j ∉ I θ w i j d θ the subset inequalities \le\int\sum_{i\in I_\theta,j\notin I_\theta} w_{ij}\,\mathrm{d}\theta\qquad\text{the subset inequalities} ≤ ∫ i ∈ I θ , j ∈ / I θ ∑ w ij d θ the subset inequalities = ∑ i < j w i j ∣ v i − v j ∣ . = \sum_{i<j} w_{ij}|v_i-v_j|. = i < j ∑ w ij ∣ v i − v j ∣. Applied at a point x x x z = F ℓ S ( x ) − F m S ( x ) z = F_\ell^S(x) - F_m^S(x) z = F ℓ S ( x ) − F m S ( x ) w i j = w i j S ( x ) w_{ij} = w_{ij}^S(x) w ij = w ij S ( x ) (9) into
∣ v ( F ℓ S − F m S ) ∣ ≤ ∑ i < j ∈ S w i j S ∣ v i − v j ∣ for every v ∈ R S , (15) |v(F_\ell^S-F_m^S)| \le\sum_{i<j\in S} w_{ij}^S|v_i-v_j| \text{ for every } v \in\mathbb{R}^{S}, \tag*{(15)} ∣ v ( F ℓ S − F m S ) ∣ ≤ i < j ∈ S ∑ w ij S ∣ v i − v j ∣ for every v ∈ R S , (15) and taking v i = 1 [ i ∈ I ] v_i = 1[i \in I] v i = 1 [ i ∈ I ] (9) , so the two forms are equivalent. An interface with unit normal v v v e i − e j e_i-e_j e i − e j ∣ v i − v j ∣ |v_i-v_j| ∣ v i − v j ∣ (15) is the cost density of the interface. Thus, at every point an interface between any two labels, in any orientation, has cost density at least the normal difference of the two label flows across it. The proof writes each entry as v i − min s v s = ∫ 1 [ i ∈ I θ ] d θ v_i-\min_s v_s = \int1[i \in I_\theta]\,\mathrm{d}\theta v i − min s v s = ∫ 1 [ i ∈ I θ ] d θ v ⋅ z v\cdot z v ⋅ z θ \theta θ ∑ i ∈ I θ z i \sum_{i\in I_\theta} z_i ∑ i ∈ I θ z i v v v I θ I_\theta I θ S S S
Summation over Faces
The first inequality of the chain is deterministic. It uses only the two conditions that compare the flows across the boundaries of the faces, the terminal condition and conservation, together with the labels a non-opposite cut may use there. For a triangle S = { 1 , 2 , 3 } S = \{1,2,3\} S = { 1 , 2 , 3 } U = { 1 , 2 } U = \{1,2\} U = { 1 , 2 } Λ S ( C ) \Lambda_S(C) Λ S ( C ) ∫ Ω U b C S → U ( x ) d x \int_{\Omega_U} b_C^{S\to U}(x)\,\mathrm{d}x ∫ Ω U b C S → U ( x ) d x Λ U ( C ) \Lambda_U(C) Λ U ( C ) − ∫ Ω U div F C ( x ) U ( x ) d x -\int_{\Omega_U} \operatorname{div} F_{C(x)}^U(x)\,\mathrm{d}x − ∫ Ω U div F C ( x ) U ( x ) d x ∗ \ast ∗ − ∫ Ω U ϵ U d x -\int_{\Omega_U}\epsilon_U\,\mathrm{d}x − ∫ Ω U ϵ U d x
Lemma 5.2 (Summation over faces). Let the label flows of a weighting satisfy the terminal condition, and conservation with allowances ϵ U \epsilon_U ϵ U R = ∑ ∣ U ∣ ≥ 2 ∫ Ω U ϵ U d x R = \sum_{|U|\ge2}\int_{\Omega_U}\epsilon_U\,\mathrm{d}x R = ∑ ∣ U ∣ ≥ 2 ∫ Ω U ϵ U d x C C C Δ q \Delta_q Δ q
∑ ∣ S ∣ ≥ 2 Λ S ( C ) + cost t e r m ( C ) ≥ B − R . \sum_{|S|\ge2}\Lambda_S(C) + \operatorname{cost}_{\mathrm{term}}(C) \ge B - R. ∣ S ∣ ≥ 2 ∑ Λ S ( C ) + cost term ( C ) ≥ B − R . Proof. The boundary of Ω S \Omega_S Ω S Φ i S \Phi_i^S Φ i S i ∈ S i \in S i ∈ S ∣ S ∣ ≥ 3 |S| \ge3 ∣ S ∣ ≥ 3 Ω S ∖ { j } \Omega_{S\setminus\{j\}} Ω S ∖ { j } j ∈ S j \in S j ∈ S Φ i S \Phi_i^S Φ i S (13) and the terminal condition give ν Ω S ( F C ( y ) S ( y ) ) = g i S ( y ) 1 [ C ( y ) = i ] \nu_{\Omega_S}(F_{C(y)}^S(y)) = g_i^S(y)1[C(y) = i] ν Ω S ( F C ( y ) S ( y )) = g i S ( y ) 1 [ C ( y ) = i ] 1 [ C ( y ) = i ] + 1 [ C ( y ) ≠ i ] = 1 1[C(y) = i] + 1[C(y) \ne i] = 1 1 [ C ( y ) = i ] + 1 [ C ( y ) = i ] = 1 g i S g_i^S g i S Ω U \Omega_U Ω U U = S ∖ { j } U = S \setminus\{j\} U = S ∖ { j } (13) gives ν Ω S ( F C ( x ) S ( x ) ) = b C ( x ) S → U ( x ) \nu_{\Omega_S}(F_{C(x)}^S(x)) = b_{C(x)}^{S\to U}(x) ν Ω S ( F C ( x ) S ( x )) = b C ( x ) S → U ( x ) C ( x ) ∈ supp ( x ) ∪ { ∗ } ⊆ U ∪ { ∗ } C(x) \in\operatorname{supp}(x) \cup\{\ast\} \subseteq U \cup\{\ast\} C ( x ) ∈ supp ( x ) ∪ { ∗ } ⊆ U ∪ { ∗ } C C C j j j x j = 0 x_j = 0 x j = 0 x x x C ( x ) C(x) C ( x ) Λ U ( C ) \Lambda_U(C) Λ U ( C ) § 5.1 .
Summing (11) over all S S S U U U
∑ ∣ S ∣ ≥ 2 Λ S ( C ) + cost t e r m ( C ) = B + ∑ ∣ U ∣ ≥ 2 ∫ Ω U ( ∑ j ∉ U U ∪ { j } → U b C ( x ) U ∪ { j } → U ( x ) − div F C ( x ) U ( x ) ) d x , (16) \sum_{|S|\ge2}\Lambda_S(C) + \operatorname{cost}_{\mathrm{term}}(C) = B + \sum_{|U|\ge2}\int_{\Omega_U}\left(\sum_{\substack{j\notin U\\U\cup\{j\}\to U}} b_{C(x)}^{U\cup\{j\}\to U}(x) - \operatorname{div} F_{C(x)}^U(x)\right)\,\mathrm{d}x, \tag*{(16)} ∣ S ∣ ≥ 2 ∑ Λ S ( C ) + cost term ( C ) = B + ∣ U ∣ ≥ 2 ∑ ∫ Ω U j ∈ / U U ∪ { j } → U ∑ b C ( x ) U ∪ { j } → U ( x ) − div F C ( x ) U ( x ) d x , (16) where the parent sum is empty for U = [ q ] U = [q] U = [ q ] C ( x ) C(x) C ( x ) Ω U \Omega_U Ω U − ϵ U ( x ) -\epsilon_U(x) − ϵ U ( x ) B − R B - R B − R
Non-oppositeness is used exactly to ensure C ( x ) ∈ U ∪ { ∗ } C(x) \in U \cup\{\ast\} C ( x ) ∈ U ∪ { ∗ } Λ S ( C ) \Lambda_S(C) Λ S ( C ) n ⋅ v n \cdot v n ⋅ v § 5.1 . In the covector representation, a unit normal n n n x p x_p x p ν ∈ R S \nu\in\mathbb{R}^S ν ∈ R S ν i = n i \nu_i = n_i ν i = n i i ≠ p i \ne p i = p ν p = 0 \nu_p = 0 ν p = 0 n ⋅ ( e i − e j ) = ν i − ν j n \cdot(e_i - e_j) = \nu_i - \nu_j n ⋅ ( e i − e j ) = ν i − ν j
Lemma 5.3 (Polyhedral cuts). Suppose the label flows on Ω S \Omega_S Ω S C C C Ω S \Omega_S Ω S S ∪ { ∗ } S \cup\{\ast\} S ∪ { ∗ } Ω S \Omega_S Ω S C C C ∂ Ω S \partial\Omega_S ∂ Ω S σ \sigma σ Z S Z_S Z S J J J J J J n n n ℓ − \ell^- ℓ − ℓ + \ell^+ ℓ +
Λ S ( C ) = ∫ J n ⋅ ( F ℓ + S − F ℓ − S ) d σ ≤ cost S ( C ) . \Lambda_S(C) = \int_J n \cdot\left(F_{\ell^+}^S - F_{\ell^-}^S\right)\,\mathrm{d}\sigma\le\operatorname{cost}_S(C). Λ S ( C ) = ∫ J n ⋅ ( F ℓ + S − F ℓ − S ) d σ ≤ cost S ( C ) . Proof. Apply (12) to F ℓ ( A ) S F_{\ell(A)}^S F ℓ ( A ) S A A A ℓ ( A ) \ell(A) ℓ ( A ) ∂ Ω S \partial\Omega_S ∂ Ω S (11) , by the assumption on the boundary labels. On a facet shared by two polytopes with the same label the two terms cancel, since the outward normals are opposite, and if
the facet is a cell facet the normal components agree across it by normal continuity. On a facet of J J J n ⋅ F ℓ − S \boldsymbol{n} \cdot F_{\ell-}^{S} n ⋅ F ℓ − S − n ⋅ F ℓ + S -\boldsymbol{n} \cdot F_{\ell+}^{S} − n ⋅ F ℓ + S − n ⋅ ( F ℓ + S − F ℓ − S ) -\boldsymbol{n} \cdot(F_{\ell+}^{S} - F_{\ell-}^{S}) − n ⋅ ( F ℓ + S − F ℓ − S )
For the inequality, a step h ( e i − e j ) h(e_i-e_j) h ( e i − e j ) J J J ∣ h ∣ ∣ n ⋅ ( e i − e j ) ∣ |h||\boldsymbol{n}\cdot(e_i-e_j)| ∣ h ∣∣ n ⋅ ( e i − e j ) ∣ μ i j S ( C ) = ∣ n ⋅ ( e i − e j ) ∣ σ \mu_{ij}^{S}(C)=|\boldsymbol{n}\cdot(e_i-e_j)|\sigma μ ij S ( C ) = ∣ n ⋅ ( e i − e j ) ∣ σ J J J
cost S ( C ) = ∑ i < j ∈ S ∫ J w i j S ∣ n ⋅ ( e i − e j ) ∣ d σ . \operatorname{cost}_{S}(C)=\sum_{i<j\in S}\int_{J}w_{ij}^{S}|\boldsymbol{n}\cdot(e_i-e_j)|\,d\sigma. cost S ( C ) = i < j ∈ S ∑ ∫ J w ij S ∣ n ⋅ ( e i − e j ) ∣ d σ . At σ \sigma σ J J J S ∪ { ∗ } S\cup\{\ast\} S ∪ { ∗ } Lemma 5.1 give (14) there with ν \nu ν n \boldsymbol{n} n J J J
We note that the inequality in Lemma 5.3 also appears in a different form in the paired calibrations of Lawlor and Morgan [16 ] , who use it to certify that a given cut is optimal. See also [7 ] and [9 ] .
The assumption on the boundary labels cannot simply be omitted. The non-opposite labeling that assigns i i i x i ≥ T x_i\ge T x i ≥ T ∗ \ast ∗
Crossing Measures and Regularity
The cost of a cut is the weight of the edges it severs. In the continuous setting an edge in direction v v v v v v
Definition 5.4 (Crossing measures and cost). For a map c c c number of changes of c c c # { s : c ( t s ) ≠ c ( t s + 1 ) } \#\{s:c(t_s)\ne c(t_{s+1})\} # { s : c ( t s ) = c ( t s + 1 )} t 1 < ⋯ < t m t_1<\cdots<t_m t 1 < ⋯ < t m essential number of changes N ( c ) N(c) N ( c ) c c c R \mathbb{R} R N N N C C C Ω S \Omega_S Ω S v ∈ V S v\in V_S v ∈ V S v v v t ↦ y + t v t\mapsto y+tv t ↦ y + t v y y y H H H v v v d y dy d y H H H d x = d y d t dx=dy\,dt d x = d y d t A ⊆ int Ω S A\subseteq\operatorname{int}\Omega_S A ⊆ int Ω S crossing mass of C C C A A A v v v
μ v ( C ) ( A ) = ∫ H N ( t ↦ C ( y + t v ) on { t : y + t v ∈ A } ) d y . \mu_v(C)(A)=\int_H N\bigl(t\mapsto C(y+tv)\text{ on }\{t:y+tv\in A\}\bigr)\,dy. μ v ( C ) ( A ) = ∫ H N ( t ↦ C ( y + t v ) on { t : y + t v ∈ A } ) d y . The labeling C C C finite crossings on Ω S \Omega_S Ω S μ e i − e j ( C ) ( int Ω S ) < ∞ \mu_{e_i-e_j}(C)(\operatorname{int}\Omega_S)<\infty μ e i − e j ( C ) ( int Ω S ) < ∞ i < j i<j i < j S S S μ v ( C ) \mu_v(C) μ v ( C ) int Ω S \operatorname{int}\Omega_S int Ω S Fact 5.5 below), the crossing measure in direction v v v μ i j S ( C ) = μ e i − e j ( C ) \mu_{ij}^{S}(C)=\mu_{e_i-e_j}(C) μ ij S ( C ) = μ e i − e j ( C ) Δ q \Delta_q Δ q C C C Δ q \Delta_q Δ q [ q ] ∪ { ∗ } [q]\cup\{\ast\} [ q ] ∪ { ∗ } Ω S \Omega_S Ω S § 3.3 are
cost S ( C ) = ∑ i < j ∈ S ∫ int Ω S w i j S d μ i j S ( C ) and cost t e r m ( C ) = ∑ S ⊆ [ q ] ∣ S ∣ ≥ 2 ∑ i ∈ S ∫ Φ i S a i S ( y ) 1 [ C ( y ) ≠ i ] d σ ( y ) , \operatorname{cost}_{S}(C)=\sum_{i<j\in S}\int_{\operatorname{int}\Omega_S}w_{ij}^{S}\,d\mu_{ij}^{S}(C)
\quad\text{and}\quad
\operatorname{cost}_{\mathrm{term}}(C)=\sum_{\substack{S\subseteq[q]\\ |S|\ge2}}\sum_{i\in S}\int_{\Phi_i^{S}}a_i^{S}(y)\mathbf{1}[C(y)\ne i]\,d\sigma(y), cost S ( C ) = i < j ∈ S ∑ ∫ int Ω S w ij S d μ ij S ( C ) and cost term ( C ) = S ⊆ [ q ] ∣ S ∣ ≥ 2 ∑ i ∈ S ∑ ∫ Φ i S a i S ( y ) 1 [ C ( y ) = i ] d σ ( y ) , with cost S ( C ) = + ∞ \operatorname{cost}_{S}(C)=+\infty cost S ( C ) = + ∞ C C C Ω S \Omega_S Ω S C C C cost ( C ) = ∑ ∣ S ∣ ≥ 2 cost S ( C ) + cost t e r m ( C ) \operatorname{cost}(C)=\sum_{|S|\ge2}\operatorname{cost}_{S}(C)+\operatorname{cost}_{\mathrm{term}}(C) cost ( C ) = ∑ ∣ S ∣ ≥ 2 cost S ( C ) + cost term ( C )
The extension of the crossing masses to Borel measures is a statement of the theory of functions of bounded variation, which we introduce after it.
Fact 5.5 (Crossing measures are derivative measures). Let C C C Ω S \Omega_S Ω S u ℓ = 1 [ C = ℓ ] u_\ell= 1[C = \ell] u ℓ = 1 [ C = ℓ ] ℓ \ell ℓ v ∈ V S v \in V_S v ∈ V S
T ℓ , v ( ψ ) = − ∫ int Ω S u ℓ ( x ) ∂ v ψ ( x ) d x T_{\ell,v}(\psi) = -\int_{\operatorname{int}\Omega_S} u_\ell(x)\,\partial_v\psi(x)\,dx T ℓ , v ( ψ ) = − ∫ int Ω S u ℓ ( x ) ∂ v ψ ( x ) d x on ψ ∈ C c 1 ( int Ω S ) \psi\in C^1_c(\operatorname{int}\Omega_S) ψ ∈ C c 1 ( int Ω S ) ∂ v ψ \partial_v\psi ∂ v ψ ψ \psi ψ C C C Ω S \Omega_S Ω S ℓ \ell ℓ v v v m ℓ , v m_{\ell,v} m ℓ , v int Ω S \operatorname{int}\Omega_S int Ω S T ℓ , v ( ψ ) = ∫ ψ d m ℓ , v T_{\ell,v}(\psi) = \int\psi\,\mathrm{d}m_{\ell,v} T ℓ , v ( ψ ) = ∫ ψ d m ℓ , v ψ ∈ C c 1 ( int Ω S ) \psi\in C^1_c(\operatorname{int}\Omega_S) ψ ∈ C c 1 ( int Ω S ) v ∈ V S v \in V_S v ∈ V S A ⊆ int Ω S A \subseteq\operatorname{int}\Omega_S A ⊆ int Ω S
μ v ( C ) ( A ) = 1 2 ∑ ℓ ∣ m ℓ , v ∣ ( A ) , (17) \mu_v(C)(A) = \frac{1}{2}\sum_\ell|m_{\ell,v}|(A), \tag*{(17)} μ v ( C ) ( A ) = 2 1 ℓ ∑ ∣ m ℓ , v ∣ ( A ) , (17) where ∣ m ∣ |m| ∣ m ∣ m m m μ v ( C ) \mu_v(C) μ v ( C ) int Ω S \operatorname{int}\Omega_S int Ω S
This is the slicing theory of functions of bounded variation [1 Sections 3.2 and 3.11] . In one variable the total variation of the distributional derivative of an indicator is its essential number of changes, and in several variables the variation in direction v v v v v v 1 2 \frac{1}{2} 2 1 (17) . For small h h h μ i j S ( C ) ( A ) \mu^S_{ij}(C)(A) μ ij S ( C ) ( A ) ∣ h ∣ − 1 |h|^{-1} ∣ h ∣ − 1 x ∈ A x \in A x ∈ A C ( x ) ≠ C ( x + h ( e i − e j ) ) C(x) \ne C(x+h(e_i-e_j)) C ( x ) = C ( x + h ( e i − e j )) ∣ h ∣ |h| ∣ h ∣ Lemma 5.6 makes this heuristic exact in expectation. A single point with a different label costs nothing, and the values of the weights on the cell boundaries Z S Z_S Z S μ i j S ( C ) ( Z S ) = 0 \mu^S_{ij}(C)(Z_S) = 0 μ ij S ( C ) ( Z S ) = 0 Lemma 5.6 ). Since the weights are bounded Borel functions and the crossing measures are finite Borel measures whenever C C C + ∞ +\infty + ∞ C C C
Fix a face S S S Ω = Ω S \Omega= \Omega_S Ω = Ω S d = ∣ S ∣ − 1 d = |S| - 1 d = ∣ S ∣ − 1 Z = Z S Z = Z_S Z = Z S ℓ ∈ S ∪ { ∗ } \ell\in S \cup\{*\} ℓ ∈ S ∪ { ∗ } u ℓ ( x ) = 1 [ C ( x ) = ℓ ] u_\ell(x) = 1[C(x) = \ell] u ℓ ( x ) = 1 [ C ( x ) = ℓ ]
The functional T ℓ , v T_{\ell,v} T ℓ , v Fact 5.5 differentiates the smooth test function ψ \psi ψ u ℓ u_\ell u ℓ m ℓ , v m_{\ell,v} m ℓ , v m ℓ , v ( A ) m_{\ell,v}(A) m ℓ , v ( A ) A A A u ℓ u_\ell u ℓ bounded variation , u ℓ ∈ B V ( int Ω ) u_\ell\in BV(\operatorname{int}\Omega) u ℓ ∈ B V ( int Ω ) m ℓ m_\ell m ℓ m ℓ , v = v ⋅ m ℓ m_{\ell,v} = v \cdot m_\ell m ℓ , v = v ⋅ m ℓ v v v [1 Section 3.1] . A set whose indicator has bounded variation is a set of finite perimeter .
For a one-dimensional example, let label 1 occupy ( − 1 , t ) (-1,t) ( − 1 , t ) ( t , 1 ) (t,1) ( t , 1 ) − 1 < t < 1 -1 < t < 1 − 1 < t < 1 t t t v = 1 v = 1 v = 1 ( − 1 , 1 ) (-1,1) ( − 1 , 1 )
T 1 , 1 ( ψ ) = − ∫ − 1 t ψ ′ ( x ) d x = − ψ ( t ) and T 2 , 1 ( ψ ) = − ∫ t 1 ψ ′ ( x ) d x = ψ ( t ) . T_{1,1}(\psi) = -\int_{-1}^{t}\psi'(x)\,\mathrm{d}x = -\psi(t) \quad\text{and}\quad T_{2,1}(\psi) = -\int_{t}^{1}\psi'(x)\,\mathrm{d}x = \psi(t). T 1 , 1 ( ψ ) = − ∫ − 1 t ψ ′ ( x ) d x = − ψ ( t ) and T 2 , 1 ( ψ ) = − ∫ t 1 ψ ′ ( x ) d x = ψ ( t ) . Thus, m 1 , 1 = − δ t m_{1,1} = -\delta_t m 1 , 1 = − δ t m 2 , 1 = δ t m_{2,1} = \delta_t m 2 , 1 = δ t δ t \delta_t δ t t t t δ t \delta_t δ t (17) , and integrating a weight φ \varphi φ ∫ φ d δ t = φ ( t ) \int\varphi\,\mathrm{d}\delta_t = \varphi(t) ∫ φ d δ t = φ ( t )
Now let t t t ( − 1 , 1 ) (-1,1) ( − 1 , 1 ) δ t \delta_t δ t E [ δ t ( A ) ] \mathbb{E}[\delta_t(A)] E [ δ t ( A )] A A A Fact 5.5 , C C C Ω \Omega Ω u ℓ u_\ell u ℓ B V ( int Ω ) BV(\operatorname{int}\Omega) B V ( int Ω ) μ v ( C ) = 1 2 ∑ ℓ ∣ m ℓ , v ∣ \mu_v(C)=\frac{1}{2}\sum_\ell|m_{\ell,v}| μ v ( C ) = 2 1 ∑ ℓ ∣ m ℓ , v ∣ v ≠ 0 v\ne0 v = 0 ∥ v ∥ \lVert v\rVert ∥ v ∥ v v v
The regularity that the proof needs is not imposed on the cuts. It is derived from the approximation factor, by the next lemma. Its part (ii) is also the estimate that bounds the expected cost in Lemma 5.10 , and part (iii) is what lets the later arguments ignore the cell walls.
Lemma 5.6 (Finite variation and expected crossings). Let C C C Δ q \Delta_q Δ q α \alpha α S S S ∣ S ∣ ≥ 2 |S|\ge2 ∣ S ∣ ≥ 2
(i) Almost surely, every indicator u ℓ = 1 [ C = ℓ ] u_\ell=\mathbf{1}[C=\ell] u ℓ = 1 [ C = ℓ ] B V ( int Ω S ) BV(\operatorname{int}\Omega_S) B V ( int Ω S ) C C C Ω S \Omega_S Ω S
(ii) For every i < j i<j i < j S S S φ ≥ 0 \varphi\ge0 φ ≥ 0 int Ω S \operatorname{int}\Omega_S int Ω S
E [ ∫ φ d μ i j S ( C ) ] ≤ α ∫ Ω S φ d x . (18) \mathbb{E}\left[\int\varphi\,\mathrm{d}\mu^S_{ij}(C)\right]\le\alpha\int_{\Omega_S}\varphi\,\mathrm{d}x. \tag*{(18)} E [ ∫ φ d μ ij S ( C ) ] ≤ α ∫ Ω S φ d x . (18) (iii) Consequently, almost surely μ i j S ( C ) ( Z S ) = 0 \mu^S_{ij}(C)(Z_S)=0 μ ij S ( C ) ( Z S ) = 0 i < j i<j i < j S S S
E [ cost S ( C ) ] ≤ α ∑ i < j ∈ S ∫ Ω S w i j S d x . \mathbb{E}[\operatorname{cost}_S(C)]\le\alpha\sum_{i<j\in S}\int_{\Omega_S}w^S_{ij}\,\mathrm{d}x. E [ cost S ( C )] ≤ α i < j ∈ S ∑ ∫ Ω S w ij S d x . Proof. Write Ω = Ω S \Omega=\Omega_S Ω = Ω S φ ≥ 0 \varphi\ge0 φ ≥ 0 int Ω \operatorname{int}\Omega int Ω u ℓ u_\ell u ℓ v v v
V v ( u ℓ ; φ ) = sup ψ ∈ C c 1 ( int Ω ) ∣ ψ ∣ ≤ φ ∫ u ℓ ∂ v ψ d x . V_v(u_\ell;\varphi)=\sup_{\substack{\psi\in C^1_c(\operatorname{int}\Omega)\\|\psi|\le\varphi}}\int u_\ell\,\partial_v\psi\,\mathrm{d}x. V v ( u ℓ ; φ ) = ψ ∈ C c 1 ( int Ω ) ∣ ψ ∣ ≤ φ sup ∫ u ℓ ∂ v ψ d x . Both ψ \psi ψ − ψ -\psi − ψ sup ∣ ψ ∣ ≤ φ ∣ T ℓ , v ( ψ ) ∣ \sup_{|\psi|\le\varphi}|T_{\ell,v}(\psi)| sup ∣ ψ ∣ ≤ φ ∣ T ℓ , v ( ψ ) ∣ m ℓ , v m_{\ell,v} m ℓ , v V v ( u ℓ ; φ ) = ∫ φ d ∣ m ℓ , v ∣ V_v(u_\ell;\varphi)=\int\varphi\,\mathrm{d}|m_{\ell,v}| V v ( u ℓ ; φ ) = ∫ φ d ∣ m ℓ , v ∣
For sufficiently small h > 0 h>0 h > 0 ψ \psi ψ int Ω \operatorname{int}\Omega int Ω ψ \psi ψ
∫ u ℓ ∂ v ψ d x = lim h ↓ 0 ∫ u ℓ ( x ) ψ ( x ) − ψ ( x − h v ) h d x = lim h ↓ 0 ∫ u ℓ ( x ) − u ℓ ( x + h v ) h ψ ( x ) d x translate the second integral = − lim h ↓ 0 ∫ ψ ( x ) u ℓ ( x + h v ) − u ℓ ( x ) h d x . \begin{aligned}
\int u_\ell\,\partial_v\psi\,\mathrm{d}x
&=\lim_{h\downarrow0}\int u_\ell(x)\frac{\psi(x)-\psi(x-hv)}{h}\,\mathrm{d}x\\
&=\lim_{h\downarrow0}\int\frac{u_\ell(x)-u_\ell(x+hv)}{h}\psi(x)\,\mathrm{d}x
&&\text{translate the second integral}\\
&=-\lim_{h\downarrow0}\int\psi(x)\frac{u_\ell(x+hv)-u_\ell(x)}{h}\,\mathrm{d}x.
\end{aligned} ∫ u ℓ ∂ v ψ d x = h ↓ 0 lim ∫ u ℓ ( x ) h ψ ( x ) − ψ ( x − h v ) d x = h ↓ 0 lim ∫ h u ℓ ( x ) − u ℓ ( x + h v ) ψ ( x ) d x = − h ↓ 0 lim ∫ ψ ( x ) h u ℓ ( x + h v ) − u ℓ ( x ) d x . translate the second integral Consequently, ∣ T ℓ , v ( ψ ) ∣ ≤ lim inf h ↓ 0 ∫ φ ( x ) ∣ u ℓ ( x + h v ) − u ℓ ( x ) ∣ h − 1 d x |T_{\ell,v}(\psi)|\le\liminf_{h\downarrow0}\int\varphi(x)|u_\ell(x+hv)-u_\ell(x)|h^{-1}\,\mathrm{d}x ∣ T ℓ , v ( ψ ) ∣ ≤ lim inf h ↓ 0 ∫ φ ( x ) ∣ u ℓ ( x + h v ) − u ℓ ( x ) ∣ h − 1 d x ψ \psi ψ V v ( u ℓ ; φ ) V_v(u_\ell;\varphi) V v ( u ℓ ; φ ) h ↓ 0 h\downarrow0 h ↓ 0
1 2 ∑ ℓ ∣ u ℓ ( x + h v ) − u ℓ ( x ) ∣ = 1 [ C ( x + h v ) ≠ C ( x ) ] . \frac{1}{2}\sum_\ell|u_\ell(x+hv)-u_\ell(x)|=\mathbf{1}[C(x+hv)\ne C(x)]. 2 1 ℓ ∑ ∣ u ℓ ( x + h v ) − u ℓ ( x ) ∣ = 1 [ C ( x + h v ) = C ( x )] . Now take v = e i − e j v=e_i-e_j v = e i − e j d ( x , x + h v ) = h d(x,x+hv)=h d ( x , x + h v ) = h C C C Ω \Omega Ω v v v φ \varphi φ
E [ 1 2 ∑ ℓ V v ( u ℓ ; φ ) ] ≤ E [ lim inf h ↓ 0 1 2 ∑ ℓ ∫ φ ( x ) ∣ u ℓ ( x + h v ) − u ℓ ( x ) ∣ h d x ] : the pathwise bounds ≤ lim inf h ↓ 0 E [ 1 2 ∑ ℓ ∫ φ ( x ) ∣ u ℓ ( x + h v ) − u ℓ ( x ) ∣ h d x ] : Fatou = lim inf h ↓ 0 1 h ∫ φ ( x ) P [ C ( x + h v ) ≠ C ( x ) ] d x : Tonelli and two indicators ≤ α ∫ Ω φ d x : the approximation factor. (19) \begin{aligned}
\mathbb{E}\left[\frac{1}{2}\sum_{\ell}V_v(u_\ell;\varphi)\right]
&\leq\mathbb{E}\left[\liminf_{h\downarrow0}\frac{1}{2}\sum_{\ell}\int\varphi(x)\frac{\lvert u_\ell(x+hv)-u_\ell(x)\rvert}{h}\,dx\right] &&\text{: the pathwise bounds}\\
&\leq\liminf_{h\downarrow0}\mathbb{E}\left[\frac{1}{2}\sum_{\ell}\int\varphi(x)\frac{\lvert u_\ell(x+hv)-u_\ell(x)\rvert}{h}\,dx\right] &&\text{: Fatou}\\
&= \liminf_{h\downarrow0}\frac{1}{h}\int\varphi(x)\mathbb{P}[C(x+hv)\ne C(x)]\,dx &&\text{: Tonelli and two indicators}\\
&\leq\alpha\int_{\Omega}\varphi\,dx &&\text{: the approximation factor.} \tag*{(19)}
\end{aligned} E [ 2 1 ℓ ∑ V v ( u ℓ ; φ ) ] ≤ E [ h ↓ 0 lim inf 2 1 ℓ ∑ ∫ φ ( x ) h ∣ u ℓ ( x + h v ) − u ℓ ( x )∣ d x ] ≤ h ↓ 0 lim inf E [ 2 1 ℓ ∑ ∫ φ ( x ) h ∣ u ℓ ( x + h v ) − u ℓ ( x )∣ d x ] = h ↓ 0 lim inf h 1 ∫ φ ( x ) P [ C ( x + h v ) = C ( x )] d x ≤ α ∫ Ω φ d x : the pathwise bounds : Fatou : Tonelli and two indicators : the approximation factor. (19) The supremum was bounded for each realization before taking the expectation. No exchange of expectation and supremum is used.
Choose continuous compactly supported weights 0 ≤ φ n ↑ 1 0\leq\varphi_n\uparrow1 0 ≤ φ n ↑ 1 φ n \varphi_n φ n (19) give
E [ 1 2 ∑ ℓ sup φ ∈ C c ( int Ω ) 0 ≤ φ ≤ 1 V v ( u ℓ ; φ ) ] = lim n → ∞ E [ 1 2 ∑ ℓ V v ( u ℓ ; φ n ) ] ≤ α ∫ Ω 1 d x < ∞ . \mathbb{E}\left[\frac{1}{2}\sum_{\ell}\sup_{\substack{\varphi\in C_c(\operatorname{int}\Omega)\\0\leq\varphi\leq1}}V_v(u_\ell;\varphi)\right]
=\lim_{n\to\infty}\mathbb{E}\left[\frac{1}{2}\sum_{\ell}V_v(u_\ell;\varphi_n)\right]
\leq\alpha\int_{\Omega}1\,dx<\infty. E 2 1 ℓ ∑ φ ∈ C c ( int Ω ) 0 ≤ φ ≤ 1 sup V v ( u ℓ ; φ ) = n → ∞ lim E [ 2 1 ℓ ∑ V v ( u ℓ ; φ n ) ] ≤ α ∫ Ω 1 d x < ∞. A nonnegative quantity with finite expectation is finite almost surely. There are finitely many labels, faces, and directions e i − e j e_i-e_j e i − e j
On that event each functional satisfies ∣ T ℓ , v ( ψ ) ∣ ≤ ∥ ψ ∥ ∞ sup 0 ≤ φ ≤ 1 V v ( u ℓ ; φ ) \lvert T_{\ell,v}(\psi)\rvert\leq\|\psi\|_\infty\sup_{0\leq\varphi\leq1}V_v(u_\ell;\varphi) ∣ T ℓ , v ( ψ )∣ ≤ ∥ ψ ∥ ∞ sup 0 ≤ φ ≤ 1 V v ( u ℓ ; φ ) T ℓ , v T_{\ell,v} T ℓ , v C c 1 ( int Ω ) C_c^1(\operatorname{int}\Omega) C c 1 ( int Ω ) [1 Theorem 1.54] then supplies a unique finite signed measure m ℓ , v m_{\ell,v} m ℓ , v T ℓ , v ( ψ ) = ∫ ψ d m ℓ , v T_{\ell,v}(\psi)=\int\psi\,dm_{\ell,v} T ℓ , v ( ψ ) = ∫ ψ d m ℓ , v e i − e j e_i-e_j e i − e j V S V_S V S m ℓ m_\ell m ℓ u ℓ ∈ B V ( int Ω ) u_\ell\in BV(\operatorname{int}\Omega) u ℓ ∈ B V ( int Ω ) Fact 5.5 , C C C Ω \Omega Ω
On the same event, V v ( u ℓ ; φ ) = ∫ φ d ∣ m ℓ , v ∣ V_v(u_\ell;\varphi)=\int\varphi\,d\lvert m_{\ell,v}\rvert V v ( u ℓ ; φ ) = ∫ φ d ∣ m ℓ , v ∣ (17) turn (19) into
E [ ∫ φ d μ i j S ( C ) ] ≤ α ∫ Ω φ d x \mathbb{E}\left[\int\varphi\,d\mu_{ij}^{S}(C)\right]\leq\alpha\int_{\Omega}\varphi\,dx E [ ∫ φ d μ ij S ( C ) ] ≤ α ∫ Ω φ d x for continuous compactly supported φ ≥ 0 \varphi\geq0 φ ≥ 0 A ⊆ int Ω A\subseteq\operatorname{int}\Omega A ⊆ int Ω 1 [ A ] \mathbf{1}[A] 1 [ A ] E [ μ i j S ( C ) ( A ) ] ≤ α ∫ A 1 d x \mathbb{E}[\mu_{ij}^{S}(C)(A)]\leq\alpha\int_A1\,dx E [ μ ij S ( C ) ( A )] ≤ α ∫ A 1 d x A A A φ ≥ 0 \varphi\geq0 φ ≥ 0 (18) .
For (iii), the set Z S Z_S Z S φ = 1 [ Z S ] \varphi=\mathbf{1}[Z_S] φ = 1 [ Z S ] (18) gives 0 ≤ E [ μ i j S ( C ) ( Z S ) ] ≤ 0 0\leq\mathbb{E}[\mu_{ij}^{S}(C)(Z_S)]\leq0 0 ≤ E [ μ ij S ( C ) ( Z S )] ≤ 0 μ i j S ( C ) ( Z S ) \mu_{ij}^{S}(C)(Z_S) μ ij S ( C ) ( Z S ) w i j S w_{ij}^{S} w ij S φ = w i j S \varphi=w_{ij}^{S} φ = w ij S (18) , summed over i < j i<j i < j E [ cost S ( C ) ] \mathbb{E}[\operatorname{cost}^{S}(C)] E [ cost S ( C )]
Measurability. Exhaust the interior by a countable family of compact sets and, for each, choose a countable dense subset of its admissible tests in the C 1 C^1 C 1
The bound (18) concerns expectations only, as the uniform-t t t
The capacity condition bounds the normal difference of one pair of label flows by the combined directional crossing cost for that same normal. To use it we need the derivative measures of all the indicators to be carried by one common interface with exactly two neighboring labels and one normal at almost every point, so that the flux and every directional crossing measure refer to the same geometry. The structure theory of partitions into sets of finite perimeter provides precisely this representation. The following is an adapted consequence of De Giorgi’s structure theorem [1 Theorem 3.59] and the local structure of Caccioppoli partitions [1 Theorem 4.17] .
Fact 5.7 (Two-label structure of a finite-variation cut). Fix the open interior int Ω \operatorname{int}\Omega int Ω d d d C : int Ω → S ∪ { ∗ } C:\operatorname{int}\Omega\to S\cup\{\ast\} C : int Ω → S ∪ { ∗ } u ℓ = 1 [ C = ℓ ] u_\ell=\mathbf{1}[C=\ell] u ℓ = 1 [ C = ℓ ] B V ( int Ω ) BV(\operatorname{int}\Omega) B V ( int Ω ) m ℓ m_\ell m ℓ J ⊆ int Ω J\subseteq\operatorname{int}\Omega J ⊆ int Ω σ ( J ) \sigma(J) σ ( J ) ℓ + , ℓ − \ell^+,\ell^- ℓ + , ℓ − J J J n n n J J J ℓ + \ell^+ ℓ + J J J σ \sigma σ x ∈ J x\in J x ∈ J
lim r → 0 ∫ B ( 0 , 1 ) ∣ u ℓ ± ( x ) ( x + r z ) − 1 [ ± z ⋅ n ( x ) > 0 ] ∣ d z = 0 , \lim_{r\to0}\int_{B(0,1)}\left|u_{\ell^\pm(x)}(x+rz)-\mathbf{1}[\pm z\cdot n(x)>0]\right|\,\mathrm{d}z=0, r → 0 lim ∫ B ( 0 , 1 ) u ℓ ± ( x ) ( x + r z ) − 1 [ ± z ⋅ n ( x ) > 0 ] d z = 0 , the ball and the normal being taken in the fixed coordinates, while every other label’s indicator tends to zero in the same sense. For every label ℓ \ell ℓ A ⊆ int Ω A\subseteq\operatorname{int}\Omega A ⊆ int Ω
m ℓ ( A ) = ∫ J ∩ A ( 1 [ ℓ = ℓ + ] − 1 [ ℓ = ℓ − ] ) n d σ . (20) m_\ell(A)=\int_{J\cap A}\left(\mathbf{1}[\ell=\ell^+]-\mathbf{1}[\ell=\ell^-]\right)n\,\mathrm{d}\sigma. \tag*{(20)} m ℓ ( A ) = ∫ J ∩ A ( 1 [ ℓ = ℓ + ] − 1 [ ℓ = ℓ − ] ) n d σ . (20) Equivalently, every compactly supported continuously differentiable vector field G G G int Ω \operatorname{int}\Omega int Ω
∫ int Ω u ℓ div G d x = − ∫ J ( 1 [ ℓ = ℓ + ] − 1 [ ℓ = ℓ − ] ) n ⋅ G d σ . \int_{\operatorname{int}\Omega}u_\ell\operatorname{div}G\,\mathrm{d}x=-\int_J\left(\mathbf{1}[\ell=\ell^+]-\mathbf{1}[\ell=\ell^-]\right)n\cdot G\,\mathrm{d}\sigma. ∫ int Ω u ℓ div G d x = − ∫ J ( 1 [ ℓ = ℓ + ] − 1 [ ℓ = ℓ − ] ) n ⋅ G d σ . De Giorgi’s theorem supplies the surface representation and the half-space limits for each set of finite perimeter, and the partition theorem says that almost every point of these surfaces belongs to exactly two label boundaries, with opposite normals. Their union, minus the exceptional null set, is J J J J ∩ A J\cap A J ∩ A (20) counts only the part of A A A J J J (20) are n n n ℓ + \ell^+ ℓ + − n -n − n ℓ − \ell^- ℓ − n ⋅ F ℓ + − n ⋅ F ℓ − n\cdot F_{\ell^+}-n\cdot F_{\ell^-} n ⋅ F ℓ + − n ⋅ F ℓ − 1 2 ( ∣ n ⋅ v ∣ + ∣ − n ⋅ v ∣ ) = ∣ n ⋅ v ∣ \frac{1}{2}(|n\cdot v|+|-n\cdot v|)=|n\cdot v| 2 1 ( ∣ n ⋅ v ∣ + ∣ − n ⋅ v ∣ ) = ∣ n ⋅ v ∣ A ⊆ int Ω A\subseteq\operatorname{int}\Omega A ⊆ int Ω v v v F ℓ F_\ell F ℓ
μ v ( C ) ( A ) = ∫ J ∩ A ∣ n ⋅ v ∣ d σ , \mu_v(C)(A)=\int_{J\cap A}|n\cdot v|\,\mathrm{d}\sigma, μ v ( C ) ( A ) = ∫ J ∩ A ∣ n ⋅ v ∣ d σ , ∑ ℓ ∫ A F ℓ ⋅ d m ℓ = ∫ J ∩ A n ⋅ ( F ℓ + − F ℓ − ) d σ . (21) \sum_\ell\int_A F_\ell\cdot\mathrm{d}m_\ell=\int_{J\cap A}n\cdot(F_{\ell^+}-F_{\ell^-})\,\mathrm{d}\sigma. \tag*{(21)} ℓ ∑ ∫ A F ℓ ⋅ d m ℓ = ∫ J ∩ A n ⋅ ( F ℓ + − F ℓ − ) d σ . (21) where the vector-measure integral in the second line is the sum of the integrals of each component of the field against the corresponding coordinate measure.
These are the cost and flux descriptions of the same interface, since all directions see the same two labels and the same normal, and the capacity condition compares the two integrands pointwise. We combine (21) with Lemma 5.6 (iii). Since the directions e i − e j e_i-e_j e i − e j ∑ i < j ∣ n ⋅ ( e i − e j ) ∣ \sum_{i<j}|n\cdot(e_i-e_j)| ∑ i < j ∣ n ⋅ ( e i − e j ) ∣ c S c_S c S
σ ( J ∩ Z S ) ≤ c S − 1 ∑ i < j μ i j S ( C ) ( Z S ) = 0 and E [ σ ( J ) ] ≤ c S − 1 ∑ i < j E [ μ i j S ( C ) ( int Ω S ) ] < ∞ , \sigma(J\cap Z_S)\le c_S^{-1}\sum_{i<j}\mu_{ij}^{S}(C)(Z_S)=0
\quad\text{and}\quad
\mathbb{E}[\sigma(J)]\le c_S^{-1}\sum_{i<j}\mathbb{E}[\mu_{ij}^{S}(C)(\operatorname{int}\Omega_S)]<\infty, σ ( J ∩ Z S ) ≤ c S − 1 i < j ∑ μ ij S ( C ) ( Z S ) = 0 and E [ σ ( J )] ≤ c S − 1 i < j ∑ E [ μ ij S ( C ) ( int Ω S )] < ∞ , and by (20) also ∣ m ℓ ∣ ( Z S ) = 0 |m_\ell|(Z_S)=0 ∣ m ℓ ∣ ( Z S ) = 0 ∣ m ℓ ∣ |m_\ell| ∣ m ℓ ∣
Recovering the Boundary Labels
Fact 5.7 concerns interfaces in the open interior and tests only compactly supported vector fields. It does not identify the labels that C C C ∂ Ω S \partial\Omega_S ∂ Ω S (11) and in the cancellation between faces of Lemma 5.2 . The counterexample after Lemma 5.3 shows that interior information alone cannot determine them. The next identity supplies the connection, in expectation, using the approximation factor. Integration by parts first yields an interior expression, and the approximation factor makes the probability of disagreement between a boundary point and a nearby interior point tend to zero at a controlled rate. A normalized collar integral then recovers the selected flux with the actual boundary labels.
Lemma 5.8 (Boundary-flux identity). Let C C C Δ q \Delta_q Δ q α \alpha α S S S ∣ S ∣ ≥ 2 |S|\ge2 ∣ S ∣ ≥ 2 F ℓ S F_\ell^S F ℓ S Ω S \Omega_S Ω S C C C Ω S \Omega_S Ω S Fact 5.7 provides an interface J J J ℓ ± \ell^\pm ℓ ± n n n
E [ Λ S ( C ) ] = E [ ∫ J n ⋅ ( F ℓ + S − F ℓ − S ) d σ ] . (22) \mathbb{E}[\Lambda_S(C)]=\mathbb{E}\left[\int_J n\cdot(F_{\ell^+}^S-F_{\ell^-}^S)\,d\sigma\right]. \tag*{(22)} E [ Λ S ( C )] = E [ ∫ J n ⋅ ( F ℓ + S − F ℓ − S ) d σ ] . (22) Proof. Write Ω = Ω S \Omega=\Omega_S Ω = Ω S F ℓ = F ℓ S F_\ell=F_\ell^S F ℓ = F ℓ S Z = Z S Z=Z_S Z = Z S F C ( x ) = F C ( x ) ( x ) F_C(x)=F_{C(x)}(x) F C ( x ) = F C ( x ) ( x ) Lemma 5.6 (i), and σ ( J ∩ Z ) = 0 \sigma(J\cap Z)=0 σ ( J ∩ Z ) = 0 ∣ m ℓ ∣ ( Z ) = 0 |m_\ell|(Z)=0 ∣ m ℓ ∣ ( Z ) = 0 (21) . Work in the fixed coordinates of § 5.3 .
Cutoff. For each facet f f f Ω \Omega Ω a f ( x ) a_f(x) a f ( x ) s ( x ) = min f a f ( x ) s(x)=\min_f a_f(x) s ( x ) = min f a f ( x ) χ δ = min ( 1 , max ( 0 , s / δ − 1 ) ) \chi_\delta=\min(1,\max(0,s/\delta-1)) χ δ = min ( 1 , max ( 0 , s / δ − 1 )) δ \delta δ 2 δ 2\delta 2 δ G ℓ = χ δ F ℓ G_\ell=\chi_\delta F_\ell G ℓ = χ δ F ℓ div G ℓ = χ δ div F ℓ + F ℓ ⋅ ∇ χ δ \operatorname{div}G_\ell=\chi_\delta\operatorname{div}F_\ell+F_\ell\cdot\nabla\chi_\delta div G ℓ = χ δ div F ℓ + F ℓ ⋅ ∇ χ δ G ℓ G_\ell G ℓ χ δ \chi_\delta χ δ (12) to ψ G ℓ \psi G_\ell ψ G ℓ ψ ∈ C c 1 ( int Ω ) \psi\in C_c^1(\operatorname{int}\Omega) ψ ∈ C c 1 ( int Ω )
∫ G ℓ ⋅ ∇ ψ d x = − ∫ ψ ( χ δ div F ℓ + F ℓ ⋅ ∇ χ δ ) d x . \int G_\ell\cdot\nabla\psi\,dx=-\int\psi(\chi_\delta\operatorname{div}F_\ell+F_\ell\cdot\nabla\chi_\delta)\,dx. ∫ G ℓ ⋅ ∇ ψ d x = − ∫ ψ ( χ δ div F ℓ + F ℓ ⋅ ∇ χ δ ) d x . Thus, the displayed bounded, cellwise function is also the distributional divergence of G ℓ G_\ell G ℓ
Mollification. Choose a nonnegative smooth ρ \rho ρ ∫ ρ d x = 1 \int\rho\,dx=1 ∫ ρ d x = 1 ρ η ( z ) = η − d ρ ( z / η ) \rho_\eta(z)=\eta^{-d}\rho(z/\eta) ρ η ( z ) = η − d ρ ( z / η ) G ℓ G_\ell G ℓ Ω \Omega Ω G ℓ , η ( x ) = ∫ ρ η ( z ) G ℓ ( x − z ) d z G_{\ell,\eta}(x)=\int\rho_\eta(z)G_\ell(x-z)\,dz G ℓ , η ( x ) = ∫ ρ η ( z ) G ℓ ( x − z ) d z 0 < η < δ / 2 0<\eta<\delta/2 0 < η < δ /2 η \eta η G ℓ , η G_{\ell,\eta} G ℓ , η int Ω \operatorname{int}\Omega int Ω Fact 5.7 gives
∫ ψ ℓ div G ℓ , η d x = − ∫ G ℓ , η ⋅ d m ℓ . \int\psi_\ell\operatorname{div}G_{\ell,\eta}\,dx=-\int G_{\ell,\eta}\cdot dm_\ell. ∫ ψ ℓ div G ℓ , η d x = − ∫ G ℓ , η ⋅ d m ℓ . The divergence of G ℓ , η G_{\ell,\eta} G ℓ , η div G ℓ \operatorname{div} G_\ell div G ℓ L 1 L^1 L 1 η ↓ 0 \eta\downarrow0 η ↓ 0 0 ≤ u ℓ ≤ 1 0 \le u_\ell\le1 0 ≤ u ℓ ≤ 1 ∫ u ℓ div G ℓ d x \int u_\ell\operatorname{div} G_\ell\,dx ∫ u ℓ div G ℓ d x Z Z Z G ℓ G_\ell G ℓ G ℓ , η ( x ) → G ℓ ( x ) G_{\ell,\eta}(x) \to G_\ell(x) G ℓ , η ( x ) → G ℓ ( x ) ∥ G ℓ , η ( x ) ∥ ≤ sup x ∥ G ℓ ( x ) ∥ \lVert G_{\ell,\eta}(x)\rVert\le\sup_x\lVert G_\ell(x)\rVert ∥ G ℓ , η ( x )∥ ≤ sup x ∥ G ℓ ( x )∥ ∣ m ℓ ∣ \lvert m_\ell\rvert ∣ m ℓ ∣ ∣ m ℓ ∣ ( Z ) = 0 \lvert m_\ell\rvert(Z)=0 ∣ m ℓ ∣ ( Z ) = 0 (21) ,
∫ χ δ div F C d x + ∫ F C ⋅ ∇ χ δ d x = − ∫ J χ δ n ⋅ ( F ℓ + − F ℓ − ) d σ . (23) \int\chi_\delta\operatorname{div} F_C\,dx+\int F_C\cdot\nabla\chi_\delta\,dx=-\int_J\chi_\delta n\cdot(F_{\ell+}-F_{\ell-})\,d\sigma. \tag*{(23)} ∫ χ δ div F C d x + ∫ F C ⋅ ∇ χ δ d x = − ∫ J χ δ n ⋅ ( F ℓ + − F ℓ − ) d σ . (23) Limits. As δ ↓ 0 \delta\downarrow0 δ ↓ 0 E [ ∫ Ω div F C d x ] \mathbb{E}\left[\int_\Omega\operatorname{div}F_C\,dx\right] E [ ∫ Ω div F C d x ] Ω \Omega Ω − E [ ∫ J n ⋅ ( F ℓ + − F ℓ − ) d σ ] -\mathbb{E}\left[\int_J n\cdot(F_{\ell+}-F_{\ell-})\,d\sigma\right] − E [ ∫ J n ⋅ ( F ℓ + − F ℓ − ) d σ ] 2 sup ℓ , x ∥ F ℓ ( x ) ∥ σ ( J ) 2\sup_{\ell,x}\lVert F_\ell(x)\rVert\sigma(J) 2 sup ℓ , x ∥ F ℓ ( x )∥ σ ( J )
Collar. Where f f f a f a_f a f δ < a f < 2 δ \delta<a_f<2\delta δ < a f < 2 δ − ∇ χ δ = n f / δ -\nabla\chi_\delta=n_f/\delta − ∇ χ δ = n f / δ n f n_f n f f f f x = y − t n f x=y-tn_f x = y − t n f y ∈ f y\in f y ∈ f δ < t < 2 δ \delta<t<2\delta δ < t < 2 δ d σ ( y ) d t d\sigma(y)\,dt d σ ( y ) d t f f f O ( δ ) O(\delta) O ( δ ) f f f K δ K_\delta K δ [ y , y − 2 δ n f ] [y,y-2\delta n_f] [ y , y − 2 δ n f ] f f f δ \delta δ f f f f f f O ( δ ) O(\delta) O ( δ ) 1 / δ 1/\delta 1/ δ
Inside a cell let K K K M M M c f c_f c f ℓ 1 \ell_1 ℓ 1 n f n_f n f V S V_S V S d ( y − t n f , y ) = c f t d(y-tn_f,y)=c_ft d ( y − t n f , y ) = c f t y ∈ K δ y\in K_\delta y ∈ K δ P [ C ( y − t n f ) ≠ C ( y ) ] ≤ α d ( y − t n f , y ) = c f α t \mathbb{P}[C(y-tn_f)\ne C(y)]\le\alpha\,d(y-tn_f,y)=c_f\alpha t P [ C ( y − t n f ) = C ( y )] ≤ α d ( y − t n f , y ) = c f α t y − t n f y-tn_f y − t n f y y y C ( y − t n f ) C(y-tn_f) C ( y − t n f ) y y y K t Kt K t 2 M 2M 2 M
E [ ∣ ν f ( F C ( y − t n f ) ( y − t n f ) ) − ν f ( F C ( y ) ( y ) ) ∣ ] ≤ K t + 2 M P [ C ( y − t n f ) ≠ C ( y ) ] ≤ ( K + 2 M c f α ) t . \mathbb{E}\left[\left|\nu_f\left(F_{C(y-tn_f)}(y-tn_f)\right)-\nu_f\left(F_{C(y)}(y)\right)\right|\right]\le Kt+2M\mathbb{P}[C(y-tn_f)\ne C(y)]\le(K+2Mc_f\alpha)t. E [ ν f ( F C ( y − t n f ) ( y − t n f ) ) − ν f ( F C ( y ) ( y ) ) ] ≤ K t + 2 M P [ C ( y − t n f ) = C ( y )] ≤ ( K + 2 M c f α ) t . Averaging over the collar,
1 δ ∫ δ 2 δ ∫ K δ E [ ∣ ν f ( F C ( y − t n f ) ( y − t n f ) ) − ν f ( F C ( y ) ( y ) ) ∣ ] d σ ( y ) d t ≤ σ ( f ) ( K + 2 M c f α ) δ ∫ δ 2 δ t d t = O ( δ ) . \frac{1}{\delta}\int_\delta^{2\delta}\int_{K_\delta}\mathbb{E}\left[\left|\nu_f\left(F_{C(y-tn_f)}(y-tn_f)\right)-\nu_f\left(F_{C(y)}(y)\right)\right|\right]\,d\sigma(y)\,dt\le\frac{\sigma(f)(K+2Mc_f\alpha)}{\delta}\int_\delta^{2\delta}t\,dt=O(\delta). δ 1 ∫ δ 2 δ ∫ K δ E [ ν f ( F C ( y − t n f ) ( y − t n f ) ) − ν f ( F C ( y ) ( y ) ) ] d σ ( y ) d t ≤ δ σ ( f ) ( K + 2 M c f α ) ∫ δ 2 δ t d t = O ( δ ) . Together with the discarded strips, this proves
− E [ ∫ Ω F C ⋅ ∇ χ δ d x ] ⟶ E [ ∫ ∂ Ω ν Ω ( F C ( y ) ( y ) ) d σ ( y ) ] . -\mathbb{E}\left[\int_\Omega F_C\cdot\nabla\chi_\delta\,dx\right]\longrightarrow\mathbb{E}\left[\int_{\partial\Omega}\nu_\Omega(F_{C(y)}(y))\,d\sigma(y)\right]. − E [ ∫ Ω F C ⋅ ∇ χ δ d x ] ⟶ E [ ∫ ∂ Ω ν Ω ( F C ( y ) ( y )) d σ ( y ) ] . In dimension one, facets are endpoints, σ \sigma σ δ \delta δ (23) proves (22) . □ \square □
The three hypotheses play separate roles. Normal continuity cancels the artificial flux that the cell walls would otherwise contribute to the distributional divergence. The zero crossing mass on the walls, Lemma 5.6 (iii), permits the piecewise argument and the passage to the limit against m ℓ m_\ell m ℓ C C C (22) deliberately uses those labels.
One Face and Expected Cost
The second inequality of the chain compares, face by face, the selected flux with the cost.
Lemma 5.9 (One face). Suppose the label flows on Ω S \Omega_S Ω S C C C Δ q \Delta_q Δ q
E [ Λ S ( C ) ] ≤ E [ cost S ( C ) ] . \mathbb{E}[\Lambda_S(C)] \le\mathbb{E}[\operatorname{cost}_S(C)]. E [ Λ S ( C )] ≤ E [ cost S ( C )] . Proof. On Ω S \Omega_S Ω S S ∪ { ∗ } S \cup\{\ast\} S ∪ { ∗ } C C C J J J σ ( J ∩ Z S ) = 0 \sigma(J \cap Z_S) = 0 σ ( J ∩ Z S ) = 0 Lemma 5.6 and the remark after (21) . At a point of J ∖ Z S J \setminus Z_S J ∖ Z S ℓ ± \ell^\pm ℓ ± Lemma 5.1 with z = F ℓ + S − F ℓ − S z = F_{\ell_+}^S - F_{\ell_-}^S z = F ℓ + S − F ℓ − S ν \nu ν n n n (15) there. Hence,
E [ Λ S ( C ) ] = E [ ∫ J n ⋅ ( F ℓ + S − F ℓ − S ) d σ ] (Lemma 5.8) ≤ E [ ∫ J ∑ i < j ∈ S w i j S ∣ n ⋅ ( e i − e j ) ∣ d σ ] (capacity and Lemma 5.1) = E [ ∑ i < j ∈ S ∫ int Ω S w i j S d μ i j S ( C ) ] (xref‘(20)‘) = E [ cost S ( C ) ] (Definition 5.4). \begin{aligned}
\mathbb{E}[\Lambda_S(C)]
&= \mathbb{E}\left[\int_J n \cdot\left(F_{\ell_+}^S-F_{\ell_-}^S\right)\,d\sigma\right]
&&\text{(Lemma 5.8)}\\
&\le\mathbb{E}\left[\int_J \sum_{i<j\in S}w_{ij}^S\lvert n\cdot(e_i-e_j)\rvert\,d\sigma\right]
&&\text{(capacity and Lemma 5.1)}\\
&= \mathbb{E}\left[\sum_{i<j\in S}\int_{\operatorname{int}\Omega_S}w_{ij}^S\,d\mu_{ij}^S(C)\right]
&&\text{({xref}`(20)`)}\\
&= \mathbb{E}[\operatorname{cost}_S(C)]
&&\text{(Definition 5.4).}
\end{aligned} E [ Λ S ( C )] = E [ ∫ J n ⋅ ( F ℓ + S − F ℓ − S ) d σ ] ≤ E ∫ J i < j ∈ S ∑ w ij S ∣ n ⋅ ( e i − e j )∣ d σ = E i < j ∈ S ∑ ∫ int Ω S w ij S d μ ij S ( C ) = E [ cost S ( C )] (Lemma 5.8) (capacity and Lemma 5.1) ( xref ‘(20)‘) (Definition 5.4). Weights and flows may have different values on cell facets, but those facets carry no crossing mass and no interface, so the pointwise comparison on J ∖ Z S J \setminus Z_S J ∖ Z S
The third inequality of the chain uses the approximation factor alone, through Lemma 5.6 (ii) for the interior edges and directly for the terminal edges.
Lemma 5.10 (Expected cost). Let a weighting have fractional cost L L L C C C Δ q \Delta_q Δ q α \alpha α E [ cost ( C ) ] ≤ α L \mathbb{E}[\operatorname{cost}(C)] \le\alpha L E [ cost ( C )] ≤ α L
Proof. For each S S S Lemma 5.6 (iii) gives E [ cost S ( C ) ] ≤ α ∑ i < j ∈ S ∫ Ω S w i j S d x \mathbb{E}[\operatorname{cost}_S(C)] \le\alpha\sum_{i<j\in S}\int_{\Omega_S}w_{ij}^S\,dx E [ cost S ( C )] ≤ α ∑ i < j ∈ S ∫ Ω S w ij S d x y ∈ Φ i S y \in\Phi_i^S y ∈ Φ i S d ( y , e i ) = 1 − T d(y,e_i)=1-T d ( y , e i ) = 1 − T C ( e i ) = i C(e_i)=i C ( e i ) = i P [ C ( y ) ≠ i ] ≤ α ( 1 − T ) \mathbb{P}[C(y)\ne i]\le\alpha(1-T) P [ C ( y ) = i ] ≤ α ( 1 − T ) E [ cost t e r m ( C ) ] ≤ α ( 1 − T ) B \mathbb{E}[\operatorname{cost}_{\rm term}(C)]\le\alpha(1-T)B E [ cost term ( C )] ≤ α ( 1 − T ) B (8) gives the claim.
With the three lemmas proved, the proof of Theorem 3.4 in § 3.3 is complete.
The bound of Theorem 3.4 can only improve when q q q
Proposition 5.11 (Zero extension). A flow instance on Δ q \Delta_q Δ q Δ q ′ \Delta_{q'} Δ q ′ q ′ ≥ q q' \ge q q ′ ≥ q B B B R R R L L L
Proof. For S ⊆ [ q ′ ] S \subseteq[q'] S ⊆ [ q ′ ] S ⊈ [ q ] S \not\subseteq[q] S ⊆ [ q ] P S = { Ω S } P_S=\{\Omega_S\} P S = { Ω S } w i j S = 0 w_{ij}^S=0 w ij S = 0 g i S = 0 g_i^S=0 g i S = 0 F ℓ S = 0 F_\ell^S=0 F ℓ S = 0 ϵ S = 0 \epsilon_S=0 ϵ S = 0 U ⊆ [ q ] U \subseteq[q] U ⊆ [ q ] U ∪ { j } U\cup\{j\} U ∪ { j } j ∉ [ q ] j\notin[q] j ∈ / [ q ] U ⊈ [ q ] U\not\subseteq[q] U ⊆ [ q ] B B B R R R L L L
§ 6 , § 7 and § 7.8 apply the theorem to the two flow instances of § 3.4 .
Affine Flow Instances
We show how to extend the flow instance of § 4 into a family of instances for every q q q T T T affine . Every truncated face is a single cell, the label flows point toward the terminal from a point that moves affinely with x x x Theorem 3.5 .
Theorem 6.1 (Affine flow instances). Fix q ≥ 2 q \ge2 q ≥ 2 T ∈ ( 1 / 2 , 1 ) T \in(1/2,1) T ∈ ( 1/2 , 1 ) 2 ≤ r ≤ q 2 \le r \le q 2 ≤ r ≤ q
a r = ( r T − 1 ) ( r − 2 ) ! ( q − r ) ! T r − 2 q ! . (24) a_r = \frac{(rT-1)(r-2)!(q-r)!}{T^{r-2}q!}. \tag*{(24)} a r = T r − 2 q ! ( r T − 1 ) ( r − 2 )! ( q − r )! . (24) For every S ⊆ [ q ] S \subseteq[q] S ⊆ [ q ] r = ∣ S ∣ ≥ 2 r = |S| \ge2 r = ∣ S ∣ ≥ 2 Ω S \Omega_S Ω S
p s S ( x ) = T − x s r T − 1 for s ∈ S , F i S ( x ) = a r ( e i − p S ( x ) ) for i ∈ S , F ∗ S = 0 , p_s^S(x) = \frac{T-x_s}{rT-1}\text{ for }s \in S,\qquad F_i^S(x) = a_r(e_i-p^S(x))\text{ for }i \in S,\qquad F_*^S=0, p s S ( x ) = r T − 1 T − x s for s ∈ S , F i S ( x ) = a r ( e i − p S ( x )) for i ∈ S , F ∗ S = 0 , w s t S = a r r − 1 for s < t ∈ S and g i S = a r for i ∈ S , (25) w_{st}^S = \frac{a_r}{r-1}\text{ for }s<t\in S\text{ and }g_i^S=a_r\text{ for }i\in S, \tag*{(25)} w s t S = r − 1 a r for s < t ∈ S and g i S = a r for i ∈ S , (25) with allowances ϵ U = 0 \epsilon_U=0 ϵ U = 0 U ≠ [ q ] U\ne[q] U = [ q ] ϵ [ q ] = ( q − 1 ) a q / ( q T − 1 ) \epsilon_{[q]}=(q-1)a_q/(qT-1) ϵ [ q ] = ( q − 1 ) a q / ( q T − 1 ) Δ q \Delta_q Δ q
B = ∑ r = 2 q ( r T − 1 ) z r − 2 ( r − 1 ) ! = T ( 1 − z q − 1 ( q − 1 ) ! ) , R = 1 − q ( 1 − T ) q − 1 q ! T q − 2 , B=\sum_{r=2}^{q}\frac{(rT-1)z^{r-2}}{(r-1)!}=T\left(1-\frac{z^{q-1}}{(q-1)!}\right),\qquad R=\frac{1-q(1-T)^{q-1}}{q!T^{q-2}}, B = r = 2 ∑ q ( r − 1 )! ( r T − 1 ) z r − 2 = T ( 1 − ( q − 1 )! z q − 1 ) , R = q ! T q − 2 1 − q ( 1 − T ) q − 1 , B − R = T − 1 q ! T q − 2 , L = ( 1 − T ) B + ∑ r = 2 q ( r T − 1 ) ( 1 − r ( 1 − T ) r − 1 ) 2 ( r − 1 ) ( r − 1 ) ! T r − 2 , (26) B-R=T-\frac{1}{q!T^{q-2}},\qquad L=(1-T)B+\sum_{r=2}^{q}\frac{(rT-1)(1-r(1-T)^{r-1})}{2(r-1)(r-1)!T^{r-2}}, \tag*{(26)} B − R = T − q ! T q − 2 1 , L = ( 1 − T ) B + r = 2 ∑ q 2 ( r − 1 ) ( r − 1 )! T r − 2 ( r T − 1 ) ( 1 − r ( 1 − T ) r − 1 ) , (26) where z = ( 1 − T ) / T z=(1-T)/T z = ( 1 − T ) / T
Since x s ≤ T x_s\le T x s ≤ T Ω S \Omega_S Ω S ∑ s x s = 1 \sum_s x_s=1 ∑ s x s = 1 p S ( x ) p^S(x) p S ( x ) Δ S \Delta_S Δ S p i S = 0 p_i^S=0 p i S = 0 x i = T x_i=T x i = T i i i a r a_r a r p S ( x ) p^S(x) p S ( x ) e i e_i e i q = 3 q=3 q = 3 T = 2 / 3 T=2/3 T = 2/3 4 4 4 Proposition 4.1 .
Proof. Normal continuity holds trivially, since each face is one cell.
Capacity. Let I ⊂ S I\subset S I ⊂ S P I = ∑ s ∈ I p s S ∈ [ 0 , 1 ] P_I=\sum_{s\in I}p_s^S\in[0,1] P I = ∑ s ∈ I p s S ∈ [ 0 , 1 ] ∑ s ∈ I F ℓ , s S = a r ( 1 [ ℓ ∈ I ] − P I ) \sum_{s\in I}F_{\ell,s}^S=a_r(\mathbf{1}[\ell\in I]-P_I) ∑ s ∈ I F ℓ , s S = a r ( 1 [ ℓ ∈ I ] − P I ) ℓ ∈ S \ell\in S ℓ ∈ S 0 0 0 ℓ = ∗ \ell=* ℓ = ∗ ℓ ∈ I \ell\in I ℓ ∈ I ℓ ∈ S ∖ I \ell\in S\setminus I ℓ ∈ S ∖ I ∗ * ∗ a r ( 1 − P I ) a_r(1-P_I) a r ( 1 − P I ) − a r P I -a_rP_I − a r P I 0 0 0 a r a_r a r I I I ∣ I ∣ ( r − ∣ I ∣ ) a r / ( r − 1 ) ≥ a r |I|(r-|I|)a_r/(r-1)\ge a_r ∣ I ∣ ( r − ∣ I ∣ ) a r / ( r − 1 ) ≥ a r (9) holds.
Terminal condition. On Φ i S \Phi_i^S Φ i S p i S = 0 p_i^S=0 p i S = 0 F ℓ , i S = a r 1 [ ℓ = i ] = g i S 1 [ ℓ = i ] F_{\ell,i}^S=a_r\mathbf{1}[\ell=i]=g_i^S\mathbf{1}[\ell=i] F ℓ , i S = a r 1 [ ℓ = i ] = g i S 1 [ ℓ = i ] ℓ \ell ℓ
Conservation. In every tangent direction v v v p S p^S p S − v / ( r T − 1 ) -v/(rT-1) − v / ( r T − 1 ) F i S F_i^S F i S a r v / ( r T − 1 ) a_rv/(rT-1) a r v / ( r T − 1 ) r − 1 r-1 r − 1
div F i S = ( r − 1 ) a r r T − 1 for i ∈ S . \operatorname{div}F_i^S=\frac{(r-1)a_r}{rT-1}\text{ for }i\in S. div F i S = r T − 1 ( r − 1 ) a r for i ∈ S . Let U U U r r r S = U ∪ { j } S=U\cup\{j\} S = U ∪ { j } q − r q-r q − r Ω U \Omega_U Ω U x j = 0 x_j=0 x j = 0 Ω S \Omega_S Ω S (14) is b S → U ℓ = − F ℓ , j ℓ = a r + 1 p j S = a r + 1 T / ( ( r + 1 ) T − 1 ) b^\ell_{S\to U}=-F^\ell_{\ell,j}=a_{r+1}p^S_j=a_{r+1}T/((r+1)T-1) b S → U ℓ = − F ℓ , j ℓ = a r + 1 p j S = a r + 1 T / (( r + 1 ) T − 1 ) ℓ ∈ U \ell\in U ℓ ∈ U ℓ = ∗ \ell=\ast ℓ = ∗ (24) satisfy
( q − r ) a r + 1 T ( r + 1 ) T − 1 = ( r − 1 ) a r r T − 1 for 2 ≤ r < q , (q-r)a_{r+1}\frac{T}{(r+1)T-1}=\frac{(r-1)a_r}{rT-1}\quad\text{for }2\le r<q, ( q − r ) a r + 1 ( r + 1 ) T − 1 T = r T − 1 ( r − 1 ) a r for 2 ≤ r < q , since both sides equal ( r − 1 ) ! ( q − r ) ! / ( q ! T r − 2 ) (r-1)!(q-r)!/(q!T^{r-2}) ( r − 1 )! ( q − r )! / ( q ! T r − 2 ) Ω U \Omega_U Ω U (10) holds with zero allowance for every U ≠ [ q ] U\ne[q] U = [ q ] ∗ \ast ∗ Ω [ q ] \Omega_{[q]} Ω [ q ] ( q − 1 ) a q / ( q T − 1 ) (q-1)a_q/(qT-1) ( q − 1 ) a q / ( q T − 1 )
The values. There are ( q r ) \binom{q}{r} ( r q ) r r r ( 1 − r ( 1 − T ) r − 1 ) / ( r − 1 ) ! (1-r(1-T)^{r-1})/(r-1)! ( 1 − r ( 1 − T ) r − 1 ) / ( r − 1 )! r r r ( r 2 ) \binom{r}{2} ( 2 r ) a r / ( r − 1 ) a_r/(r-1) a r / ( r − 1 ) r r r ( 1 − T ) r − 2 / ( r − 2 ) ! (1-T)^{r-2}/(r-2)! ( 1 − T ) r − 2 / ( r − 2 )! (24) gives the sums for B B B L L L R R R ( q − 1 ) a q / ( q T − 1 ) (q-1)a_q/(qT-1) ( q − 1 ) a q / ( q T − 1 ) B B B r r r T r − 2 / ( r − 2 ) ! − z r − 1 / ( r − 1 ) ! T^{r-2}/(r-2)!-z^{r-1}/(r-1)! T r − 2 / ( r − 2 )! − z r − 1 / ( r − 1 )! B − R B-R B − R
Proof of Theorem 3.5 . Take q = 10 q=10 q = 10 T = 3 / 5 T=3/5 T = 3/5 Theorem 6.1 . Substitution in (26) yields
B = 55801301 93002175 , R = 43289 2645395200 , and L = 8180229294583 16665989760000 , B=\frac{55801301}{93002175},\qquad R=\frac{43289}{2645395200},\qquad\text{and}\qquad L=\frac{8180229294583}{16665989760000}, B = 93002175 55801301 , R = 2645395200 43289 , and L = 16665989760000 8180229294583 , whose ratio ( B − R ) / L (B-R)/L ( B − R ) / L 9999320418500 / 8180229294583 = 1.2223765445 … 9999320418500/8180229294583=1.2223765445\ldots 9999320418500/8180229294583 = 1.2223765445 …
By Theorem 3.4 , every random non-opposite cut of Δ 10 \Delta_{10} Δ 10 α \alpha α α ≥ 1.2223765445 \alpha\ge1.2223765445 α ≥ 1.2223765445 lim k → ∞ G k ≥ 1.2223765445 \lim_{k\to\infty}G_k\ge1.2223765445 lim k → ∞ G k ≥ 1.2223765445
For T = 3 / 5 T=3/5 T = 3/5
Table 1.
The computer-aided flow instance of § 7.8 improves the affine construction by allowing piecewise quadratic label flows and weights on many cells, and by choosing them by linear programming, which § 7 describes next.
Finding and Verifying a Flow Instance by Linear Programming
We find the flow instance behind Theorem 1.1 by computer search, which chooses the weighting and the label flows that bound its cuts together. Note that this is different from solving the relaxation (2) , where the weights are fixed and the embedding is optimized. This section describes the family of flow instances in which we search, the linear program that finds the best one, and the finite list of integer inequalities that proves that the one found is a flow instance. § 7.8 then states the instance and completes the proof of Theorem 1.1 .
We impose two simplifying restrictions on the family we search in. The first is symmetry: we only consider flow instances that are mapped to themselves when the coordinates of Δ q \Delta_q Δ q q − 1 q-1 q − 1 § 5.1 , and on each cell every weight and every component of every label flow is a polynomial of degree at most two. A flow instance in the family is then a finite list of coefficients, and then B B B R R R L L L
The conditions of Definition 3.3 are linear in the weighting, the label flows, and the allowances, and they are homogeneous, so the flow instance of largest value in the family is found by a linear program. However, there is one challenge. The conditions must hold at every point of every cell, and at each point they are linear in the coefficients, but there are infinitely many points. We write the polynomials in the Bernstein basis, whose basis functions are nonnegative, so that an inequality between coefficients implies the same inequality at every point. This replaces every pointwise condition by finitely many linear inequalities, at the price of searching a smaller family.
Symmetric Flow Instances
Let r r r Ω S \Omega_S Ω S ∣ S ∣ = r |S| = r ∣ S ∣ = r r − 1 r - 1 r − 1 2 ≤ r ≤ q 2 \le r \le q 2 ≤ r ≤ q r r r r ! r! r ! r r r 0 , … , r − 1 0,\ldots,r-1 0 , … , r − 1
O r = { x ∈ Δ r : x 0 ≥ x 1 ≥ ⋯ ≥ x r − 1 , x 0 ≤ T } for 2 ≤ r ≤ q \mathcal{O}_r = \{x \in\Delta_r : x_0 \ge x_1 \ge\cdots\ge x_{r-1},\ x_0 \le T\}\text{ for }2 \le r \le q O r = { x ∈ Δ r : x 0 ≥ x 1 ≥ ⋯ ≥ x r − 1 , x 0 ≤ T } for 2 ≤ r ≤ q be the ordered region . It is the part of a truncated face with r r r x 0 = T x_0 = T x 0 = T equality facets x j = x j + 1 x_j = x_{j+1} x j = x j + 1 0 ≤ j ≤ r − 2 0 \le j \le r - 2 0 ≤ j ≤ r − 2 r ≥ 3 r \ge3 r ≥ 3 x r − 1 = 0 x_{r-1} = 0 x r − 1 = 0 O r − 1 \mathcal{O}_{r-1} O r − 1
For a face S ⊆ [ q ] S \subseteq[q] S ⊆ [ q ] ∣ S ∣ = r |S| = r ∣ S ∣ = r π : { 0 , … , r − 1 } → S \pi: \{0,\ldots,r-1\} \to S π : { 0 , … , r − 1 } → S copy O π = { y ∈ Ω S : y π ( 0 ) ≥ ⋯ ≥ y π ( r − 1 ) } \mathcal{O}_{\pi} = \{y \in\Omega_S : y_{\pi(0)} \ge\cdots\ge y_{\pi(r-1)}\} O π = { y ∈ Ω S : y π ( 0 ) ≥ ⋯ ≥ y π ( r − 1 ) } O r \mathcal{O}_r O r x ↦ y x \mapsto y x ↦ y y π ( s ) = x s y_{\pi(s)} = x_s y π ( s ) = x s r r r Ω S \Omega_S Ω S ∣ S ∣ = r |S| = r ∣ S ∣ = r
M r = ( q r ) r ! = q ! ( q − r ) ! M_r = \binom{q}{r}r! = \frac{q!}{(q-r)!} M r = ( r q ) r ! = ( q − r )! q ! of them, one for each face with r r r f f f O r \mathcal{O}_r O r transported to O π \mathcal{O}_{\pi} O π y ↦ f ( x ) y \mapsto f(x) y ↦ f ( x ) F i F_i F i i i i π ( i ) \pi(i) π ( i ) F π ( i ) , π ( s ) ( y ) = F i , s ( x ) F_{\pi(i),\pi(s)}(y) = F_{i,s}(x) F π ( i ) , π ( s ) ( y ) = F i , s ( x ) w s t w_{st} w s t w π ( s ) π ( t ) w_{\pi(s)\pi(t)} w π ( s ) π ( t ) g 0 g_0 g 0 x 0 = T x_0 = T x 0 = T g π ( 0 ) g_{\pi(0)} g π ( 0 ) ∗ \ast ∗
A symmetric flow instance is specified, unscaled , on each O r \mathcal{O}_r O r divided by M r M_r M r B B B R R R L L L q − 1 q - 1 q − 1 O r \mathcal{O}_r O r r r r x j = 0 x_j = 0 x j = 0 q − r q-r q − r r + 1 r+1 r + 1
M r + 1 = ( q − r ) M r , or equivalently q − r M r + 1 = 1 M r . (27) M_{r+1} = (q-r)M_r,\text{ or equivalently }\frac{q-r}{M_{r+1}} = \frac{1}{M_r}. \tag*{(27)} M r + 1 = ( q − r ) M r , or equivalently M r + 1 q − r = M r 1 . (27) For q = 4 q = 4 q = 4 r = 2 r = 2 r = 2 M 2 = 12 M_2 = 12 M 2 = 12 M 3 = 24 M_3 = 24 M 3 = 24
Lemma 7.1 (Coordinate symmetry). For 2 ≤ r ≤ q 2 \le r \le q 2 ≤ r ≤ q P ( r ) \mathcal{P}^{(r)} P ( r ) O r \mathcal{O}_r O r x r − 1 = 0 x_{r-1} = 0 x r − 1 = 0 O r \mathcal{O}_r O r P ( r − 1 ) \mathcal{P}^{(r-1)} P ( r − 1 ) O r − 1 \mathcal{O}_{r-1} O r − 1
appended. Let w s t ( r ) ≥ 0 w_{st}^{(r)} \ge0 w s t ( r ) ≥ 0 g 0 ( r ) ≥ 0 g_{0}^{(r)} \ge0 g 0 ( r ) ≥ 0 x 0 = T x_{0}=T x 0 = T F i ( r ) F_{i}^{(r)} F i ( r ) i ∈ { 0 , … , r − 1 , ∗ } i \in\{0,\ldots,r-1,*\} i ∈ { 0 , … , r − 1 , ∗ } F ∗ ( r ) = 0 F_{*}^{(r)}=0 F ∗ ( r ) = 0 ϵ ( r ) ≥ 0 \epsilon^{(r)} \ge0 ϵ ( r ) ≥ 0 O r O_{r} O r § 3.2 and § 5.1 . Transport the cells and these quantities to every copy, dividing the weights, terminal densities, label flows, and allowances by M r M_{r} M r
(i) The total terminal weight, the total allowance, and the fractional cost of the transported weighting are the unscaled sums
B = ∑ r = 2 q ∫ { x 0 = T } ∩ O r g 0 ( r ) d σ , R = ∑ r = 2 q ∫ O r ϵ ( r ) d x , L = ∑ r = 2 q ∑ s < t ∫ O r w s t ( r ) d x + ( 1 − T ) B . B=\sum_{r=2}^{q}\int_{\{x_{0}=T\}\cap O_{r}}g_{0}^{(r)}\,\mathrm{d}\sigma,\qquad R=\sum_{r=2}^{q}\int_{O_{r}}\epsilon^{(r)}\,\mathrm{d}x,\qquad L=\sum_{r=2}^{q}\sum_{s<t}\int_{O_{r}}w_{st}^{(r)}\,\mathrm{d}x+(1-T)B. B = r = 2 ∑ q ∫ { x 0 = T } ∩ O r g 0 ( r ) d σ , R = r = 2 ∑ q ∫ O r ϵ ( r ) d x , L = r = 2 ∑ q s < t ∑ ∫ O r w s t ( r ) d x + ( 1 − T ) B . (ii) For r < q r<q r < q x ∈ O r x\in O_{r} x ∈ O r O r O_{r} O r 1 / M r 1/M_{r} 1/ M r − F ℓ , r ( r + 1 ) ( x , 0 ) -F_{\ell,r}^{(r+1)}(x,0) − F ℓ , r ( r + 1 ) ( x , 0 ) O r + 1 O_{r+1} O r + 1 x r = 0 x_{r}=0 x r = 0 ℓ ∈ { 0 , … , r − 1 , ∗ } \ell\in\{0,\ldots,r-1,*\} ℓ ∈ { 0 , … , r − 1 , ∗ }
(iii) The transported quantities satisfy capacity and the terminal condition on every face if and only if the unscaled ones satisfy them on every O r O_{r} O r r r r ℓ ∈ { 0 , … , r − 1 , ∗ } \ell\in\{0,\ldots,r-1,*\} ℓ ∈ { 0 , … , r − 1 , ∗ } O r O_{r} O r
div F ℓ ( r ) ( x ) ≤ − F ℓ , r ( r + 1 ) ( x , 0 ) + ϵ ( r ) ( x ) , \operatorname{div}F_{\ell}^{(r)}(x)\le-F_{\ell,r}^{(r+1)}(x,0)+\epsilon^{(r)}(x), div F ℓ ( r ) ( x ) ≤ − F ℓ , r ( r + 1 ) ( x , 0 ) + ϵ ( r ) ( x ) , with the supply term omitted for r = q r=q r = q
Proof. Transport preserves volume and surface measure, and the copies with r r r M r M_{r} M r r r r M r M_{r} M r O r O_{r} O r y y y x x x O π O_{\pi} O π U U U ∣ U ∣ = r |U|=r ∣ U ∣ = r x x x S = U ∪ { j } S=U\cup\{j\} S = U ∪ { j } y y y O r + 1 O_{r+1} O r + 1 S S S π \pi π j j j y j = 0 y_{j}=0 y j = 0 (14) of the transported flow is − F ℓ , r ( r + 1 ) ( x , 0 ) / M r + 1 -F_{\ell,r}^{(r+1)}(x,0)/M_{r+1} − F ℓ , r ( r + 1 ) ( x , 0 ) / M r + 1 q − r q-r q − r (27) gives (ii). For (iii), capacity and the terminal condition are pointwise inequalities and equalities that are homogeneous in the quantities and covariant under the coordinate permutation. The divergence of a transported flow is the transported divergence divided by M r M_{r} M r M r M_{r} M r (10) at y y y 1 / M r 1/M_{r} 1/ M r x x x
The Cells and the Quadratic Flows
In this section d = r − 1 d=r-1 d = r − 1 r r r 2 ≤ j ≤ r 2\le j\le r 2 ≤ j ≤ r
u j = ( 1 j , … , 1 j , 0 , … , 0 ) and v j = ( T , 1 − T j − 1 , … , 1 − T j − 1 , 0 , … , 0 ) . u_{j}=\left(\frac{1}{j},\ldots,\frac{1}{j},0,\ldots,0\right)\quad\text{and}\quad v_{j}=\left(T,\frac{1-T}{j-1},\ldots,\frac{1-T}{j-1},0,\ldots,0\right). u j = ( j 1 , … , j 1 , 0 , … , 0 ) and v j = ( T , j − 1 1 − T , … , j − 1 1 − T , 0 , … , 0 ) . Since T > 1 / 2 T>1/2 T > 1/2 O r O_{r} O r
conv ( u 2 , … , u s , v s , … , v r ) for 2 ≤ s ≤ r . (28) \operatorname{conv}(u_{2},\ldots,u_{s},v_{s},\ldots,v_{r})\quad\text{for }2\le s\le r. \tag*{(28)} conv ( u 2 , … , u s , v s , … , v r ) for 2 ≤ s ≤ r . (28) For r = 2 r=2 r = 2 [ u 2 , v 2 ] [u_{2},v_{2}] [ u 2 , v 2 ] r ≥ 3 r\ge3 r ≥ 3 O r O_{r} O r v r v_{r} v r O r − 1 O_{r-1} O r − 1 x r − 1 = 0 x_{r-1}=0 x r − 1 = 0 conv ( u 2 , … , u r ) \operatorname{conv}(u_{2},\ldots,u_{r}) conv ( u 2 , … , u r ) x 0 = x 1 x_{0}=x_{1} x 0 = x 1 v r v_{r} v r (28) .
Fix integers n ≥ 1 n\ge1 n ≥ 1 r 0 ≥ 2 r_{0}\ge2 r 0 ≥ 2 2 ≤ r ≤ r 0 2\le r\le r_{0} 2 ≤ r ≤ r 0 (28) into n r − 1 n^{r-1} n r − 1 z z z σ \sigma σ [ d ] [d] [ d ] z z z z + e σ ( 1 ) , … , z + ( 1 , … , 1 ) z+e_{\sigma(1)},\ldots,z+(1,\ldots,1) z + e σ ( 1 ) , … , z + ( 1 , … , 1 ) y y y
1 n ( n − y d , y 1 , y 2 − y 1 , … , y d − y d − 1 ) (29) \frac{1}{n}(n-y_d,y_1,y_2-y_1,\ldots,y_d-y_{d-1}) \tag*{(29)} n 1 ( n − y d , y 1 , y 2 − y 1 , … , y d − y d − 1 ) (29) in the ordered original simplex. Each path gives one small simplex. Cumulative barycentric coordinates identify the original simplex with { 0 ≤ y 1 ≤ ⋯ ≤ y d ≤ n } \{0\le y_1\le\cdots\le y_d\le n\} { 0 ≤ y 1 ≤ ⋯ ≤ y d ≤ n }
For r > r 0 r>r_0 r > r 0 O r − 1 \mathcal{O}_{r-1} O r − 1 v r v_r v r f f f O r − 1 \mathcal{O}_{r-1} O r − 1 x 0 = x 1 x_0=x_1 x 0 = x 1 conv ( f , u r , v r ) \operatorname{conv}(f,u_r,v_r) conv ( f , u r , v r ) O r \mathcal{O}_r O r O r \mathcal{O}_r O r O r − 1 \mathcal{O}_{r-1} O r − 1 Lemma 7.1 requires, and the cells of § 5.1 , the subdivision P S P_S P S Ω S \Omega_S Ω S r = 3 r=3 r = 3 O 3 \mathcal{O}_3 O 3 u 2 , v 2 , v 3 , u 3 u_2,v_2,v_3,u_3 u 2 , v 2 , v 3 , u 3 u 2 v 2 v 3 u_2v_2v_3 u 2 v 2 v 3 u 2 u 3 v 3 u_2u_3v_3 u 2 u 3 v 3 n 2 n^2 n 2 n = 3 n=3 n = 3
∣ O r ∣ = 1 − r ( 1 − T ) r − 1 r ! ( r − 1 ) ! and ∣ { x 0 = T } ∩ O r ∣ = ( 1 − T ) r − 2 ( r − 2 ) ! ( r − 1 ) ! . (30) |\mathcal{O}_r|=\frac{1-r(1-T)^{r-1}}{r!(r-1)!}
\quad\text{and}\quad
|\{x_0=T\}\cap\mathcal{O}_r|=\frac{(1-T)^{r-2}}{(r-2)!(r-1)!}. \tag*{(30)} ∣ O r ∣ = r ! ( r − 1 )! 1 − r ( 1 − T ) r − 1 and ∣ { x 0 = T } ∩ O r ∣ = ( r − 2 )! ( r − 1 )! ( 1 − T ) r − 2 . (30) The first subtracts the r r r { x i ≥ T } \{x_i\ge T\} { x i ≥ T } Δ r \Delta_r Δ r r ! r! r ! ( r − 1 ) ! (r-1)! ( r − 1 )!
Let P P P a 0 , … , a d a_0,\ldots,a_d a 0 , … , a d V P V_P V P λ 0 , … , λ d \lambda_0,\ldots,\lambda_d λ 0 , … , λ d P P P Bernstein basis
F ( x ) = ∑ s F s s λ s ( x ) 2 + 2 ∑ s < t F s t λ s ( x ) λ t ( x ) , (31) F(x)=\sum_s F_{ss}\lambda_s(x)^2+2\sum_{s<t}F_{st}\lambda_s(x)\lambda_t(x), \tag*{(31)} F ( x ) = s ∑ F ss λ s ( x ) 2 + 2 s < t ∑ F s t λ s ( x ) λ t ( x ) , (31) with one coefficient F s t F_{st} F s t s ≤ t s\le t s ≤ t F s t F_{st} F s t a s a t a_sa_t a s a t P P P 2 V P / ( r ( r + 1 ) ) 2V_P/(r(r+1)) 2 V P / ( r ( r + 1 ))
The first property is sufficient, not necessary. On [ 0 , 1 ] [0,1] [ 0 , 1 ] ( 1 − 2 t ) 2 = ( 1 − t ) 2 − 2 t ( 1 − t ) + t 2 (1-2t)^2=(1-t)^2-2t(1-t)+t^2 ( 1 − 2 t ) 2 = ( 1 − t ) 2 − 2 t ( 1 − t ) + t 2 1 , − 1 , 1 1,-1,1 1 , − 1 , 1 Definition 3.3 coefficient by coefficient. This restricts the flow instances we search for and verify, while the resulting flow instance still covers every cut in Theorem 3.4 .
The Linear Program
All conditions are homogeneous, so the value ( B − R ) / L (B-R)/L ( B − R ) / L w w w g g g F F F ϵ \epsilon ϵ
maximize B − R subject to L = 1 , w i j S ≥ 0 , g i S ≥ 0 , ϵ U ≥ 0 , ∑ ℓ F ℓ , i S = 0 , F ∗ S = 0 , normal continuity, capacity, the terminal condition, and conservation. \begin{aligned}
\text{maximize}\quad& B-R\\
\text{subject to}\quad& L=1,\quad w^S_{ij}\ge0,\quad g^S_i\ge0,\quad\epsilon_U\ge0,\quad\sum_\ell F^S_{\ell,i}=0,\quad F^S_\ast=0,\\
&\text{normal continuity, capacity, the terminal condition, and conservation.}
\end{aligned} maximize subject to B − R L = 1 , w ij S ≥ 0 , g i S ≥ 0 , ϵ U ≥ 0 , ℓ ∑ F ℓ , i S = 0 , F ∗ S = 0 , normal continuity, capacity, the terminal condition, and conservation. By Lemma 7.1 the unknowns are the coefficients on the ordered regions, and conservation couples O r \mathcal{O}_r O r O r + 1 \mathcal{O}_{r+1} O r + 1 § 7.4 chooses the unknowns so that they hold identically. Capacity and conservation are inequalities between coefficients, imposed through the first property of the basis, with both signs for each absolute value. The objective and the normalization are sums of coefficients by the third property. The result is a finite linear program, and § 7.8 describes how it was solved.
Representing a Flow by Its Boundary Fluxes
Normal continuity, the terminal condition, and the supply to a child all concern the normal flux of a label flow through a facet of a cell. We therefore take the fluxes as the unknowns and recover the flow from them. A facet shared by two cells then carries one coefficient, read with opposite orientations by the two cells, so normal continuity holds by construction. The terminal condition becomes a rule on the coefficients of the terminal facet, and the supply to the child is the coefficient on the facet x r − 1 = 0 x_{r-1}=0 x r − 1 = 0
Orient each facet f f f s P , f = 1 s_{P,f}=1 s P , f = 1 s P , f = − 1 s_{P,f}=-1 s P , f = − 1 o P , f o_{P,f} o P , f P P P f f f H i , f , s t H_{i,f,st} H i , f , s t i i i f f f a s , a t a_s,a_t a s , a t f f f s = t s=t s = t s , t s,t s , t Z i , P , s t Z_{i,P,st} Z i , P , s t i i i P P P a s a t a_sa_t a s a t s < t s<t s < t W P , s t , i j W_{P,st,ij} W P , s t , ij P P P s t st s t e i − e j e_i-e_j e i − e j i < j i<j i < j
Let h i , f , s t = H i , f , s t / D h_{i,f,st}=H_{i,f,st}/D h i , f , s t = H i , f , s t / D z i , P , s t = Z i , P , s t / D z_{i,P,st}=Z_{i,P,st}/D z i , P , s t = Z i , P , s t / D D D D h i , f , s t h_{i,f,st} h i , f , s t F i F_i F i f f f b b b
V P F i , P , s t = 1 d ∑ f ⊂ ∂ P a s , a t ∈ f s P , f h i , f , s t ( a s + a t 2 − o P , f ) + { z i , P , s t ( a s − a t ) , s < t , 0 , s = t , (32) V_PF_{i,P,st}=\frac{1}{d}\sum_{\substack{f\subset\partial P\\a_s,a_t\in f}}s_{P,f}h_{i,f,st}\left(\frac{a_s+a_t}{2}-o_{P,f}\right)+
\begin{cases}
z_{i,P,st}(a_s-a_t), & s<t,\\
0, & s=t,
\end{cases} \tag*{(32)} V P F i , P , s t = d 1 f ⊂ ∂ P a s , a t ∈ f ∑ s P , f h i , f , s t ( 2 a s + a t − o P , f ) + { z i , P , s t ( a s − a t ) , 0 , s < t , s = t , (32) w i j , P , s t = W P , s t , i j D V P , (33) w_{ij,P,st}=\frac{W_{P,st,ij}}{DV_P}, \tag*{(33)} w ij , P , s t = D V P W P , s t , ij , (33) extended inside P P P (31) , with F ∗ = 0 F_\ast=0 F ∗ = 0 Lemma 5.6 ).
Two boundary rules are imposed on H H H x j = x j + 1 x_j=x_{j+1} x j = x j + 1 O r \mathcal{O}_r O r j j j j + 1 j+1 j + 1 x 0 = T x_0=T x 0 = T 0 0 0
Lemma 7.2 (Reconstruction). The flows (32) are tangent to their face, and on every facet f f f of a cell P P P the quadratic normal component of F i F_i F i multiplied by the measure of f f f has coefficients exactly
s P , f h i , f , s t s_{P,f}h_{i,f,st} s P , f h i , f , s t a s , a t ∈ f a_s,a_t \in f a s , a t ∈ f O r \mathcal{O}_r O r H H H O r \mathcal{O}_r O r H H H g 0 g_0 g 0 F 0 F_0 F 0 x 0 = T x_0=T x 0 = T
Proof. Every vector ( a s + a t ) / 2 − o P , f (a_s+a_t)/2-o_{P,f} ( a s + a t ) /2 − o P , f a s − a t a_s-a_t a s − a t P P P o o o − d V P ∇ λ o -dV_P\nabla\lambda_o − d V P ∇ λ o ( a s + a t ) / 2 − o (a_s+a_t)/2-o ( a s + a t ) /2 − o d V P dV_P d V P a s , a t a_s,a_t a s , a t a s , a t a_s,a_t a s , a t a s − a t a_s-a_t a s − a t F i F_i F i f f f f f f s P , f h i , f , s t s_{P,f}h_{i,f,st} s P , f h i , f , s t f f f f f f
Since the two cells sharing a facet use the same coefficients with opposite orientations, their quadratic normal components agree, which is normal continuity inside O r \mathcal{O}_r O r O r \mathcal{O}_r O r x j = x j + 1 x_j=x_{j+1} x j = x j + 1 j j j j + 1 j+1 j + 1 j j j j + 1 j+1 j + 1
On x 0 = T x_0=T x 0 = T (13) , and the terminal-facet rule says that it vanishes for every label other than 0 and is a nonnegative quadratic for label 0, which is the terminal condition with that quadratic as g 0 g_0 g 0 a s − a t a_s-a_t a s − a t (32) .
The Finite Conditions
With the flows and weights given by the table, two conditions of Definition 3.3 remain, and we reduce each to a statement about the integers. Capacity becomes a list of integer inequalities, which the table must satisfy. Conservation is satisfied by definition, because the allowance is defined as whatever the divergence exceeds the supply by, and it is paid for in R R R
Capacity. Since max ℓ y ℓ − min ℓ y ℓ ≤ c \max_\ell y_\ell-\min_\ell y_\ell\le c max ℓ y ℓ − min ℓ y ℓ ≤ c ∣ y ℓ − y m ∣ ≤ c \lvert y_\ell-y_m\rvert\le c ∣ y ℓ − y m ∣ ≤ c ℓ , m \ell,m ℓ , m I ⊂ { 0 , … , r − 1 } I\subset\{0,\ldots,r-1\} I ⊂ { 0 , … , r − 1 }
max ℓ ∈ { 0 , … , r − 1 , ∗ } ∑ i ∈ I F ℓ , P , s t , i − min ℓ ∈ { 0 , … , r − 1 , ∗ } ∑ i ∈ I F ℓ , P , s t , i ≤ ∑ i ∈ I , j ∉ I w i j , P , s t . (34) \max_{\ell\in\{0,\ldots,r-1,*\}}\sum_{i\in I}F_{\ell,P,st,i}-\min_{\ell\in\{0,\ldots,r-1,*\}}\sum_{i\in I}F_{\ell,P,st,i}\le\sum_{i\in I,j\notin I}w_{ij,P,st}. \tag*{(34)} ℓ ∈ { 0 , … , r − 1 , ∗ } max i ∈ I ∑ F ℓ , P , s t , i − ℓ ∈ { 0 , … , r − 1 , ∗ } min i ∈ I ∑ F ℓ , P , s t , i ≤ i ∈ I , j ∈ / I ∑ w ij , P , s t . (34) where F ∗ , P , s t = 0 F_{*,P,st}=0 F ∗ , P , s t = 0 r r r p s , j / Q r p_{s,j}/Q_r p s , j / Q r Q r Q_r Q r
N i , j ( P , s t ) = ∑ f ⊃ { a s , a t } s P , f H i , f , s t ( p s , j + p t , j − 2 p o P , f , j ) + { 2 d Z i , P , s t ( p s , j − p t , j ) , s < t , 0 , s = t , N_{i,j}(P,st)=\sum_{f\supset\{a_s,a_t\}}s_{P,f}H_{i,f,st}(p_{s,j}+p_{t,j}-2p_{o_{P,f},j})+
\begin{cases}
2dZ_{i,P,st}(p_{s,j}-p_{t,j}), & s<t,\\
0, & s=t,
\end{cases} N i , j ( P , s t ) = f ⊃ { a s , a t } ∑ s P , f H i , f , s t ( p s , j + p t , j − 2 p o P , f , j ) + { 2 d Z i , P , s t ( p s , j − p t , j ) , 0 , s < t , s = t , so that V P F i , P , s t , j = N i , j ( P , s t ) / ( 2 d Q r D ) V_PF_{i,P,st,j}=N_{i,j}(P,st)/(2dQ_rD) V P F i , P , s t , j = N i , j ( P , s t ) / ( 2 d Q r D ) (32) , with N ∗ , j = 0 N_{*,j}=0 N ∗ , j = 0
Lemma 7.3 (Integer capacity). Suppose that for every r r r P P P O r \mathcal{O}_r O r s t st s t I ⊂ { 0 , … , r − 1 } I\subset\{0,\ldots,r-1\} I ⊂ { 0 , … , r − 1 }
max ℓ ∈ { 0 , … , r − 1 , ∗ } ∑ j ∈ I N ℓ , j ( P , s t ) − min ℓ ∈ { 0 , … , r − 1 , ∗ } ∑ j ∈ I N ℓ , j ( P , s t ) ≤ 2 d Q r ∑ i ∈ I , j ∉ I W P , s t , i j . (35) \max_{\ell\in\{0,\ldots,r-1,*\}}\sum_{j\in I}N_{\ell,j}(P,st)-\min_{\ell\in\{0,\ldots,r-1,*\}}\sum_{j\in I}N_{\ell,j}(P,st)\le2dQ_r\sum_{i\in I,j\notin I}W_{P,st,ij}. \tag*{(35)} ℓ ∈ { 0 , … , r − 1 , ∗ } max j ∈ I ∑ N ℓ , j ( P , s t ) − ℓ ∈ { 0 , … , r − 1 , ∗ } min j ∈ I ∑ N ℓ , j ( P , s t ) ≤ 2 d Q r i ∈ I , j ∈ / I ∑ W P , s t , ij . (35) Then the flows (32) and the weights (33) satisfy capacity at every point of every cell of every O r \mathcal{O}_r O r
Proof. Multiplying (34) by 2 d Q r D V P 2dQ_{r}DV_{P} 2 d Q r D V P (35) , so the hypothesis is capacity between corresponding coefficients, for every pair of labels and every subset. For a fixed pair of labels and a fixed I I I
Conservation
The divergence of a quadratic flow is affine, and the residual is computed from the flows and their parent fluxes and then bounded above by a nonnegative polynomial. The sign is forced by div F ≤ b + ϵ \operatorname{div} F \le b+\epsilon div F ≤ b + ϵ A P , i , s = V P div F i , P ( a s ) A_{P,i,s}=V_{P}\operatorname{div}F_{i,P}(a_{s}) A P , i , s = V P div F i , P ( a s ) (31) and substituting (32) gives
A P , i , s = 1 d ∑ f ∋ a s s P , f ( 2 h i , f , s s + ∑ a t ∈ f ∖ { a s } h i , f , s t ) + 2 ( ∑ t < s z i , P , t s − ∑ t > s z i , P , s t ) . (36) A_{P,i,s}=\frac{1}{d}\sum_{f\ni a_s}s_{P,f}\left(2h_{i,f,ss}+\sum_{a_t\in f\setminus\{a_s\}}h_{i,f,st}\right)+2\left(\sum_{t<s}z_{i,P,ts}-\sum_{t>s}z_{i,P,st}\right). \tag*{(36)} A P , i , s = d 1 f ∋ a s ∑ s P , f 2 h i , f , ss + a t ∈ f ∖ { a s } ∑ h i , f , s t + 2 ( t < s ∑ z i , P , t s − t > s ∑ z i , P , s t ) . (36) An affine function, written in the quadratic basis, has coefficient at s t st s t a s a_s a s a t a_t a t r < q r<q r < q f + f^{+} f + O r + 1 \mathcal{O}_{r+1} O r + 1 P P P h i , f + , s t h_{i,f^{+},st} h i , f + , s t O r + 1 \mathcal{O}_{r+1} O r + 1 V P V_P V P
e P , s t = max ( 0 , max 0 ≤ i < r { A P , i , s + A P , i , t 2 − h i , f + , s t } ) , (37) e_{P,st}=\max\left(0,\max_{0\le i<r}\left\{\frac{A_{P,i,s}+A_{P,i,t}}{2}-h_{i,f^{+},st}\right\}\right), \tag*{(37)} e P , s t = max ( 0 , 0 ≤ i < r max { 2 A P , i , s + A P , i , t − h i , f + , s t } ) , (37) with the parent coefficient replaced by zero when r = q r=q r = q
Lemma 7.4 (Integer conservation). Let ϵ ( r ) \epsilon^{(r)} ϵ ( r ) P P P O r \mathcal{O}_r O r e P , s t / V P e_{P,st}/V_P e P , s t / V P ϵ ( r ) ≥ 0 \epsilon^{(r)}\ge0 ϵ ( r ) ≥ 0 Δ q \Delta_q Δ q
Proof. The coefficients e P , s t e_{P,st} e P , s t ϵ ( r ) ≥ 0 \epsilon^{(r)}\ge0 ϵ ( r ) ≥ 0 (36) and the averaging rule, ( A P , i , s + A P , i , t ) / ( 2 V P ) (A_{P,i,s}+A_{P,i,t})/(2V_P) ( A P , i , s + A P , i , t ) / ( 2 V P ) s t st s t div F i , P \operatorname{div}F_{i,P} div F i , P f + f^{+} f + (13) , h i , f + , s t / V P h_{i,f^{+},st}/V_P h i , f + , s t / V P − F i , r ( r + 1 ) ( ⋅ , 0 ) -F^{(r+1)}_{i,r}(\mathord{\cdot},0) − F i , r ( r + 1 ) ( ⋅ , 0 ) (37) says that ϵ ( r ) \epsilon^{(r)} ϵ ( r ) ∗ \ast ∗
The quantities B B B R R R L L L
A facet has r ( r − 1 ) / 2 r(r-1)/2 r ( r − 1 ) /2 r ( r + 1 ) / 2 r(r+1)/2 r ( r + 1 ) /2 (33) ,
B = ∑ r = 2 q ∑ f on x 0 = T 2 r ( r − 1 ) ∑ s ≤ t : a s , a t ∈ f h 0 , f , s t and R = ∑ r = 2 q ∑ P ⊂ O r 2 r ( r + 1 ) ∑ s ≤ t e P , s t , (38) B=\sum_{r=2}^{q}\sum_{f\text{ on }x_0=T}\frac{2}{r(r-1)}\sum_{s\le t:\,a_s,a_t\in f}h_{0,f,st}
\quad\text{and}\quad
R=\sum_{r=2}^{q}\sum_{P\subset\mathcal{O}_r}\frac{2}{r(r+1)}\sum_{s\le t}e_{P,st}, \tag*{(38)} B = r = 2 ∑ q f on x 0 = T ∑ r ( r − 1 ) 2 s ≤ t : a s , a t ∈ f ∑ h 0 , f , s t and R = r = 2 ∑ q P ⊂ O r ∑ r ( r + 1 ) 2 s ≤ t ∑ e P , s t , (38) L = ∑ r = 2 q ∑ P ⊂ O r 2 r ( r + 1 ) D ∑ s ≤ t ∑ i < j W P , s t , i j + ( 1 − T ) B . (39) L=\sum_{r=2}^{q}\sum_{P\subset\mathcal{O}_r}\frac{2}{r(r+1)D}\sum_{s\le t}\sum_{i<j}W_{P,st,ij}+(1-T)B. \tag*{(39)} L = r = 2 ∑ q P ⊂ O r ∑ r ( r + 1 ) D 2 s ≤ t ∑ i < j ∑ W P , s t , ij + ( 1 − T ) B . (39) Proposition 7.5 (Soundness of the finite checks). Fix q ≥ 2 q\ge2 q ≥ 2 T ∈ ( 1 / 2 , 1 ) T\in(1/2,1) T ∈ ( 1/2 , 1 ) n ≥ 1 n\ge1 n ≥ 1 r 0 ≥ 2 r_0\ge2 r 0 ≥ 2 D ≥ 1 D\ge1 D ≥ 1 § 7.2 . Let integers H H H Z Z Z W ≥ 0 W\ge0 W ≥ 0 § 7.4 and the integer capacity inequality (35) for every cell, coefficient, and subset. Then the flows (32) , the weights (33) , the terminal densities given by the normal density of F 0 F_0 F 0 x 0 = T x_0=T x 0 = T (37) , transported to every
face by Lemma 7.1 , form a flow instance on Δ q \Delta_q Δ q B B B R R R L L L (38) and (39) . In particular, if L > 0 L > 0 L > 0 Δ q \Delta_q Δ q α \alpha α α ≥ ( B − R ) / L \alpha\ge(B-R)/L α ≥ ( B − R ) / L lim k G k ≥ ( B − R ) / L \lim_{k} G_k \ge(B-R)/L lim k G k ≥ ( B − R ) / L
Proof. The quantities are of the kinds required in § 3.2 and § 5.1 , since the cells are simplices, the weights and flows are quadratics on each cell, and the terminal densities are nonnegative quadratics. Normal continuity holds inside each ordered region and across ordered regions by Lemma 7.2 , and the terminal condition by the same lemma. Capacity holds on every O r \mathcal{O}_r O r Lemma 7.1 (iii), and conservation holds by Lemma 7.4. The formulas for B B B R R R L L L Lemma 7.1 (i). The last assertion is Theorem 3.4 .
The validity of a flow instance given by a table therefore depends only on exact integer checks, not on how the table was found.
The Flow Instance on Δ 11 \Delta_{11} Δ 11
Proof of Proposition 3.6 . The flow instance uses q = 11 q = 11 q = 11 T = 249 / 400 T = 249/400 T = 249/400 n = 3 n = 3 n = 3 r 0 = 5 r_0 = 5 r 0 = 5 D = 230000000000 D = 230000000000 D = 230000000000 § 7.2 , with quadratic flows and weights on every cell. Its ordered regions contain 2,937 cells:
Table 1 (PDF p. 31).
The table consists of the integers H H H Z Z Z W W W § 7.4 for r = 2 , … , 11 r = 2,\ldots,11 r = 2 , … , 11 (35) for every cell, coefficient, and subset, which we checked in integer and rational arithmetic, together with the geometry of the subdivision, by the checker described at the end of this section. By Proposition 7.5 the table defines a flow instance on Δ 11 \Delta_{11} Δ 11 T = 249 / 400 T = 249/400 T = 249/400 (38) and (39) , evaluated in exact arithmetic, are
B = 1725000000167 1725000000000 , R = 2593033 910800000000000 , and L = 43107286191734959 53130000000000000 . (40) B = \frac{1725000000167}{1725000000000}, \qquad R = \frac{2593033}{910800000000000}, \qquad\text{and } L = \frac{43107286191734959}{53130000000000000}. \tag*{(40)} B = 1725000000000 1725000000167 , R = 910800000000000 2593033 , and L = 53130000000000000 43107286191734959 . (40) Their ratio is
B − R L = 159389999561650025 129321858575204877 = 1.232506254686709004 … \frac{B-R}{L} = \frac{159389999561650025}{129321858575204877} = 1.232506254686709004\ldots L B − R = 129321858575204877 159389999561650025 = 1.232506254686709004 … Proof of Theorem 1.1 . By Proposition 3.6 there is a flow instance on Δ 11 \Delta_{11} Δ 11 L > 0 L > 0 L > 0 159389999561650025 129321858575204877 \frac{159389999561650025}{129321858575204877} 129321858575204877 159389999561650025 Theorem 3.4 every random non-opposite cut of Δ 11 \Delta_{11} Δ 11 α \alpha α α ≥ β \alpha\ge\beta α ≥ β Lemma 2.2 with q = 11 q = 11 q = 11 β \beta β lim k → ∞ G k ≥ β > 1.2325 \lim_{k\to\infty} G_k \ge\beta> 1.2325 lim k → ∞ G k ≥ β > 1.2325 η > 0 \eta> 0 η > 0 k k k k k k β − η \beta-\eta β − η
How the flow instance was found. The linear program of § 7.3 was solved with the allowance set to zero, so that the normalization is B = 1 B = 1 B = 1 L L L r ≤ 5 r \le5 r ≤ 5 6 ≤ r ≤ 10 6 \le r \le10 6 ≤ r ≤ 10 i i i A ( e i − u r ) A(e_i-u_r) A ( e i − u r ) A A A u r u_r u r A / ( r − 1 ) A/(r-1) A / ( r − 1 ) § 6 . For r = 11 r = 11 r = 11 D D D (37) of the rounded table, and the weights were rounded upward and increased where capacity required it, then reduced wherever every inequality remained valid. The proof of Proposition 3.6 uses the rounded table alone.
For these weights, the lower bound on the cut cost is already within R R R B B B ∗ \ast ∗ R / L < 3.6 × 10 − 9 R/L < 3.6 \times10^{-9} R / L < 3.6 × 1 0 − 9
Availability. The table, the checker, and the search and rounding code are available at https://github.com/dimitarch/multiway-cut-integrality-gap . The checker verify.py rebuilds the subdivision of § 7.2 from the stored vertices, checks the two boundary rules and the inequality (35) for every cell, coefficient, and subset in integer arithmetic, and prints B B B R R R L L L (40) , in about ten seconds and without any optimization software. The floating solution of the linear program is stored as well, and the rounding and trimming steps described above are deterministic, so the table can be regenerated from it.
Generative AI Statement. The authors came up the idea of establishing a lower bound for the LP relaxation of the Minimum Multiway Cut problem using flows in a continuous setting and non-opposite cuts. The proofs were developed through interactive sessions with GPT-6 Astra. The authors substantially revised the proofs proposed by the LLM, identified a number of gaps and fixed them. Claude Fable 5.1 and Opus 5.5 were used in preparing the numerical optimization code. We take full responsibility for the contents of this paper.
Proof of the Non-Opposite Reduction
Lemma 2.2 turns a lower bound on the approximation factor of every random non-opposite cut of Δ q \Delta_q Δ q lim k → ∞ G k \lim_{k\to\infty} G_k lim k → ∞ G k [2 ] , sketched in § 2 , at α = lim k → ∞ G k \alpha= \lim_{k\to\infty} G_k α = lim k → ∞ G k Δ q \Delta_q Δ q Δ q \Delta_q Δ q
Proof of Lemma 2.2. Let α = lim k → ∞ G k \alpha= \lim_{k\to\infty} G_k α = lim k → ∞ G k G k G_k G k G k ≤ 3 / 2 G_k \le3/2 G k ≤ 3/2 k k k [10 ] quoted in § 1 , and G k ≤ α G_k \le\alpha G k ≤ α k k k Δ q \Delta_q Δ q α \alpha α
Let Δ q , n \Delta_{q,n} Δ q , n Δ q \Delta_q Δ q 1 / n 1/n 1/ n Δ k \Delta_k Δ k G k G_k G k q q q Δ q \Delta_q Δ q ∗ \ast ∗ x x x k − ∣ supp ( x ) ∣ k - |\operatorname{supp}(x)| k − ∣ supp ( x ) ∣ q − ∣ supp ( x ) ∣ q - |\operatorname{supp}(x)| q − ∣ supp ( x ) ∣ x x x q / k q/k q / k Δ q , n \Delta_{q,n} Δ q , n 1 / n 1/n 1/ n O ( q n / k ) O(qn/k) O ( q n / k ) Δ q , n \Delta_{q,n} Δ q , n k → ∞ k \to\infty k → ∞ n n n Δ q , n \Delta_{q,n} Δ q , n n n n Δ q , n \Delta_{q,n} Δ q , n α \alpha α n ! n! n ! [5 Section 36] gives a random cut of the rational points of Δ q \Delta_q Δ q α \alpha α
To extend it measurably, round every coordinate of x x x 2 − m 2^{-m} 2 − m π m \pi_m π m supp ( π m ( x ) ) ⊆ supp ( x ) \operatorname{supp}(\pi_m(x)) \subseteq\operatorname{supp}(x) supp ( π m ( x )) ⊆ supp ( x ) π m ( e i ) = e i \pi_m(e_i) = e_i π m ( e i ) = e i d ( π m ( x ) , x ) ≤ ( q − 1 ) 2 − m d(\pi_m(x),x) \le(q - 1)2^{-m} d ( π m ( x ) , x ) ≤ ( q − 1 ) 2 − m
P [ C ( π m ( x ) ) ≠ C ( π m + 1 ( x ) ) ] ≤ α ( q − 1 ) ( 2 − m + 2 − m − 1 ) , \mathbb{P}[C(\pi_m(x)) \ne C(\pi_{m+1}(x))] \le\alpha(q - 1)(2^{-m} + 2^{-m-1}), P [ C ( π m ( x )) = C ( π m + 1 ( x ))] ≤ α ( q − 1 ) ( 2 − m + 2 − m − 1 ) , which is summable in m m m x x x C ( π m ( x ) ) C(\pi_m(x)) C ( π m ( x )) C ( x ) C(x) C ( x ) supp ( x ) \operatorname{supp}(x) supp ( x ) σ \sigma σ ( ξ , x ) ↦ C ( π m ( x ) ) (\xi,x) \mapsto C(\pi_m(x)) ( ξ , x ) ↦ C ( π m ( x )) C ( π m ( x ) ) C(\pi_m(x)) C ( π m ( x )) supp ( x ) ∪ { ∗ } \operatorname{supp}(x) \cup\{\ast\} supp ( x ) ∪ { ∗ } x , y x,y x , y
P [ C ( x ) ≠ C ( y ) ] = lim m → ∞ P [ C ( π m ( x ) ) ≠ C ( π m ( y ) ) ] ≤ lim m → ∞ α d ( π m ( x ) , π m ( y ) ) = α d ( x , y ) . \mathbb{P}[C(x) \ne C(y)] = \lim_{m\to\infty} \mathbb{P}[C(\pi_m(x)) \ne C(\pi_m(y))] \le\lim_{m\to\infty} \alpha d(\pi_m(x),\pi_m(y)) = \alpha d(x,y). P [ C ( x ) = C ( y )] = m → ∞ lim P [ C ( π m ( x )) = C ( π m ( y ))] ≤ m → ∞ lim α d ( π m ( x ) , π m ( y )) = α d ( x , y ) . So C C C Δ q \Delta_q Δ q α \alpha α α ≥ β \alpha\ge\beta α ≥ β lim k → ∞ G k ≥ β \lim_{k\to\infty} G_k \ge\beta lim k → ∞ G k ≥ β η > 0 \eta> 0 η > 0 k k k G k ≥ β − η / 2 G_k \ge\beta- \eta/2 G k ≥ β − η /2 G k G_k G k k k k k k k β − η \beta- \eta β − η
Flow Instances on a Graph
§ 3.1 defined flow instances on a finite graph H H H Lemma 3.1 , and its obstruction, Proposition 3.2 . This section proves both. A small example shows how a vertex where a label is forbidden acts as a source of that label’s flow, at no cost. The obstruction is what the construction on the simplex gets around, as § 3.2 explains.
Proof of Lemma 3.1 . Let the label flows φ ℓ \varphi_\ell φ ℓ ϵ v \epsilon_v ϵ v H = ( V , E ) H=(V,E) H = ( V , E ) C C C C ( v ) ∈ A ( v ) C(v)\in A(v) C ( v ) ∈ A ( v ) v v v ℓ \ell ℓ v v v in ℓ ( v ) = ∑ u : u v ∈ E φ ℓ ( u → v ) \operatorname{in}_\ell(v)=\sum_{u:uv\in E}\varphi_\ell(u\to v) in ℓ ( v ) = ∑ u : uv ∈ E φ ℓ ( u → v ) g v , i = 0 g_{v,i}=0 g v , i = 0 i ∉ supp ( v ) i\notin\operatorname{supp}(v) i ∈ / supp ( v ) g v , ∗ = 0 g_{v,*}=0 g v , ∗ = 0 g v , C ( v ) = ∑ i ∈ [ q ] g v , i 1 [ C ( v ) = i ] g_{v,C(v)}=\sum_{i\in[q]}g_{v,i}\mathbf{1}[C(v)=i] g v , C ( v ) = ∑ i ∈ [ q ] g v , i 1 [ C ( v ) = i ]
Sum the selected inflows in C ( v ) ( v ) \operatorname{in}_{C(v)}(v) in C ( v ) ( v ) u v uv uv v v v φ C ( v ) ( u → v ) \varphi_{C(v)}(u\to v) φ C ( v ) ( u → v ) u u u φ C ( u ) ( v → u ) = − φ C ( u ) ( u → v ) \varphi_{C(u)}(v\to u)=-\varphi_{C(u)}(u\to v) φ C ( u ) ( v → u ) = − φ C ( u ) ( u → v ) φ C ( v ) ( u → v ) − φ C ( u ) ( u → v ) \varphi_{C(v)}(u\to v)-\varphi_{C(u)}(u\to v) φ C ( v ) ( u → v ) − φ C ( u ) ( u → v ) C ( u ) = C ( v ) C(u)=C(v) C ( u ) = C ( v ) w u v w_{uv} w uv C ( u ) , C ( v ) ∈ A ( u ) ∪ A ( v ) C(u),C(v)\in A(u)\cup A(v) C ( u ) , C ( v ) ∈ A ( u ) ∪ A ( v ) C ( v ) ∈ A ( v ) C(v)\in A(v) C ( v ) ∈ A ( v ) in C ( v ) ( v ) ≥ g v , C ( v ) − ϵ v \operatorname{in}_{C(v)}(v)\ge g_{v,C(v)}-\epsilon_v in C ( v ) ( v ) ≥ g v , C ( v ) − ϵ v
∑ u v ∈ E w u v 1 [ C ( u ) ≠ C ( v ) ] ≥ ∑ u v ∈ E ( φ C ( v ) ( u → v ) − φ C ( u ) ( u → v ) ) = ∑ v ∈ V in C ( v ) ( v ) ≥ ∑ v ∈ V g v , C ( v ) − R . \begin{aligned}
\sum_{uv\in E}w_{uv}\mathbf{1}[C(u)\ne C(v)]\ge\sum_{uv\in E}\left(\varphi_{C(v)}(u\to v)-\varphi_{C(u)}(u\to v)\right) \\
&=\sum_{v\in V}\operatorname{in}_{C(v)}(v) \\
&\ge\sum_{v\in V}g_{v,C(v)}-R.
\end{aligned} uv ∈ E ∑ w uv 1 [ C ( u ) = C ( v )] ≥ uv ∈ E ∑ ( φ C ( v ) ( u → v ) − φ C ( u ) ( u → v ) ) = v ∈ V ∑ in C ( v ) ( v ) ≥ v ∈ V ∑ g v , C ( v ) − R . The last sum is the weight of the terminal edges that C C C ∑ v , i g v , i 1 [ C ( v ) ≠ i ] \sum_{v,i}g_{v,i}\mathbf{1}[C(v)\ne i] ∑ v , i g v , i 1 [ C ( v ) = i ] cost ( C ) ≥ ∑ v , i g v , i − R = B − R \operatorname{cost}(C)\ge\sum_{v,i}g_{v,i}-R=B-R cost ( C ) ≥ ∑ v , i g v , i − R = B − R (4) .
For the second assertion, let C C C Δ q \Delta_q Δ q α \alpha α V V V H H H cost ( C ) ≥ B − R \operatorname{cost}(C)\ge B-R cost ( C ) ≥ B − R u v uv uv α d ( u , v ) \alpha d(u,v) α d ( u , v ) v e i ve_i v e i α d ( v , e i ) = α ( 1 − v i ) \alpha d(v,e_i)=\alpha(1-v_i) α d ( v , e i ) = α ( 1 − v i ) C ( e i ) = i C(e_i)=i C ( e i ) = i (4) gives
B − R ≤ E [ cost ( C ) ] ≤ α ∑ u v ∈ E w u v d ( u , v ) + α ∑ v , i g v , i ( 1 − v i ) = α L , B-R\le\mathbb{E}[\operatorname{cost}(C)]\le\alpha\sum_{uv\in E}w_{uv}d(u,v)+\alpha\sum_{v,i}g_{v,i}(1-v_i)=\alpha L, B − R ≤ E [ cost ( C )] ≤ α uv ∈ E ∑ w uv d ( u , v ) + α v , i ∑ g v , i ( 1 − v i ) = α L , and dividing by L > 0 L>0 L > 0 α ≥ ( B − R ) / L \alpha\ge(B-R)/L α ≥ ( B − R ) / L
For a small calculation, take the path a b c abc ab c a = ( 0 , 1 / 2 , 1 / 2 ) a=(0,1/2,1/2) a = ( 0 , 1/2 , 1/2 ) b = ( 1 / 3 , 1 / 3 , 1 / 3 ) b=(1/3,1/3,1/3) b = ( 1/3 , 1/3 , 1/3 ) c = ( 2 / 3 , 1 / 6 , 1 / 6 ) c=(2/3,1/6,1/6) c = ( 2/3 , 1/6 , 1/6 ) w a b = 2 w_{ab}=2 w ab = 2 w b c = 1 w_{bc}=1 w b c = 1 φ 1 ( a → b ) = 2 \varphi_1(a\to b)=2 φ 1 ( a → b ) = 2 φ 1 ( b → c ) = 1 \varphi_1(b\to c)=1 φ 1 ( b → c ) = 1 g a , 2 = 1 / 2 g_{a,2}=1/2 g a , 2 = 1/2 g b , 1 = g c , 1 = 1 g_{b,1}=g_{c,1}=1 g b , 1 = g c , 1 = 1 ϵ a = 1 / 2 \epsilon_a=1/2 ϵ a = 1/2 ϵ b = ϵ c = 0 \epsilon_b=\epsilon_c=0 ϵ b = ϵ c = 0 in 1 ( a ) = − 2 \operatorname{in}_1(a)=-2 in 1 ( a ) = − 2 in 1 ( b ) = 2 − 1 = 1 \operatorname{in}_1(b)=2-1=1 in 1 ( b ) = 2 − 1 = 1 in 1 ( c ) = 1 \operatorname{in}_1(c)=1 in 1 ( c ) = 1 a a a 1 1 1 a a a g a , 2 g_{a,2} g a , 2 in 2 ( a ) = 0 \operatorname{in}_2(a)=0 in 2 ( a ) = 0
Label the vertices C ( a ) = ∗ C(a)=* C ( a ) = ∗ C ( b ) = C ( c ) = 1 C(b)=C(c)=1 C ( b ) = C ( c ) = 1 0 , 1 , 1 0,1,1 0 , 1 , 1 b c bc b c 1 − 1 = 0 1-1=0 1 − 1 = 0 a b ab ab 2 − 0 = 2 2-0=2 2 − 0 = 2 b b b c c c e 1 e_1 e 1 2 2 2 a a a e 2 e_2 e 2 1 / 2 1/2 1/2 B = 5 / 2 B=5/2 B = 5/2 R = 1 / 2 R=1/2 R = 1/2
L = 2 ⋅ 1 3 + 1 ⋅ 1 3 + 1 2 ⋅ 1 2 + 1 ⋅ 2 3 + 1 ⋅ 1 3 = 9 4 , L=2\cdot\frac{1}{3}+1\cdot\frac{1}{3}+\frac{1}{2}\cdot\frac{1}{2}+1\cdot\frac{2}{3}+1\cdot\frac{1}{3}=\frac{9}{4}, L = 2 ⋅ 3 1 + 1 ⋅ 3 1 + 2 1 ⋅ 2 1 + 1 ⋅ 3 2 + 1 ⋅ 3 1 = 4 9 , where the first two terms in L L L 2 + 1 / 2 = 5 / 2 ≥ B − R = 2 2 + 1/2 = 5/2 \ge B - R = 2 2 + 1/2 = 5/2 ≥ B − R = 2
Proof of Proposition 3.2 . Let the label flows φ ℓ \varphi_\ell φ ℓ ϵ v \epsilon_v ϵ v H = ( V , E ) H = (V, E) H = ( V , E ) g v , i = 0 g_{v,i} = 0 g v , i = 0 i ∉ supp ( v ) i \notin\operatorname{supp}(v) i ∈ / supp ( v ) v v v in i ( v ) ≥ g v , i − ϵ v \operatorname{in}_i(v) \ge g_{v,i} - \epsilon_v in i ( v ) ≥ g v , i − ϵ v i i i v i v_i v i i ∈ [ q ] i \in[q] i ∈ [ q ] v i > 0 v_i > 0 v i > 0 ∑ i v i = 1 \sum_i v_i = 1 ∑ i v i = 1
∑ v , i v i in i ( v ) ≥ ∑ v , i v i g v , i − R . \sum_{v,i} v_i \operatorname{in}_i(v) \ge\sum_{v,i} v_i g_{v,i} - R. v , i ∑ v i in i ( v ) ≥ v , i ∑ v i g v , i − R . An edge u w uw u w ∑ i ( v i − u i ) φ i ( u → v ) \sum_i (v_i - u_i)\varphi_i(u \to v) ∑ i ( v i − u i ) φ i ( u → v ) v i φ i ( u → v ) v_i\varphi_i(u \to v) v i φ i ( u → v ) v v v u i φ i ( v → u ) = − u i φ i ( u → v ) u_i\varphi_i(v \to u) = -u_i\varphi_i(u \to v) u i φ i ( v → u ) = − u i φ i ( u → v ) u u u v i − u i v_i - u_i v i − u i d ( u , v ) d(u,v) d ( u , v ) i ∈ supp ( u ) ∪ supp ( v ) ⊆ A ( u ) ∪ A ( v ) i \in\operatorname{supp}(u) \cup\operatorname{supp}(v) \subseteq A(u) \cup A(v) i ∈ supp ( u ) ∪ supp ( v ) ⊆ A ( u ) ∪ A ( v ) φ i ( u → v ) \varphi_i(u \to v) φ i ( u → v ) w u v w_{uv} w uv d ( u , v ) d(u,v) d ( u , v )
∑ i ( v i − u i ) φ i ( u → v ) ≤ d ( u , v ) w u v . \sum_i (v_i-u_i)\varphi_i(u \to v) \le d(u,v)w_{uv}. i ∑ ( v i − u i ) φ i ( u → v ) ≤ d ( u , v ) w uv . Summing over edges and adding ∑ v , i g v , i ( 1 − v i ) \sum_{v,i}g_{v,i}(1-v_i) ∑ v , i g v , i ( 1 − v i )
L ≥ ∑ v , i v i g v , i − R + ∑ v , i ( 1 − v i ) g v , i = B − R . L \ge\sum_{v,i}v_i g_{v,i} - R + \sum_{v,i}(1-v_i)g_{v,i} = B - R. L ≥ v , i ∑ v i g v , i − R + v , i ∑ ( 1 − v i ) g v , i = B − R . The obstruction concerns label flows on edges, not finite graphs themselves, since the proof applies to the fractional labeling p v ( i ) = v i p_v(i) = v_i p v ( i ) = v i § 3.2 ), and § 5 proves the resulting bound.
Verification of the Triangle Flow Instance
§ 4 read the three conditions of Definition 3.3 off the figure for the flow instance on the triangle and computed its three numbers. This appendix verifies the conditions at every point, with the conventions of § 5.1 , and so completes the proof of Proposition 4.1 .
Proof of Proposition 4.1 . Normal continuity. Every face is one cell, so there is nothing to check. Terminal condition and supply. On Φ i [ 3 ] \Phi^{[3]}_i Φ i [ 3 ] p i [ 3 ] = 0 p^{[3]}_i = 0 p i [ 3 ] = 0 i i i F [ 3 ] F^{[3]} F [ 3 ] 1 [ ℓ = i ] = g i [ 3 ] 1 [ ℓ = i ] \mathbf{1}[\ell= i] = g^{[3]}_i\mathbf{1}[\ell= i] 1 [ ℓ = i ] = g i [ 3 ] 1 [ ℓ = i ] (13) this is the outward flux, so label i i i 1 1 1 x i = 2 / 3 x_i = 2/3 x i = 2/3 Ω { i , j } \Omega_{\{i,j\}} Ω { i , j } i i i F { i , j } F^{\{i,j\}} F { i , j } ( 2 / 3 ) ( 2 / 3 − 1 / 3 ) = 2 / 9 = g i { i , j } (2/3)(2/3 - 1/3) = 2/9 = g^{\{i,j\}}_i ( 2/3 ) ( 2/3 − 1/3 ) = 2/9 = g i { i , j } F { i , j } F^{\{i,j\}} F { i , j } x j = 1 / 3 x_j = 1/3 x j = 1/3 F ∗ { i , j } F_*^{\{i,j\}} F ∗ { i , j } x i = 0 x_i = 0 x i = 0 i i i F i [ 3 ] F^{[3]}_i F i [ 3 ] 1 − 2 / 3 = 1 / 3 1 - 2/3 = 1/3 1 − 2/3 = 1/3 i i i Ω { i , j } \Omega_{\{i,j\}} Ω { i , j } s s s (14) ,
b i [ 3 ] → { i , j } = − F i , s [ 3 ] ∣ x s = 0 = − ( 0 − 2 3 + 0 ) = 2 3 , b_i^{[3]\to\{i,j\}} = -F^{[3]}_{i,s}\big|_{x_s=0} = -\left(0-\frac{2}{3}+0\right)=\frac{2}{3}, b i [ 3 ] → { i , j } = − F i , s [ 3 ] x s = 0 = − ( 0 − 3 2 + 0 ) = 3 2 , and likewise b j [ 3 ] → { i , j } = 2 / 3 b_j^{[3]\to\{i,j\}} = 2/3 b j [ 3 ] → { i , j } = 2/3 b ∗ [ 3 ] → { i , j } = 0 b_*^{[3]\to\{i,j\}} = 0 b ∗ [ 3 ] → { i , j } = 0 Capacity. On the hexagon the nonempty proper subsets of [ 3 ] [3] [ 3 ] (9) for I I I [ 3 ] ∖ I [3]\setminus I [ 3 ] ∖ I I = { i } I = \{i\} I = { i } w i j [ 3 ] + w i s [ 3 ] = 1 w_{ij}^{[3]} + w_{is}^{[3]} = 1 w ij [ 3 ] + w i s [ 3 ] = 1 i i i F ℓ [ 3 ] F_{\ell}^{[3]} F ℓ [ 3 ] 1 − p i [ 3 ] 1-p_i^{[3]} 1 − p i [ 3 ] ℓ = i \ell=i ℓ = i − p i [ 3 ] -p_i^{[3]} − p i [ 3 ] ∗ * ∗ 0 ≤ p i [ 3 ] ≤ 2 / 3 0 \le p_i^{[3]} \le2/3 0 ≤ p i [ 3 ] ≤ 2/3 (15) , this reads
1 2 ( ∣ ν 1 − ν 2 ∣ + ∣ ν 1 − ν 3 ∣ + ∣ ν 2 − ν 3 ∣ ) = max s ν s − min s ν s ≥ ∣ ν ( F ℓ [ 3 ] − F m [ 3 ] ) ∣ , \frac{1}{2}\left(\lvert\nu_1-\nu_2\rvert+\lvert\nu_1-\nu_3\rvert+\lvert\nu_2-\nu_3\rvert\right)=\max_s \nu_s-\min_s \nu_s\geq\lvert\nu(F_{\ell}^{[3]}-F_m^{[3]})\rvert, 2 1 ( ∣ ν 1 − ν 2 ∣ + ∣ ν 1 − ν 3 ∣ + ∣ ν 2 − ν 3 ∣ ) = s max ν s − s min ν s ≥ ∣ ν ( F ℓ [ 3 ] − F m [ 3 ] )∣ , since ν ( F i [ 3 ] − F j [ 3 ] ) = ν i − ν j \nu(F_i^{[3]}-F_j^{[3]})=\nu_i-\nu_j ν ( F i [ 3 ] − F j [ 3 ] ) = ν i − ν j ν ( F i [ 3 ] − F ∗ [ 3 ] ) = ν i − ∑ s p s [ 3 ] ν s \nu(F_i^{[3]}-F_*^{[3]})=\nu_i-\sum_s p_s^{[3]}\nu_s ν ( F i [ 3 ] − F ∗ [ 3 ] ) = ν i − ∑ s p s [ 3 ] ν s ν i \nu_i ν i ν s \nu_s ν s
On the interval Ω { i , j } \Omega_{\{i,j\}} Ω { i , j } I = { i } I=\{i\} I = { i } w i j { i , j } = 2 / 9 w_{ij}^{\{i,j\}}=2/9 w ij { i , j } = 2/9 x i + x j = 1 x_i+x_j=1 x i + x j = 1 i i i ( 2 / 3 ) ( x i − 1 / 3 ) ∈ [ 0 , 2 / 9 ] (2/3)(x_i-1/3)\in[0,2/9] ( 2/3 ) ( x i − 1/3 ) ∈ [ 0 , 2/9 ] − ( 2 / 3 ) ( x j − 1 / 3 ) = ( 2 / 3 ) ( x i − 2 / 3 ) ∈ [ − 2 / 9 , 0 ] -(2/3)(x_j-1/3)=(2/3)(x_i-2/3)\in[-2/9,0] − ( 2/3 ) ( x j − 1/3 ) = ( 2/3 ) ( x i − 2/3 ) ∈ [ − 2/9 , 0 ]
2 3 ( x i − 1 3 ) + 2 3 ( x j − 1 3 ) = 2 3 ( x i + x j − 2 3 ) = 2 9 , \frac{2}{3}\left(x_i-\frac{1}{3}\right)+\frac{2}{3}\left(x_j-\frac{1}{3}\right)=\frac{2}{3}\left(x_i+x_j-\frac{2}{3}\right)=\frac{2}{9}, 3 2 ( x i − 3 1 ) + 3 2 ( x j − 3 1 ) = 3 2 ( x i + x j − 3 2 ) = 9 2 , and the component of F ∗ { i , j } F_*^{\{i,j\}} F ∗ { i , j } 2 / 9 2/9 2/9
Conservation. In the coordinates x 1 , x 2 x_1,x_2 x 1 , x 2 F ℓ , 1 [ 3 ] = 1 [ ℓ = 1 ] − 2 / 3 + x 1 F_{\ell,1}^{[3]}=\mathbb{1}[\ell=1]-2/3+x_1 F ℓ , 1 [ 3 ] = 1 [ ℓ = 1 ] − 2/3 + x 1 F ℓ , 2 [ 3 ] = 1 [ ℓ = 2 ] − 2 / 3 + x 2 F_{\ell,2}^{[3]}=\mathbb{1}[\ell=2]-2/3+x_2 F ℓ , 2 [ 3 ] = 1 [ ℓ = 2 ] − 2/3 + x 2
div F ℓ [ 3 ] = ∂ F ℓ , 1 [ 3 ] ∂ x 1 + ∂ F ℓ , 2 [ 3 ] ∂ x 2 = 1 + 1 = 2 and div F ∗ [ 3 ] = 0. \operatorname{div} F_{\ell}^{[3]}=\frac{\partial F_{\ell,1}^{[3]}}{\partial x_1}+\frac{\partial F_{\ell,2}^{[3]}}{\partial x_2}=1+1=2\quad\text{and}\quad\operatorname{div} F_*^{[3]}=0. div F ℓ [ 3 ] = ∂ x 1 ∂ F ℓ , 1 [ 3 ] + ∂ x 2 ∂ F ℓ , 2 [ 3 ] = 1 + 1 = 2 and div F ∗ [ 3 ] = 0. The top face has no parent, and the allowance 2 covers this divergence. On Ω { i , j } \Omega_{\{i,j\}} Ω { i , j } x i x_i x i F i { i , j } F_i^{\{i,j\}} F i { i , j } ( 2 / 3 ) ( x i − 1 / 3 ) (2/3)(x_i-1/3) ( 2/3 ) ( x i − 1/3 ) F j { i , j } F_j^{\{i,j\}} F j { i , j } ( 2 / 3 ) ( x i − 2 / 3 ) (2/3)(x_i-2/3) ( 2/3 ) ( x i − 2/3 ) 2 / 3 2/3 2/3
div F i { i , j } = div F j { i , j } = 2 3 = b i [ 3 ] → { i , j } = b j [ 3 ] → { i , j } and div F ∗ { i , j } = 0 = b ∗ [ 3 ] → { i , j } , \operatorname{div} F_i^{\{i,j\}}=\operatorname{div} F_j^{\{i,j\}}=\frac{2}{3}=b_i^{[3]\to\{i,j\}}=b_j^{[3]\to\{i,j\}}\quad\text{and}\quad\operatorname{div} F_*^{\{i,j\}}=0=b_*^{[3]\to\{i,j\}}, div F i { i , j } = div F j { i , j } = 3 2 = b i [ 3 ] → { i , j } = b j [ 3 ] → { i , j } and div F ∗ { i , j } = 0 = b ∗ [ 3 ] → { i , j } , and conservation holds on the intervals with zero allowance. The hexagon supplies exactly the growth of the interval flows, which is the balance that fixed the interval slope.
The three numbers. They were computed in § 4 , where B = 7 / 3 B=7/3 B = 7/3 R = 2 / 3 R=2/3 R = 2/3 L = 3 / 2 L=3/2 L = 3/2 Theorem 3.4 .
