Sparse Euclidean Spanners with Tiny Diameter: A Tight Lower Bound

In STOC\u2795 [ADMSS95] Arya et al. showed that any set of n points in 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 ?_k(n)) edges, for any k?2. The function ?_k is the inverse of a certain Ackermann-style function at the ?k/2?th level of the primitive recursive hierarchy, where ??(n)=?n/2?, ??(n)=??n?, ??(n)=?log n?, ??(n)=?log log n?, ??(n)=log^* n, ??(n)=?1/2 log^*n?, .... Roughly speaking, for k?2 the function ?_{k} is close to ?(k-2)/2?-iterated log-star function, i.e., log with ?(k-2)/2? stars. Also, ?_{2?(n)+4}(n)?4, where ?(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 ?(n ?_k(n)) edges