Lemma 4.6 — Replacement NO instances have distance at least α′/12
OpenQuantumBipartiteTesting.Bipartiteness.Supplement.lemma_4_6complexity-theorygraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-information
For every fixed , all sufficiently large intermediate orders , every , and every fixed simple cubic cloud , every in the support of the actual feasible law at satisfies
Consequently, this farness event has probability exactly one. The support and the probability are both computed from the actual sampling data. No upper bound on is imposed. This supplies the replacement NO promise.
Differences from the source:
- encoding: vertices [n] and asymptotic notation → Fin n, natural logarithms and explicit uniform constants/thresholds; reason: bijective vertex labeling and logarithm-base changes preserve all source instances
- generalization: logarithmically many colors and an expanding fixed cubic cloud → every positive color count and every simple cubic cloud; reason: the separated-block distance argument uses neither cloud expansion nor logarithmic color growth; it includes every source instance
- encoding: epsilon-far from expansion → an ENNReal infimum over actual simple targets, normalized by 4nc; reason: an empty target class has infinite distance; support-wise farness and probability one are both retained
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Supplement_Unsigned
Formal statement
namespace QuantumBipartiteTesting.Bipartiteness.Supplement
open Finset
theorem lemma_4_6 (α' : ℝ) (hα : 0 < α') :
∃ n₀ : ℕ, 2 ≤ n₀ ∧ ∀ n ≥ n₀, ∀ c : ℕ, 0 < c →
∀ e : Fin (n*c) ≃ Fin n × Fin c, ∀ J : Finset (Edge c), Cubic J →
(∀ H : Finset (ColoredEdge n c), InSupport n (Center n) 2 c H →
ExpansionFar 4 (α'/12) α' (Replacement e J H)) ∧
FeasibleProb n (Center n) 2 c
(fun H => ExpansionFar 4 (α'/12) α' (Replacement e J H)) = 1 := by sorry
end QuantumBipartiteTesting.Bipartiteness.Supplement
Source
Chandrima Kayal, Sayantan Sen, Dániel Szabó, STOC 2027 submission #878 (October 2026), https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/878.pdf, Lemma 4.6, printed page = PDF page 24