Lemma 3.3 — random-sign frustration bound
ProvedQuantumBipartiteTesting.Bipartiteness.lemma_3_3complexity-theorygraph-property-testingp2o-batch-stoc27ap2o-gran-per-chapterp2o-plan-paperp2o-v1quantum-information
Let be any finite colored multigraph on vertices, with distinct colored edges, and assign independent uniform signs to those edges. For every ,
where is binary entropy in base two. There is a positive absolute constant such that, for every such graph with ,
The constants are independent of the graph and its color count. This is the farness estimate for random signed constraints.
Differences from the source:
- encoding: vertices [N], distinct undirected edges and color-labeled parallel edges → Fin N; oriented unordered pairs; color included in each edge identifier; reason: bijections relabel vertices; differently colored parallel constraints remain distinct
Preamble
import Definitions.Def_QuantumBipartiteTesting_Bipartiteness_Reduction
Formal statement
namespace QuantumBipartiteTesting.Bipartiteness
open Finset
theorem lemma_3_3 :
(∀ N colors : ℕ, ∀ F : Finset (ColoredEdge N colors), Consistent F →
∀ τ : ℝ, 0 < τ → τ < 1/2 →
FrustrationTail F (τ * F.card) ≤
(2 : ℝ) ^ ((N : ℝ) - (1 - BinaryEntropy τ) * F.card)) ∧
(∃ c : ℝ, 0 < c ∧ ∀ N colors : ℕ, ∀ F : Finset (ColoredEdge N colors),
Consistent F → (13/10 : ℝ) * N ≤ F.card →
FrustrationTail F ((F.card : ℝ)/50) ≤ (2 : ℝ) ^ (-c*N)) := by sorry
end QuantumBipartiteTesting.Bipartiteness
Source
Chandrima Kayal, Sayantan Sen, Dániel Szabó, STOC 2027 submission #878 (October 2026), Lemma 3.3, PDF = printed page 14. https://github.com/sigact-stoc/stoc2027/releases/download/papers-1/878.pdf
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.