Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound

In STOC’95 [ADMSS’95] Arya et al. showed that any set of $n$ points in ${\mathbb{R}}^d$ admits a $(1+ϵ)$-spanner with hop-diameter at most 2 (respectively, 3) and $O(n\log n)$ edges (resp., $O(n\log \log n)$ edges). They also gave a general upper bound tradeoff of hop-diameter at most $k$ and $O(n{\alpha }_k(n))$ edges, for any $k\ge 2$. The function ${\alpha }_k$ is the inverse of a certain Ackermann-style function at the $\lfloor k\mathrm{/}2\rfloor$th level of the primitive recursive hierarchy, where $\alpha_0(n) = \lceil n/2 \rceil$,$\alpha_1(n) = \left\lceil \sqrt{n} \right\rceil$,$\alpha_2(n) = \lceil \log{n} \rceil$,$\alpha_3(n) = \lceil \log\log{n} \rceil$,$\alpha_4(n) = \log^* n$,$\alpha_5(n) = \lfloor \frac{1}{2} \log^*n \rfloor$, \ldots. Roughly speaking, for $k\ge 2$ the function ${\alpha }_k$ is close to $\lfloor \frac{k-2}{2} \rfloor$-iteratedlog-starfunction,i\mathrm{.}e\mathrm{.},$\log$with$\lfloor \frac{k-2}{2} \rfloor$stars\mathrm{.}Also,$\alpha_{2\alpha(n)+4}(n) \le 4$,where$\alpha(n)$ is the one-parameter inverse Ackermann function, which is an extremely slowly growing function. Whether or not this tradeoff is tight has remained open, even for the cases $k=2$ and $k=3$. Two lower bounds are known: The first applies only to spanners with stretch 1 and the second is sub-optimal and applies only to sufficiently large (constant) values of $k$. In this paper we prove a tight lower bound for any constant $k$: For any fixed $ϵ>0$, any $(1+ϵ)$-spanner for the uniform line metric with hop-diameter at most $k$ must have at least $\mathrm{\Omega }(n{\alpha }_k(n))$ edges.