Theorem 6.6 — odd-cycle bound
OpenGraphTensorCP.Supplement.theorem_6_6graph-tensorsmax-cutodd-cyclesp2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programmingtensor-rank
Let be any field. For every odd integer , the cycle satisfies
Thus the strengthened copositive and semidefinite programs have the same exact value on every odd cycle and leave only a gap above the maximum-cut lower bound.
Differences from the source:
- encoding: the source labels the cycle vertices → Lean uses Mathlib’s
cycleGraph monFin m; reason: this is the same cycle after shifting the vertex labels by one.
Preamble
import Mathlib.Combinatorics.SimpleGraph.CycleGraph import Definitions.Def_GraphTensorCP_uCPDelta import Definitions.Def_GraphTensorCP_specWeight import Definitions.Def_GraphTensorCP_Supplement_uSDPDelta universe u
Formal statement
namespace GraphTensorCP
namespace Supplement
/-- **Theorem 6.6 (odd-cycle bound)**, Zhou, *Asymptotic Rank of Weighted Graph Tensors via
Completely Positive Covers*, arXiv:2610.34273 (version of 2026-11-03), pp.59–60.
**Formalization Note.** `SimpleGraph.cycleGraph m` is the cycle on the 0-based vertex type
`Fin m`; graph parameters are evaluated on its real adjacency matrix. The hypotheses retain both
the lower threshold `m ≥ 3` and oddness. -/
theorem theorem_6_6 {K : Type u} [Field K] (m : ℕ) (hm : 3 ≤ m) (hodd : Odd m) :
(m : ℝ) - 1 ≤ gammaF K (by omega) ((SimpleGraph.cycleGraph m).adjMatrix ℝ) ∧
gammaF K (by omega) ((SimpleGraph.cycleGraph m).adjMatrix ℝ) ≤
uCPDelta ((SimpleGraph.cycleGraph m).adjMatrix ℝ) ∧
uCPDelta ((SimpleGraph.cycleGraph m).adjMatrix ℝ) =
uSDPDelta ((SimpleGraph.cycleGraph m).adjMatrix ℝ) ∧
uSDPDelta ((SimpleGraph.cycleGraph m).adjMatrix ℝ) = (m : ℝ) ^ 2 / (m + 1) ∧
(m : ℝ) ^ 2 / (m + 1) = (m : ℝ) - 1 + 1 / (m + 1) := by sorry
end Supplement
end GraphTensorCP
Source
Zhou, Asymptotic Rank of Weighted Graph Tensors via Completely Positive Covers, arXiv:2610.34273 (version of 2026-11-03), Theorem 6.6, pp.59–60