Procedure 1 realizes every tau-prominent barcode copy
ProvedPersistClust.Count.alg_numclust_eq_barcode_reverseLet 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 (multiplicities of pairs , immortals at ). This lemma is the reverse half of the equality
namely
Every barcode copy in the region is realized by a distinct output cluster: the underlying peak root of the point survives the -sweep because its recorded death prominence is at least (or it is immortal). The per-root death map of the plain () sweep identifies each barcode point with a peak root, and the -thresholded merge rules preserve exactly those roots whose prominence is at least (and the immortal roots), so the surviving roots cover all region copies.
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_reverse
(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