Lemma 4.11 — Subdivided NO instances retain distance α′/12
OpenQuantumBipartiteTesting.Bipartiteness.Supplement.lemma_4_11complexity-theorygraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-information
Fix any . For all sufficiently large intermediate orders , let be any graph in the support of the feasible law at and let for any fixed simple cubic cloud with vertices. Put . For every set of distinct original edges, subdivide each selected edge exactly once, using a separate fresh vertex, to obtain on vertices. Then
The selection can include external edges; the fresh vertex labeling is arbitrary. This retains the exact NO farness with the new vertex-count normalization, permitting arbitrary-size final instances.
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: subdivide r distinct edges once each → a finite selected edge set and arbitrary bijective fresh-vertex labels on Fin (nc+r); reason: no selection is excluded and the distance normalization uses the resulting size
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Supplement_Unsigned
Formal statement
namespace QuantumBipartiteTesting.Bipartiteness.Supplement
open Finset
theorem lemma_4_11 (α' : ℝ) (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 →
∀ T : Finset (Edge (n*c)), T ⊆ Replacement e J H → 4*T.card ≤ n*c →
∀ idx : {x // x ∈ T} ≃ Fin T.card,
ExpansionFar 4 (α'/12) α' (Subdivision (Replacement e J H) T idx) := 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.11, printed page = PDF page 26; proof p.39