Lemma 4.5 — Replacement graph preserves expansion
OpenQuantumBipartiteTesting.Bipartiteness.Supplement.lemma_4_5complexity-theorygraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-strengthenedp2o-v1quantum-information
For any there is , depending only on these parameters, with the following property. Let be any consistent colored matching multigraph on vertices with colors and
For every fixed simple cubic cloud with edge expansion , the actual replacement graph has vertex expansion at least . Any fixed bijective labeling of its vertices is allowed. This transfers the YES expansion promise to maximum-degree-four graphs.
Differences from the source:
- encoding: replacement vertices (u,j) and a positive constant depending only on beta,h0 → any fixed bijective labeling of Fin (n*c), with alpha quantified before n,c,J,H; reason: this makes the stated uniformity and free vertex labeling explicit
- generalization: the section constructs clouds at logarithmic color counts from one fixed expanding cubic family → every positive color count and every simple cubic cloud with the stated edge expansion; reason: the A.8 cut argument depends only on beta and h0, so the statement includes every cloud and color count used in the source
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Supplement_Unsigned
Formal statement
namespace QuantumBipartiteTesting.Bipartiteness.Supplement
open Finset
theorem lemma_4_5 (β h₀ : ℝ) (hβ : 0 < β) (hh : 0 < h₀) :
∃ α : ℝ, 0 < α ∧ ∀ n c : ℕ, 0 < c →
∀ e : Fin (n*c) ≃ Fin n × Fin c, ∀ J : Finset (Edge c), Cloud h₀ J →
∀ H : Finset (ColoredEdge n c), Consistent H → ColoredExpansion β H →
VertexExpander α (Replacement e J H) := 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.5, printed page = PDF page 23; proof p.38