Leaf-to-leaf paths of many lengths

Abstract

We prove that every tree of maximum degree $\hat{I}”$ with $\ell$ leaves contains paths between leaves of at least ${\log }_{\hat{I}”-1}((\hat{I}”-2)\ell )$ distinct lengths. This settles in a strong form a conjecture of Narins, Pokrovskiy and Szabó. We also make progress towards another conjecture of the same authors, by proving that every tree with no vertex of degree 2 and diameter at least $N$ contains $N^{2/3}/6$ distinct leaf-to-leaf path lengths between $0$ and $N$.

This article has been superseded by arXiv:2504.11656