Procedure 1 with threshold τ outputs exactly the τ-prominent barcode pairs
ProvedPersistClust.Count.alg_numclust_eq_barcodeLet be a finite point cloud with vertex values , let be a symmetric non-negative distance matrix, a scale for the Rips graph , a prominence threshold, and a sort order of (a permutation with ).
Procedure 1 of the source paper processes the points in decreasing order of with a union-find structure whose entries are trees rooted at local maxima of in . While vertex is processed: if no processed Rips-neighbour exists, starts a new entry (a peak); otherwise joins the entry of its highest processed neighbour, every neighbouring entry whose root satisfies (prominence less than at the current level) is merged into it, and finally the whole entry is merged into the neighbouring entry with the highest root whenever its own root is not -prominent. The algorithm outputs the number numClusters of final entries whose root satisfies .
Let be the elder-rule barcode of the same filtration: the multiplicity function of the persistence pairs (birth at a peak, death by merging into an older component) with the immortal classes at . The theorem states that the algorithm outputs exactly the number of barcode points of prominence at least born above level :
Immortal points always have infinite prominence and contribute exactly when . This is the combinatorial correctness of the -thresholded merges: they kill exactly the non--prominent pairs, which is the step of the proof of Theorem 4.8 where the paper states that the algorithm discards the part of the Rips diagram and keeps the part located in .
Formalization Note. numClusters is defined in Definitions.Def_PersistClust_Count_Algorithm; ripsBarcode g Dm δ σ in Definitions.Def_PersistClust_Count_AlgBarcode (which must be imported). The region count is the cardinality of the set of copies with below the barcode multiplicity; the birth condition is the closed inequality .
import Mathlib import Definitions.Def_PersistClust_Count_Algorithm import Definitions.Def_PersistClust_Count_AlgBarcode
namespace PersistClust.Count
theorem alg_numclust_eq_barcode
(n : ℕ) (g : Fin n → ℝ) (Dm : Fin n → Fin n → ℝ)
(hDm : ∀ i j, Dm i j = Dm j i) (hDm0 : ∀ i j, 0 ≤ Dm i j)
(δ τ : ℝ) (hδ : 0 ≤ δ) (hτ : 0 < τ)
(σ : Fin n ≃ Fin n) (hσ : IsSortOrder g σ) :
(numClusters g Dm δ τ σ : ℕ∞)
= {q : (EReal × EReal) × ℕ | (q.2 : ℕ∞) < ripsBarcode g Dm δ σ q.1 ∧
q.1.2 ≤ q.1.1 - (τ : EReal) ∧ (τ : EReal) ≤ q.1.1}.encard := by sorry
end PersistClust.Count