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 $$\mathrm{\mid }E(H)\mathrm{\mid }\ge \mathrm{\Omega }\left(f^{1-1\mathrm{/}k}{n}^{1+1\mathrm{/}k}\right)\mathrm{.}$$ 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 $\mathtt{\text{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).