Unconditional Lower Bounds for Degree Fault Tolerant Spanners

We study multiplicative graph spanners in the $f$-degree fault tolerant ($f$-DFT) model, in which the spanner must approximately preserve distances even after any subset of edges of maximum degree $f$ temporarily "fails" and is removed from the graph.

We prove that there are $n$-node lower bound graphs for which any $f$-DFT $(2k-1)$-stretch spanner $H$ must have size $$|E(H)| \ge \Omega\left( f^{1-1/k} n^{1+1/k}\right).$$ This matches a lower bound that was previously only known to hold conditionally, under the 1963 girth conjecture of Erdős.

It also matches the current upper bounds, up to a factor of $\texttt{exp}(k)$.

Our proof is an analysis of the so-called Wenger graphs (J.

Comb.

Theory 1991), via their recent reinterpretation by Szabó and by Conlon (Am.

Math.

Monthly 2021).