Weighted minimum cut
DefinitionGraphTensorCP_Supplement_minCutgraph-tensorsgraph-theorymin-cutp2o-gran-per-chapterp2o-plan-paperp2o-v1tensor-subrank
For a symmetric nonnegative zero-diagonal matrix of order , the minimum cut weight is
It is the weighted edge connectivity of the support graph and is the exact logarithmic asymptotic subrank of a weighted graph tensor.
Formalization Note This reuses the published cutWeight and takes an infimum over the finite type of nonempty proper subsets of Fin n. For that type is nonempty, so the infimum is the ordinary minimum.
Definition code
import Mathlib
import Definitions.Def_GraphTensorCP_maxCut
namespace GraphTensorCP
namespace Supplement
/-- The **minimum cut weight** of a symmetric nonnegative zero-diagonal matrix `W`
(Zhou, *Asymptotic Rank of Weighted Graph Tensors via Completely Positive Covers*,
arXiv:2610.34273 (version of 2026-11-03), Definition 2.27, p.26, used in Theorem B.5, p.80):
the minimum of `cutWeight W S` over nonempty proper vertex sets.
**Formalization Note.** The infimum is over the same finite subtype as the published `maxCut`.
For the paper's standing assumption `n ≥ 2` the subtype is nonempty and finite, so this is the
ordinary minimum. -/
noncomputable def minCut {n : ℕ} (W : Matrix (Fin n) (Fin n) ℝ) : ℝ :=
⨅ S : {S : Finset (Fin n) // S.Nonempty ∧ S ≠ Finset.univ}, cutWeight W S.1
end Supplement
end GraphTensorCP
Source
Zhou, Asymptotic Rank of Weighted Graph Tensors via Completely Positive Covers, arXiv:2610.34273 (version of 2026-11-03), Definition 2.27, p.26; Theorem B.5, p.80