← All papers
First page of Isometric embeddings of trees: why 32 leaves can require six dimensions, and bounds for every tree

Isometric embeddings of trees: why 32 leaves can require six dimensions, and bounds for every tree

Logan R. Chalmers

math.MG Aug 17, 2026 · v2 math.CO math.FA
Both main theorems, the 32-leaf six-dimension obstruction and the universal 1.162832 log2 t upper bound, are formalised in Lean with proofs archived on Zenodo.
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.

Fitzpatrick and Nowakowski asked whether the leaf-count lower bound ⌈log2 t⌉ on the isometric ℓ∞-dimension of a t-leaf tree can be strict. A conjecture of Aksoy, Kılıç and Koçak, and an unproved 2008 announcement, held that equality always holds.

Embedding dimension is reduced to the minimum size of an orientation cover of leaf pairs. Each cover is analysed through branch interfaces placed as regions in the hypercube Q_m. Packing arguments with cube-isometric initial segments, together with minority-count constraints, decide when the branches can partition the cube. A subadditive potential function bounds the packing capacities for general trees. Both main theorems are formalised in Lean using only standard axioms.

Every tree with at most 31 leaves attains ⌈log2 t⌉, but a specific 32-leaf cubic tree requires six dimensions. For a family of three-branch trees, the bound is attained exactly when the two larger branches have equal leaf counts. Every tree embeds in ⌈1.162832 log2 t⌉ dimensions, improving on the 1.44042 coefficient from 2005, and the excess stabilizes under repeated leaf expansion.