# On Hamming-Lipschitz Type Stability of the Subdominant (Minmax) Ultrametric: Theory and Simple Proofs

arXiv: https://arxiv.org/abs/2608.04014 · HTML: https://mlsanity.com/paper/2608.04014/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 14 of its 33 references that are in the map.
- First posted on arXiv 27 Apr 2026.

## Builds on (most cited first, 14 of 14)

- [Ultrametric Fitting by Gradient Descent](https://mlsanity.com/paper/1905.10566/) (2019)
- [View-Consistent Hierarchical 3D Segmentation Using Ultrametric Feature Fields](https://mlsanity.com/paper/2405.19678/) (2024)
- [v-PuNNs: van der Put Neural Networks for Transparent Ultrametric Representation Learning](https://mlsanity.com/paper/2508.01010/) (2025)
- [Stable and consistent density-based clustering via multiparameter persistence](https://mlsanity.com/paper/2005.09048/) (2020)
- [Learning Ultrametric Trees for Optimal Transport Regression](https://mlsanity.com/paper/2210.12288/) (2022)
- [Temporal Hierarchical Clustering](https://mlsanity.com/paper/1707.09904/) (2017)
- [Engineering Massively Parallel MST Algorithms](https://mlsanity.com/paper/2302.12199/) (2023)
- [Convergence to Lexicographically Optimal Base in a (Contra)Polymatroid and Applications to Densest Subgraph and Tree Packing](https://mlsanity.com/paper/2305.02987/) (2023)
- [Gromov-Hausdorff stability of linkage-based hierarchical clustering methods](https://mlsanity.com/paper/1311.5068/) (2013)
- [Statistical Properties of the Single Linkage Hierarchical Clustering Estimator](https://mlsanity.com/paper/1511.07715/) (2015)
- [Component Tree Loss Function: Definition and Optimization](https://mlsanity.com/paper/2101.08063/) (2021)
- [Massively Parallel Minimum Spanning Tree in General Metric Spaces](https://mlsanity.com/paper/2408.06455/) (2024)
- [Hierarchical clustering with maximum density paths and mixture models](https://mlsanity.com/paper/2503.15582/) (2025)
- [Dynamic Matroids: Base Packing and Covering](https://mlsanity.com/paper/2511.15460/) (2025)

## Abstract (arXiv)

The subdominant (minmax) ultrametric is a canonical tree-structured summary of a dissimilarity matrix, arising equivalently as the ultrametric induced by single-linkage clustering. While its classical stability theory is usually formulated in ℓ_∞ or Gromov--Hausdorff terms, such bounds are poorly suited to sparse perturbations that alter only a few pairwise distances. We develop an ℓ0-type stability theory for this operator. Our analysis shows that sparse edits propagate only through the minimum spanning tree (MST): a pairwise ultrametric value can change only if its tree path crosses an edited edge or a cut newly exposed by an edited off-tree edge. This yields a sharp per-edit exposed-cut score and a tree-only global envelope, leading to Hamming--Lipschitz bounds on the number of ultrametric entries that can change. We also prove sharpness results showing that this dependence on tree geometry is unavoidable: under strict cut separation the tree-edge bound is attained exactly, and for off-tree edits there are explicit families in which one edited distance changes Theta(n2) ultrametric entries. In addition, we prove a conditional near-additivity principle for multiple edits under certified large per-edit changed regions and negligible aggregate overlap. Experiments on deep-embedding graphs show that the resulting structural scores provide useful vulnerability diagnostics for hierarchical representations.