Lemma 4.12 — Once-per-edge subdivisions preserve positive vertex expansion
OpenQuantumBipartiteTesting.Bipartiteness.Supplement.lemma_4_12complexity-theorygraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information
For every there is , depending only on , such that every simple -vertex graph of maximum degree at most four satisfying
has the following property: subdividing any set of at most distinct edges, once per selected edge, gives a graph with vertex expansion at least . The constant precedes the graph size, graph and subdivision set. This preserves the YES promise for arbitrary-size adjustments, and is not restricted to replacement graphs.
Differences from the source:
- encoding: an m-vertex simple graph and r at most m/4 once-subdivided edges → Fin m and a selected subset T of original edges with 4 card(T) at most m, labeled by any bijection; reason: the construction represents every permitted subdivision and excludes repeated subdivisions
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Supplement_Unsigned
Formal statement
namespace QuantumBipartiteTesting.Bipartiteness.Supplement
open Finset
theorem lemma_4_12 (ρ : ℝ) (hρ : 0 < ρ) :
∃ α : ℝ, 0 < α ∧ ∀ m : ℕ, ∀ G : Finset (Edge m),
IsGraph G → DegreeBound 4 G → EdgeExpander ρ G →
∀ T : Finset (Edge m), T ⊆ G → 4*T.card ≤ m →
∀ idx : {x // x ∈ T} ≃ Fin T.card,
VertexExpander α (Subdivision G 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.12, printed page = PDF page 26; proof pp.39–40