{"id":"arxiv/2607.07576","url":"https://arxiv.org/abs/2607.07576","tags":["cs.DS","math.CO"],"score":0,"title":"Unconditional Lower Bounds for Degree Fault Tolerant Spanners","domain":"cs.DS","source":"arxiv","authors":["Greg Bodwin","Aleksey Lopez"],"reviews":0,"subject":"cs.DS","summary":"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…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-08","reactions":{}}