Corollary 4.8 — Both replacement-distribution testing promises
OpenQuantumBipartiteTesting.Bipartiteness.Supplement.corollary_4_8complexity-theorygraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-information
There are positive constants and an order threshold for which simple cubic clouds with edge expansion exist at every even order . For every fixed and every , all sufficiently large satisfy, uniformly for even with and for every such cloud,
The same precedes all ; this records both replacement-distribution promises, with quantitative meaning for .
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: c is an even logarithmic color count with sufficiently large coefficient → all even c at least 400 ln n, without an upper logarithmic bound; reason: the cut-failure sum and replacement promises improve with more independent matching colors; the logarithmic regime is included
- encoding: a fixed cubic cloud family and probability 1-o(1) → existence of clouds at every sufficiently large even order, and uniform delta thresholds for every qualifying cloud; reason: the same cloud expansion constant controls all orders; both probability clauses are retained
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Supplement_Unsigned
Formal statement
namespace QuantumBipartiteTesting.Bipartiteness.Supplement
open Finset
theorem corollary_4_8 :
∃ h₀ α : ℝ, 0 < h₀ ∧ 0 < α ∧ ∃ c₀ : ℕ,
(∀ c ≥ c₀, Even c → ∃ J : Finset (Edge c), Cloud h₀ J) ∧
∀ α' : ℝ, 0 < α' → α' < α → ∀ δ : ℝ, 0 < δ →
∃ n₀ : ℕ, 2 ≤ n₀ ∧ ∀ n ≥ n₀, ∀ c ≥ c₀,
Even c → 400 * Real.log n ≤ (c : ℝ) →
∀ e : Fin (n*c) ≃ Fin n × Fin c, ∀ J : Finset (Edge c), Cloud h₀ J →
(1 - δ ≤ FeasibleProb n (Center n) 1 c
(fun H => VertexExpander α (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, Corollary 4.8, printed page = PDF page 25