A 32-leaf tree requiring six coordinates for an isometric ${\ell }_{\infty }$ embedding

Abstract

We disprove the conjecture that every tree with t leaves embeds isometrically into ${\ell }_{\infty }^{\lceil {\log }_{2}t\rceil }$. We construct a 32-leaf tree whose least isometric ${\ell }_{\infty }$-dimension is six rather than five, and prove that every tree with at most 31 leaves attains the conjectured bound; Brigham et al. had recorded equality through 21 leaves. Thus 32 is the first failure, and the example answers affirmatively a question of Fitzpatrick and Nowakowski from 2000. The same topology has dimension six under every assignment of positive edge lengths, and therefore also disproves the later sharp leaf-threshold conjecture for weighted metric trees.

6 pages. Ancillary material and verification code available at Zenodo, https://zenodo.org/records/21965426