Proof of Theorem 1.2 — Algorithm 3 with and (5.3) separates every -edge with probability (finite- form)
ProvedMultiwayCut.theorem_1_2_densityapproximation-algorithmsmultiway-cutp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1randomized-rounding
Run Algorithm 3 with and the transformation (5.1) defined by the matrix (5.3). The paper shows (p.8) that for edges of type
Stated in the form the corrected reduction needs: for every there is a constant such that for every -edge with parameter (in any order of the coordinates, any ), the probability that Algorithm 3 assigns and to different terminals is at most
In particular the cut density of Algorithm 3 is at most for every type .
Differences from the source:
- generalization: for the cut density → on every -edge, with depending only on ; reason: the printed bound is true, and the finite- form implies it (divide by and let ); the stronger form is the one the corrected reduction (
karger_reduction) consumes, since the bound alone does not imply the approximation ratio - encoding: edges of type after sorting the coordinates → an -edge in an arbitrary order
π; reason: the paper's "there exists an order of the coordinates", p.4 - encoding: the paper's coordinates and terminals , →
Fin kfrom , ; reason: Lean convention; the same statement after the index shift - reading: the matrix (5.3) printed with "…" for a general →
A53 kfor every , defined by the entry formula (the top-left block of the printed pattern); reason: the paper never restricts ; this is the only matrix consistent with the printed pattern
Preamble
import Mathlib import Definitions.Def_MultiwayCut_Algorithm3 import Definitions.Def_MultiwayCut_CutDensity import Definitions.Def_MultiwayCut_Transformation import Definitions.Def_MultiwayCut_A53
Formal statement
namespace MultiwayCut
/-- **Cut density of the 297/229 algorithm** (finite-`ε` form), Buchbinder, Schwartz
& Weizman, *Simplex Transformations and the Multiway Cut Problem*, manuscript of Nov. 1, 2016,
proof of Theorem 1.2, p.8: Algorithm 3 with `p = 121/229` and the transformation defined by the
matrix (5.3) has, for edges of type `(i, j)`,
`(1 − p) α_{i,j} + p β_{i,j} ≤ 2p + (1 − p)(55/108) Σ_{ℓ≠i,j} u_ℓ + (uᵢ + u_j)((1 − p)(44/27) − p)
= 242/229 + (55/229) Σ_{ℓ=1}^k u_ℓ = 297/229`.
Posed in the form the corrected reduction (`karger_reduction`) consumes: for every `k ≥ 1` there
is a constant `C` such that on every `(i, j)`-edge `(u, v)` (any order `π`, any `i < j`) with
parameter `ε`, the separation probability of Algorithm 3 is at most `297/229 · ε + C ε²`. This
implies the printed lim sup bound `≤ 297/229`.
**Formalization Note.** `C` may depend on `k` but not on the edge. -/
theorem theorem_1_2_density {k : ℕ} [NeZero k] :
∃ C : ℝ, ∀ (π : Equiv.Perm (Fin k)) (i j : Fin k) (ε : ℝ) (u v : Fin k → ℝ),
IsIJEdge π i j ε u v →
alg3Sep (121 / 229) (quadTransform (A53 k)) u v ≤ 297 / 229 * ε + C * ε ^ 2 := by sorry
end MultiwayCut
Source
Buchbinder, Schwartz & Weizman, Simplex Transformations and the Multiway Cut Problem, manuscript of Nov. 1, 2016, proof of Theorem 1.2, p.8
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.