Lemma 3.8 — Independent rounding
OpenSubquadCutReach.Faster.Supplement.lemma_3_8graph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1randomized-rounding
Let be a simple graph on labelled vertices and let be an integer. Let be integral orientation rules (for example those of Algorithm 1) and their average fractional rule. For each pair choose an iteration uniformly from , independently over the pairs, and give the pair its direction in . Let be the orientation of induced by the resulting rule. Then
This is the rounding step of the warm-up protocol: one random integral orientation whose imbalance stays close to that of the average.
Formalization Note The independent uniform choices are the uniform law on choice functions from the pairs to , so the probability is the fraction of choice functions for which the bound holds.
Differences from the source:
- generalization: the rules generated by Algorithm 1 → every family of integral rules
z : Fin T → Rule n; reason: the proof uses only that each is integral, and ; takingz t := warmRule H b T tgives the source's statement - encoding: independent uniform choices → a uniform choice function
I : Pairs n → Fin T, probability as a counting ratio (roundingProb); reason: the product of independent uniform laws is the uniform law on choice functions - encoding: the sampled orientation and →
induced H (roundRule z I)andfractionalImbalance H (avgRules z); reason: the same objects
Preamble
import Definitions.Def_SubquadCutReach_Faster_Supplement_Warmup set_option autoImplicit false
Formal statement
namespace SubquadCutReach.Faster.Supplement
open SubquadCutReach.Faster
/-- Lemma 3.8, p. 9 (PDF 11), restated p. 15 (PDF 17). Stated for every family of `T`
integral rules, in particular those of Algorithm 1. -/
theorem lemma_3_8 (n T : ℕ) (hT1 : 1 ≤ T) (hTn : T ≤ n) (H : SimpleGraph (Fin n))
(z : Fin T → Rule n) :
(1 : ℝ) / 2 ≤ roundingProb z fun D =>
l1 (fun v => (imbalance (induced H D) v : ℝ) - fractionalImbalance H (avgRules z) v) ≤
4 * (n : ℝ) ^ 2 / Real.sqrt (T : ℝ) := by sorry
end SubquadCutReach.Faster.Supplement
Source
Henry Fleischmann, Sagnik Mukhopadhyay, Swagato Sanyal, STOC 2027 submission #503 (October 2026), p. 9, Lemma 3.8 (PDF p. 11); restated p. 15 (PDF p. 17), proof pp. 15–16 (PDF pp. 17–18)