{"ID":6138340,"CreatedAt":"2026-07-09T01:07:32.349475501Z","UpdatedAt":"2026-07-11T15:55:22.600961252Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.07576","arxiv_id":"2607.07576","title":"Unconditional Lower Bounds for Degree Fault Tolerant Spanners","abstract":"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 Ω\\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).","short_abstract":"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...","url_abs":"https://arxiv.org/abs/2607.07576","url_pdf":"https://arxiv.org/pdf/2607.07576v1","authors":"[\"Greg Bodwin\",\"Aleksey Lopez\"]","published":"2026-07-08T16:02:15Z","proceeding":"cs.DS","tasks":"[\"cs.DS\",\"math.CO\"]","methods":"[]","has_code":false}