New Theory Explains Ultrametric Stability to Sparse Edits

The subdominant (minmax) ultrametric provides a canonical tree-structured summary of dissimilarity matrices, often derived from single-linkage clustering. While its stability has been studied using traditional metrics, these are often inadequate for sparse perturbations where only a few pairwise distances are altered. This paper introduces an L0-type stability theory specifically designed for such sparse edits. The analysis reveals that changes from sparse edits propagate exclusively through the Minimum Spanning Tree (MST). An ultrametric value can only change if its tree path crosses an edited edge or a cut newly exposed by an off-tree edge modification. The theory yields sharp per-edit exposed-cut scores and global tree-only envelopes, leading to Hamming-Lipschitz bounds on the number of ultrametric entries that can be affected. Sharpness results demonstrate that this dependence on tree geometry is unavoidable, with explicit examples showing how a single edited distance can change a large number of ultrametric entries. This framework provides valuable vulnerability diagnostics for hierarchical data representations.