(50), p. 204 — the coarsest partition refining all R_t, C_t of a cut decomposition with error εn² is 2ε-pseudo-regular
ProvedFriezeKannan.PseudoReg.claim_50Let be a finite simple graph with vertices and adjacency matrix , and let be a real number. Let , , be cut matrices with and , and . Suppose the decomposition has error at most in the cut norm:
Let be the coarsest partition of into subsets such that each or is a union of parts of the partition. Then
that is, for all disjoint .
Combined with a cut decomposition of width , whose atom partition has at most parts, this produces pseudo-regular partitions of every graph with a number of parts depending only on : a weak form of Szemerédi's regularity lemma.
Formalization Note. The paper takes to be "cut matrices as defined in Theorem 2", the output of a randomized algorithm whose error satisfies (for a matrix ). The proof of (50) uses only this error bound, so the formal statement takes it as the hypothesis, for all pairs (the cut norm is a maximum over all pairs); the paper's proof phrases it through the symmetrised error , which is not needed when the bound is assumed for directly. The width of the decomposition plays no role in (50) and is not constrained. The partition is Mathlib's Finpartition.atomise of . The diagonal densities in are block averages, as explained in the definitions item.
import Mathlib import Definitions.Def_FriezeKannan_PseudoReg_Setting
namespace FriezeKannan.PseudoReg
theorem claim_50 {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) [DecidableRel G.Adj] (ε : ℝ)
(s : ℕ) (Rs Cs : Fin s → Finset V) (d : Fin s → ℝ)
(hD : ∀ S T : Finset V,
|blockSum (G.adjMatrix ℝ - cutSum Rs Cs d) S T| ≤ ε * (Fintype.card V : ℝ) ^ 2) :
IsPseudoRegular G (atomPartition Rs Cs) (2 * ε) := by sorry
end FriezeKannan.PseudoReg
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.