Theorem 6.14 — wheel bounds
OpenGraphTensorCP.Supplement.theorem_6_14graph-tensorsmax-cutp2o-gran-per-chapterp2o-plan-paperp2o-v1semidefinite-programmingtensor-rankwheel-graphs
Let be any field. For every , the wheel with rim vertices satisfies
When is even, the same value also equals the unstrengthened value .
Formalization Note The published SparseDisc.wheel m uses Option (Fin m) for the named wheel. Lean states the tensor bound for an arbitrary isomorphic representative on Fin (m+1), the vertex type expected by the published graph-tensor exponent.
Differences from the source:
- encoding: the source names the wheel without fixing a vertex type → Lean reuses the published
SparseDisc.wheel mand quantifies over an isomorphic representative onFin (m+1); reason: graph isomorphism only relabels the same wheel and keeps as the number of rim vertices. - encoding: the source writes → Lean performs natural-number division before coercion to ; reason: this is the same floor for .
Preamble
import Mathlib import Definitions.Def_GraphTensorCP_maxCut import Definitions.Def_GraphTensorCP_uCPDelta import Definitions.Def_GraphTensorCP_specWeight import Definitions.Def_GraphTensorCP_Supplement_uCP import Definitions.Def_GraphTensorCP_Supplement_uSDPDelta import Definitions.Def_SparseDisc_wheel universe u
Formal statement
namespace GraphTensorCP
namespace Supplement
/-- **Theorem 6.14 (wheel bounds)**, Zhou, *Asymptotic Rank of Weighted Graph Tensors via
Completely Positive Covers*, arXiv:2610.34273 (version of 2026-11-03), pp.65–67.
The statement retains the maximum-cut lower bound, both parity branches of the exact strengthened
values, and the extra equality with unstrengthened `U_CP` for even rims.
**Formalization Note.** The published `SparseDisc.wheel m` has vertex type `Option (Fin m)`.
The theorem is stated for an arbitrary isomorphic representative `G` on `Fin (m+1)`, the vertex
type required by the published graph-tensor exponent; hence `m` remains the number of rim vertices.
The floor in `⌊3m/2⌋` is natural-number division before coercion to `ℝ`. -/
theorem theorem_6_14 {K : Type u} [Field K] (m : ℕ) (hm : 3 ≤ m)
(G : SimpleGraph (Fin (m + 1))) [DecidableRel G.Adj]
(hG : Nonempty (G ≃g SparseDisc.wheel m)) :
(((3 * m) / 2 : ℕ) : ℝ) ≤ gammaF K (by omega) (G.adjMatrix ℝ) ∧
gammaF K (by omega) (G.adjMatrix ℝ) ≤ uCPDelta (G.adjMatrix ℝ) ∧
uCPDelta (G.adjMatrix ℝ) = uSDPDelta (G.adjMatrix ℝ) ∧
(Even m →
uCPDelta (G.adjMatrix ℝ) = 25 * (m : ℝ) / 16 ∧
uCP (G.adjMatrix ℝ) = 25 * (m : ℝ) / 16) ∧
(Odd m →
uCPDelta (G.adjMatrix ℝ) = (5 * (m : ℝ) + 1) ^ 2 / (16 * (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.14, pp.65–67