(47), p. 203 — A(S,T) = e(S,T), A_Q(S,T) = Σ d_{i,j}|S_i||T_j|, and A(S,T) − A_Q(S,T) = Δ_Q(S,T)
ProvedFriezeKannan.PseudoReg.eq_47graph-densityp2o-batch-pfp2ap2o-gran-per-chapterp2o-plan-paperp2o-v1pseudo-regular-partition
Let be a finite simple graph with adjacency matrix , let be a partition of with index set , and let be the density between and . For disjoint , with and ,
and consequently
The identity rewrites the deviation from regularity as a block sum of the matrix , which turns pseudo-regularity into a statement about the cut norm of .
Formalization Note. is the number of ordered adjacent pairs in (Mathlib's interedges), which for disjoint is the number of edges between them. The diagonal densities are block averages , as explained in the definitions item; with the paper's printed the identity fails. The disjointness hypothesis is kept as on the page.
Preamble
import Mathlib import Definitions.Def_FriezeKannan_PseudoReg_Setting
Formal statement
namespace FriezeKannan.PseudoReg
theorem eq_47 {V : Type*} [Fintype V] [DecidableEq V]
(G : SimpleGraph V) [DecidableRel G.Adj]
(Q : Finpartition (Finset.univ : Finset V)) (S T : Finset V) (hST : Disjoint S T) :
blockSum (G.adjMatrix ℝ) S T = ((G.interedges S T).card : ℝ) ∧
blockSum (blockAvg Q (G.adjMatrix ℝ)) S T =
∑ Vi ∈ Q.parts, ∑ Vj ∈ Q.parts,
(G.edgeDensity Vi Vj : ℝ) * ((S ∩ Vi).card : ℝ) * ((T ∩ Vj).card : ℝ) ∧
blockSum (G.adjMatrix ℝ) S T - blockSum (blockAvg Q (G.adjMatrix ℝ)) S T =
delta G Q S T := by sorry
end FriezeKannan.PseudoReg
Source
Frieze and Kannan, Quick approximation to matrices and applications, Combinatorica 19 (1999), p. 203, §5.1, display (47) and the two equalities before it
Human review
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.