A Lower Bound for Light Spanners in General Graphs
<|reference_start|>A Lower Bound for Light Spanners in General Graphs: A recent upper bound by Le and Solomon [STOC '23] has established that every $n$-node graph has a $(1+\varepsilon)(2k-1)$-spanner with lightness $O(\varepsilon^{-1} n^{1/k})$. This bound is optimal up to its dependence on $\varepsilon$; the remaining open problem is whether this dependence can be improved or perhaps even removed entirely.   We show that the $\varepsilon$-dependence cannot in fact be completely removed. For constant $k$ and for $\varepsilon:= \Theta(n^{-\frac{1}{2k-1}})$, we show a lower bound on lightness of $$\Omega\left( \varepsilon^{-1/k} n^{1/k} \right).$$ For example, this implies that there are graphs for which any $3$-spanner has lightness $\Omega(n^{2/3})$, improving on the previous lower bound of $\Omega(n^{1/2})$.   An unusual feature of our lower bound is that it is conditional on the girth conjecture with parameter $k-1$ rather than $k$. We additionally show that this implies certain technical limitations to improving our lower bound further. In particular, under the same conditional, generalizing our lower bound to all $\varepsilon$ \emph{or} obtaining an optimal $\varepsilon$-dependence are as hard as proving the girth conjecture for all constant $k$.<|reference_end|>
@article{bodwin2024a,
    title={A Lower Bound for Light Spanners in General Graphs},
    author={Greg Bodwin and Jeremy Flics},
    journal={arXiv preprint arXiv:2406.04459},
    year={2024},
    archivePrefix={arXiv},
    eprint={2406.04459},
    primaryClass={cs.DS}
}