Theorem 6.10 — complete multipartite bounds
OpenGraphTensorCP.Supplement.theorem_6_10complete-multipartite-graphsgraph-tensorsmax-cutp2o-gran-per-chapterp2o-plan-paperp2o-v1tensor-rank
Let be any field, , and let be positive integers. Put
For ,
and
The exponent equals the maximum cut whenever or .
Differences from the source:
- encoding: the source uses named independent parts and vertices → Lean transports Mathlib’s complete multipartite graph on part-position pairs to
Fin N; reason: the transport is a graph isomorphism and preserves every displayed quantity. - encoding: the source writes and → Lean writes and ; reason: the variables are nonnegative integers and the conditions are equivalent without division.
Preamble
import Mathlib import Definitions.Def_GraphTensorCP_maxCut import Definitions.Def_GraphTensorCP_specWeight import Definitions.Def_GraphTensorCP_Supplement_uCP import Definitions.Def_GraphTensorCP_Supplement_completeMultipartiteGraph universe u
Formal statement
namespace GraphTensorCP
namespace Supplement
/-- **Theorem 6.10 (complete multipartite bounds)**, Zhou, *Asymptotic Rank of Weighted Graph
Tensors via Completely Positive Covers*, arXiv:2610.34273 (version of 2026-11-03), pp.62–63.
The maximum cut is exact, `U_CP` has both stated branches, and the exponent equals the maximum
cut in either of the two regimes from the paper.
**Formalization Note.** Parts are indexed by `Fin k`, all sizes are positive,
`N = Σ_i s_i`, `b = sup_i s_i` (the maximum on the nonempty finite index set), and `δ` is
`partitionImbalance s`. The conditions `b ≥ N/2` and `b ≤ N/2` are written without division as
`N ≤ 2b` and `2b ≤ N`. Natural subtraction in `b*(N-b)` is safe because `b` is a part size and
therefore at most `N`. -/
theorem theorem_6_10 {K : Type u} [Field K] {k : ℕ} (hk : 2 ≤ k) (s : Fin k → ℕ)
(hs : ∀ i, 0 < s i) :
let N := ∑ i, s i
let b := Finset.univ.sup s
let delta := partitionImbalance s
let G := completeMultipartiteGraph s
maxCut (G.adjMatrix ℝ) = ((N : ℝ) ^ 2 - (delta : ℝ) ^ 2) / 4 ∧
((N : ℝ) ^ 2 - (delta : ℝ) ^ 2) / 4 ≤
gammaF K (totalSize_gt_one hk s hs) (G.adjMatrix ℝ) ∧
gammaF K (totalSize_gt_one hk s hs) (G.adjMatrix ℝ) ≤ uCP (G.adjMatrix ℝ) ∧
(N ≤ 2 * b → uCP (G.adjMatrix ℝ) = (b : ℝ) * (N - b : ℕ)) ∧
(2 * b ≤ N → uCP (G.adjMatrix ℝ) = (N : ℝ) ^ 2 / 4) ∧
((N ≤ 2 * b ∨ delta = 0) →
gammaF K (totalSize_gt_one hk s hs) (G.adjMatrix ℝ) = maxCut (G.adjMatrix ℝ)) := 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.10, pp.62–63