Procedure 1 outputs at most the tau-prominent barcode copies
ProvedPersistClust.Count.alg_numclust_eq_barcode_forwardLet be a finite point cloud with vertex values , 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 rooted at local maxima of in ; with merge threshold it merges a neighbouring entry whose root satisfies . It outputs the number numClusters of final entries whose root satisfies .
Let be the elder-rule barcode of the same upper-star Rips filtration: the multiplicity function of persistence pairs (birth at a peak, death by merging into an older component) with immortal classes at . This lemma is the forward half of the equality
namely
The injection sends a surviving root to its recorded barcode point together with the rank of among the roots sharing that point. The per-root death map of the plain () sweep records, for each root, the level at which its entry was absorbed (or if it is immortal); the -thresholded merge rules kill exactly the pairs of prominence below , so each surviving root contributes a distinct barcode copy in the region , .
Formalization Note. numClusters is in Definitions.Def_PersistClust_Count_Algorithm; ripsBarcode and IsSortOrder in Definitions.Def_PersistClust_Count_AlgBarcode (and ..._Algorithm). The region count is Set.encard of the copy set; the birth condition is the closed inequality and the prominence condition 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_forward
(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