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+) (2k-1) -spanner with lightness O (^-1 n^1/k). This bound is optimal up to its dependence on ; the remaining open problem is whether this dependence can be improved or perhaps even removed entirely. We show that the -dependence cannot in fact be completely removed. In the specific parameter regime where = kn^-1{2k-2} < 12k, we show a lower bound of (^-1/k n^{1/k}k). An unusual feature of our lower bound is that it is conditional on the girth conjecture with parameter k-1 rather than k. We 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 or improving the dependence to ^-1 are both as hard as settling the girth conjecture for all constant k.