§5.1, p. 204 — D = D⁽¹⁾ + ⋯ + D⁽ˢ⁾ is compatible with the atom partition of the R_t, C_t
ProvedFriezeKannan.PseudoReg.cutSum_compatiblecut-matrixp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pseudo-regular-partition
Let be a finite set, and let , , be cut matrices on , with and . Let be the coarsest partition of such that each and each is a union of parts. Then
is compatible with : is constant over every block .
This is the property of the cut decomposition that lets Lemma 7(a) be applied with in the proof of claim (50).
Formalization Note. The partition is Mathlib's Finpartition.atomise of the family , whose parts are the nonempty atoms of the family.
Preamble
import Mathlib import Definitions.Def_FriezeKannan_PseudoReg_Setting
Formal statement
namespace FriezeKannan.PseudoReg
theorem cutSum_compatible {V : Type*} [Fintype V] [DecidableEq V]
(s : ℕ) (Rs Cs : Fin s → Finset V) (d : Fin s → ℝ) :
Compatible (atomPartition Rs Cs) (cutSum Rs Cs d) := by sorry
end FriezeKannan.PseudoReg
Source
Frieze and Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), p. 204, §5.1, "note that D is compatible with P"
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.