Persistence diagram of the upper-star Rips filtration equals its elder-rule barcode
ProvedPersistClust.Count.alg_diagram_eq_barcodeLet be a finite point cloud with vertex values , let be a symmetric distance matrix on the cloud and let be the corresponding Rips graph (two distinct points are adjacent when their distance is at most ). The upper-star Rips filtration of Eq. (3) has a 0-th persistence diagram , defined analytically: the multiplicity of a point of the extended plane is obtained from the rank function of the filtration (the number of connected components of meeting , for ) by taking infima of rank differences over small -windows.
Run the standard elder-rule (Kruskal) sweep on the same filtration: process the points in decreasing order of (any sort order of ); each new local maximum of the Rips graph starts a component (a birth at ); when vertex is processed, every neighbouring entry is merged into the entry of the highest root, and each absorbed root dies at level , giving the off-diagonal point (pairs with of zero persistence lie on the diagonal and are dropped); entries surviving at the end give the immortal points .
The theorem states that these two multiplicity functions coincide pointwise:
This is the classical fact that the persistence diagram of a finite tame filtration equals its barcode. It is the analytic core behind the counting claim of Theorem 4.8 of the source paper.
Formalization Note. ripsDiagram Dm g δ = mult (ripsRank Dm g δ) is defined in Definitions.Def_PersistClust_Count_Rips/..._Diagram; ripsBarcode g Dm δ σ is the combinatorial elder-rule pairing defined in Definitions.Def_PersistClust_Count_AlgBarcode, which must be imported. The hypothesis (symmetry) makes the Rips graph undirected; may break ties among equal -values arbitrarily.
import Mathlib import Definitions.Def_PersistClust_Count_Rips import Definitions.Def_PersistClust_Count_AlgBarcode
namespace PersistClust.Count
theorem alg_diagram_eq_barcode
(n : ℕ) (g : Fin n → ℝ) (Dm : Fin n → Fin n → ℝ)
(hDm : ∀ i j, Dm i j = Dm j i) (δ : ℝ) (σ : Fin n ≃ Fin n)
(hσ : IsSortOrder g σ) :
ripsDiagram Dm g δ = ripsBarcode g Dm δ σ := by sorry
end PersistClust.Count