no. 14 · Friday 13 November 2026
Isometric embeddings of trees: why 32 leaves can require six dimensions, and bounds for every tree
Abstract
We identify the first failure of the $\lceil\log_2 t\rceil$ leaf-count bound for isometric embeddings of $t$-leaf trees under the maximum norm. Every tree with at most $31$ leaves attains the bound, but a $32$-leaf tree requires six dimensions. This answers a question of Fitzpatrick and Nowakowski and disproves a conjecture of Aksoy, Kılıç and Koçak. We explain this failure by showing how requirements within and between branches force an additional coordinate. For a family of three-branch trees, we prove that the leaf bound is attained exactly when the two larger branches have equal leaf counts; otherwise, one additional coordinate is necessary. We also prove that every tree embeds in $\lceil 1.162832\log_2 t\rceil$ dimensions, improving the coefficient of approximately $1.44042$ established in 2005. These results hold for arbitrary positive edge lengths and the entire metric realization. We also construct infinite families in which the excess persists under repeated leaf expansion. Both main theorems are formalised in Lean using only standard axioms.
- comments
- 18 pages. Both main theorems are formalised in Lean using only standard axioms. The formalisation is available at https://doi.org/10.5281/zenodo.23664556
- fields
- Metric Geometry, Combinatorics, Functional Analysis