Lemma 4.4 — Simple cubic cloud expanders on every sufficiently large even order
OpenQuantumBipartiteTesting.Bipartiteness.Supplement.lemma_4_4complexity-theorygraph-theoryp2o-batch-stoc27sp2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information
There is an absolute and an order threshold such that every even admits a simple graph on vertices, every vertex of which has degree exactly three, satisfying
The constant precedes the order and graph. Empty and full cuts are included. These graphs provide the fixed clouds of the replacement construction.
Differences from the source:
- encoding: simple 3-regular graphs on [n] → oriented unordered edge pairs on Fin n, degree exactly three; reason: the published graph encoding counts each edge once and includes every simple graph
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Supplement_Unsigned
Formal statement
namespace QuantumBipartiteTesting.Bipartiteness.Supplement
open Finset
theorem lemma_4_4 :
∃ h₀ : ℝ, 0 < h₀ ∧ ∃ c₀ : ℕ, ∀ c ≥ c₀, Even c →
∃ J : Finset (Edge c), Cloud h₀ J := 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.4, printed page = PDF page 23