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 \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).

1 Introduction↩︎

1.1 Spanners and the Girth Conjecture↩︎

A multiplicative spanner is a primitive in graph theory and algorithms, which sparsifies an input graph while approximately preserving its shortest path distances. Spanners were abstracted in the late ’80s after being implicitly studied in networking, distributed algorithms, etc (see survey [1]).

Definition 1 (Spanners [2]). Given a graph \(G = (V, E, w)\), a subgraph \(H = (V, E', w)\) is a \(k\)-spanner of \(G\) if for all nodes \(s, t\), we have \(\operatorname{dist}_H(s, t) \le k \cdot \operatorname{dist}_G(s, t)\).

Spanners and their variants are often studied from the extremal perspective, where the goal is to prove that one can always construct a spanner with a good tradeoff between size and error. The following classic theorem of Althöfer, Das, Dobkin, Joseph, and Soares [3] conditionally settles the extremal tradeoff available for multiplicative spanners:

Theorem 1 ([3]). For all positive integers \(n, k\), every \(n\)-node graph has a \((2k-1)\)-spanner on \(O(n^{1+1/k})\) edges. Moreover, assuming the girth conjecture [4], for all positive integers \(k\) there are families of \(n\)-node graphs on which this size bound cannot be improved to \(o(n^{1+1/k})\).

The girth conjecture referenced in this theorem, attributed to Erdős [4], says the following. Let us denote by \(\texttt{ex}(n, C_{\le 2k})\) the maximum possible number of edges in an \(n\)-node graph that does not have any cycles of length \(\le 2k\) as subgraphs. There is a simple folklore counting argument, called the Moore bound, that implies \[\texttt{ex}(n, C_{\le 2k}) \le O\left( n^{1+1/k}\right).\] The girth conjecture posits that this bound is asymptotically best possible for all \(k\). The girth conjecture is an old and very difficult problem in extremal graph theory, likely beyond the reach of current techniques. It has been confirmed only for \(k \in \{1, 2, 3, 5\}\) [5], [6], with no new cases settled since the 1950s. In fact, the community has more recently started to regard it with some skepticism. For example, in an article from 2021, Conlon [7] writes:

“It is now quite commonplace to believe that the true value of certain extremal numbers lie below what the classical arguments give. We suspect that this should already be the case for \(C_8\), that is, that \(\texttt{ex}(n, C_8) = o(n^{5/4})\).”

Here \(\texttt{ex}(n, C_8)\) is the maximum possible number of edges in an \(n\)-node graph with no \(C_8\) subgraph. It follows from the definitions that \(\texttt{ex}(n, C_8) \ge \texttt{ex}(n, C_{\le 8})\), and so the suggested bound of \(o(n^{5/4})\) would imply that the girth conjecture is false already for \(k=4\). Since this seems difficult to prove, Conlon goes on to give a more attainable conjecture, very roughly stating that the techniques from incidence geometry used to confirm the girth conjecture for \(k \in \{1, 2, 3, 5\}\) cannot be extended to other values of \(k\). This conjecture is related to the classical Feit-Higman Theorem [8], which is sometimes interpreted as further evidence against the girth conjecture.² For further technical discussion and references on the girth conjecture and its surrounding literature, we recommend the excellent set of lecture notes by Szabó [9].

1.2 Fault Tolerant Spanners↩︎

Spanners are often used in distributed systems and networking, where there is a possibility of nodes or edges in the input graph \(G\) temporarily failing and becoming unusable while they await repair. A desirable feature in these application domains is for a spanner \(H\) to retain its distance approximation guarantees even after any “reasonable” failure event occurs.

The first formal model of fault tolerant spanners was introduced by Levcopoulos, Narasimhan, and Smid [10]. They defined \(H\) to be an \(f\)-vertex (edge) fault tolerant \(k\)-spanner of \(G\) if, for any set \(F\) of \(|F| \le f\) vertices (edges), the subgraph \(H \setminus F\) is still a \(k\)-spanner of \(G \setminus F\). The initial results in this model were for geometric graphs, which has remained an area of intensive focus for the community [10]–[19]. Results for general graphs were obtained later by Chechik, Langberg, Peleg, and Roditty [20], which has inspired a similarly long line of followup work [21]–[27]. By now, this model of fault tolerance is mostly well understood. We have optimal existential bounds [22], [23] and near-optimal algorithms [27] for the setting of vertex faults. We also have optimal existential bounds for edge faults for infinitely many values of spanner error \(k\) [22], [25], although some knowledge gaps remain. As usual, the lower bounds in both settings are conditioned on the girth conjecture.³

More recently, the community has turned toward new and more expressive models of fault tolerance, that strengthen the original model without harming the spanner size too much. One such model is color-fault tolerant spanners, a compelling model of correlated failure introduced recently by Petruschka, Sapir, and Tzalik [28] (see also [28]–[31]). Optimal or near-optimal bounds are known for this setting as well, again with the lower bounds conditioned on the girth conjecture.⁴ Another more expressive fault tolerance model, which will be a focus of this work, is degree fault tolerant spanners:

Figure 1: An input graph G (left) and a 1-DFT 3-spanner H (right). Note that after any degree-1 fault set is removed from both G and H (such as the pair of edges marked with red X’s), the remaining part of H is still a 3-spanner of the remaining part of G. — Figure 1: An input graph \(G\) (left) and a \(1\)-DFT \(3\)-spanner \(H\) (right). Note that after any degree-1 fault set is removed from both \(G\) and \(H\) (such as the pair of edges marked with red X’s), the remaining part of \(H\) is still a \(3\)-spanner of the remaining part of \(G\).

Definition 2 (Degree Fault Tolerant Spanners [32]). Given a graph \(G = (V, E, w)\), a subgraph \(H = (V, E', w)\) is an \(f\)-degree fault tolerant (\(f\)-DFT) \(k\)-spanner of \(G\) if, for any edge subset \(F \subseteq E\) such that \(F\) contains at most \(f\) edges incident on each node, we have \[\operatorname{dist}_{H \setminus F}(s, t) \le k\cdot \operatorname{dist}_{G \setminus F}(s, t) \qquad \text{for all nodes } s, t.\]

An \(f\)-DFT spanner can tolerate many more edge failures at once than in the original model of fault tolerance; for example, it can handle \(O(nf)\) edge failures, so long as they are spread throughout the graph such that at most \(f\) failing edges are incident to any particular node. Despite this possibility of massive failure, Bodwin, Haeupler, and Parter [32] showed that fairly reasonable existential size bounds are available, not much worse than the ones known for the original model:

Theorem 2 ([32]). For all positive integers \(k\), every \(n\)-node graph \(G\) has an \(f\)-DFT \((2k-1)\)-spanner \(H\) on \[|E(H)| \le O\left( \exp(k) \cdot f^{1-1/k} \cdot n^{1+1/k}\right)\] edges. Moreover, assuming the girth conjecture, there is a family of \(n\)-node input graphs \(G\) for which any \(f\)-DFT \((2k-1)\)-spanner \(H\) must have \[|E(H)| \ge \Omega\left( f^{1-1/k} \cdot n^{1+1/k}\right).\]

Thus conditionally nearly-tight bounds are known for this problem, up to a factor of \(\exp(k)\), and assuming the girth conjecture. Followup work by Parter and Tzalik [33] obtained matching upper and lower bounds in the reachability (\(k=\infty\)) setting, and Biniaz, Carufel, Maheshwari, and Smid [34] obtained results in the DFT model for metric and geometric spanners.

1.3 Our Results↩︎

The contribution of this paper is to show that the additional strength of the DFT model is enough to obtain unconditional lower bounds. We show:

Theorem 3. For all positive integers \(k\), there are \(n\)-node input graphs \(G\) for which any \(f\)-DFT \((2k-1)\)-spanner \(H\) must have \[|E(H)| \ge \Omega\left( f^{1-1/k} \cdot n^{1+1/k}\right).\]

These lower bounds are both optimal up to \(O_k(1)\) factors, and they hold via explicit constructions that do not assume the girth conjecture. This makes DFT spanners essentially the first variants of multiplicative spanners where one can obtain unconditionally near-optimal lower bounds. For essentially every other variant, the best unconditional lower bounds are inherited from the lower bounds for the function \(\texttt{ex}(n, C_{\le 2k})\), where the state-of-the-art is from a 1995 work of Lazebnik, Ustimenko, and Woldar [35]. These bounds are polynomially below the bound posited by the girth conjecture, meaning that our results represent polynomial improvements in the known unconditional bounds.

These theorems may also have independent interest from the standpoint of extremal combinatorics. In some sense, they state that the DFT model captures the gap between known algebraic techniques and the structure that would be needed to prove the girth conjecture, if possible. More specifically, our proofs analyze the Wenger graphs [5], which are an elegant algebraic construction that notably achieves optimal lower bounds on the function \(\texttt{ex}(n, C_{2k})\) for \(k \in \{1, 2, 3, 5\}\).⁵ Szabó [9] and Conlon [7] independently devised a reinterpretation of Wenger’s original construction with a more algebraic flavor. We adopt their interpretation, and make algebraic arguments to reason about the fine-grained structure of the short cycles that appear in these graphs. The main part of our proofs can be viewed as a formalization of the sense in which the Wenger graphs come close to proving the girth conjecture; that is, their short cycles are sparsely “spread out” throughout the graph in a way that lets one destroy the relevant ones with a low-degree fault set.

2 Proof of Main Result↩︎

2.1 Construction of Incidence System and Fault Sets↩︎

We begin by constructing an incidence system, consisting of \(n\) points and \(n\) lines (subsets of the points). This construction and its incidence graph are originally by Wenger [5], while our algebraic exposition follows Szabó [9] and Conlon [7].

(The parameters.) The construction is parametrized by an arbitrary prime \(p\) and an arbitrary integer \(k \ge 1\). We will have \(n:=p^k\) points and lines in the construction. We will use the standard shorthand \([p] := \{0, 1, \dots, p-1\}\).
(The points.) The set of points \(A\) is the elements of the finite field \(\mathbb{F}_p^k\). We interpret \(\mathbb{F}_p^k\) as a vector space with scalars in \(\mathbb{F}_p\), and so we will perform scalar multiplication with scalars from \([p]\).
(The lines.) For any \(t \in [p]\), let \(\sigma_t := (1,t,t^2,\dots,t^{k-1}) \in \mathbb{F}_p^k\); we will refer to \(\sigma_t\) as a slope vector. The set of lines \(L\) is exactly the lines of slope \(\sigma_t\) for any \(t \in [p]\). In other words, a subset of points forms a line \(\ell\) iff there exists \(t \in [p]\) such that \(\ell\) is a maximal subset of points with the property that any two points in \(\ell\) differ by a multiple of \(\sigma_t\). Formally: \[L := \left\{ \big\{x + \lambda \sigma_t \;\mid \;\lambda \in [p] \big\} \mid x \in \mathbb{F}_p^k, t \in [p] \right\}.\]
(The graph.) We define \(\mathcal{B}\) to be the bipartite incidence graph between the set of points \(A\) and the set of lines \(L\). That is: the left side is \(A\), the right side is \(L\), and there is an edge \(\{a,\ell\} \in E(\mathcal{B})\) iff \(a\in \ell\).

Figure 2: (Left) The 25 points and first 3 lines used in the construction with k=2 and p=5. (Right) The corresponding incidence graph. In the full system, there would be 25 lines and therefore 25 nodes on the right side of the incidence graph. — Figure 2: (Left) The \(25\) points and first \(3\) lines used in the construction with \(k=2\) and \(p=5\). (Right) The corresponding incidence graph. In the full system, there would be \(25\) lines and therefore \(25\) nodes on the right side of the incidence graph.

The graph \(\mathcal{B}\) has the following statistics:

Lemma 1 (Size of \(\mathcal{B}\)). The graph \(\mathcal{B}\) has \(2n\) nodes and \(n^{1+1/k}\) edges.

Proof. There are \(n=p^k\) nodes in \(\mathbb{F}_p^k\). The lines are indexed by \(p^k\) possible choices of \(x\) and \(p\) possible choices of \(t\), but each line can be generated in \(p\) ways (by choosing any of its \(p\) points for \(x\)), so there are \(p^k \cdot p / p = p^k = n\) lines. Thus \(\mathcal{B}\) has \(n\) nodes on each side of its bipartition, for \(2n\) nodes in total. Each line contains exactly \(p\) points, so it generates \(p\) edges in \(\mathcal{B}\). So there are \(p^{k+1} = n^{(k+1)/k} = n^{1+1/k}\) edges in \(\mathcal{B}\). ◻

Our goal will be to argue that \(\mathcal{B}\) is the only \(1\)-DFT \((2k-1)\)-spanner of itself. This gives our desired lower bound in the special case \(f=1\). Later, in Section 2.4, we will describe a standard technique used to boost the lower bound to arbitrary \(f \ge 1\). The first step towards this goal is, for every edge \(e\), to define a corresponding edge set \(F_e\) of maximum degree \(1\) (i.e., a matching) such that \(e\) does not participate in any cycles of length \(\le 2k\) in the graph \(\mathcal{B}\setminus F_e\). The next step in our proof is to define these sets \(F_e\). The following definitions will be useful:

Definition 3 (Line and Path Properties). Two lines \(\ell, \ell' \in L\) are parallel, written \(\ell \parallel \ell'\), if they are distinct and they have the same direction vector \(\sigma_t\). A path \(\pi\) in \(\mathcal{B}\) with vertex sequence \[\pi=(a=a_0,\ell_0,a_1,\ell_1,\dots,\ell_{r-1},a_r=b)\] is called \(\ell\)-transverse if it is simple⁶ and none of the lines \(\{\ell_0,\ell_1,\dots,\ell_{r-1}\}\) are equal to \(\ell\) or parallel to \(\ell\). Its line-length is the number of lines in \(L\) corresponding to nodes in the path; for example, the above path \(\pi\) has \(\texttt{line-length}(\pi) = r\).

Definition 4 (Failure Set \(F_e\)). For any edge \(e = \{a, \ell\} \in E(\mathcal{B})\), we define \(F_e\subseteq E(\mathcal{B})\setminus\{e\}\) to be the set of all edges \(\{b,\ell'\}\) such that \(\ell \parallel \ell'\), and there exists an \(\ell\)-transverse path from \(a\) to \(b\) of line-length \(\le \frac{k}{2}-1\).⁷

Figure 3: When considering the edge e corresponding to the point-line incidence a \in \ell, we add to its associated fault set F_e the edges corresponding to point-line incidences b \in \ell', where \ell \parallel \ell' and b can be reached from a by an \ell-transverse path of small line-length. — Figure 3: When considering the edge \(e\) corresponding to the point-line incidence \(a \in \ell\), we add to its associated fault set \(F_e\) the edges corresponding to point-line incidences \(b \in \ell'\), where \(\ell \parallel \ell'\) and \(b\) can be reached from \(a\) by an \(\ell\)-transverse path of small line-length.

2.2 Bound on Degree of \(F_e\)↩︎

Our next goal is to prove that, for each edge \(e \in E(\mathcal{B})\), the associated fault set \(F_e\) has maximum degree \(1\). We will need two supporting structural lemmas before the main proof.

Lemma 2. For any closed, non-backtracking⁸ walk \(W\) in \(\mathcal{B}\) of length \(|W| \le 2k\), there is no \(t \in [p]\) such that \(W\) contains exactly one line of slope \(\sigma_t\). (This allows the case where \(W\) contains two instances of the same line \(\ell\).)

Proof. Let the vertex sequence of \(W\) be \[W=(a_0,\ell_0,a_1,\ell_1,\dots,\ell_{r-1},a_r=a_0),\] where each \(a_j\) is a point and each \(\ell_j\) is a line with slope vector \(\sigma_j\), and \(r \le k\). Since \(a_j,a_{j+1}\in \ell_j\), there exists a scalar \(\lambda_j\in \mathbb{F}_p\) such that \(a_{j+1}=a_j+\lambda_j \sigma_j\). Moreover, since the walk is non-backtracking, we have \(a_j \ne a_{j+1}\) and so these scalars are all nonzero. Summing these equations around the walk \(W\) gives the identity \[\sum_{j=0}^{r-1}\lambda_j \sigma_j = 0.\] However, it follows from the usual analysis of the Vandermonde matrix [7] that any \(k\) slope vectors \(\{\sigma_j\}\) are linearly independent. Thus, this identity is possible only if after grouping equal slope vectors together, their associated coefficients must sum to \(0\). Since each individual coefficient \(\lambda_j\) is nonzero, this implies that each slope vector must have at least two associated coefficients, implying the lemma. ◻

Lemma 3 (Unique endpoints). Let \(\ell,\ell'\) be parallel lines in \(L\) and let \(a\in \ell\). Then there is a point \(b \in \ell'\) such that every \(\ell\)-transverse path of line-length \(\le \frac{k}{2}-1\) that starts at \(a\) and ends at a point in \(\ell'\) specifically ends at \(b\).

Proof. Suppose there are \(\ell\)-transverse paths with node sequences \[\pi_1=(a,\ell_0,a_1,\ell_1,\dots,\ell_{r-1},b) \quad \text{and} \quad \pi_2=(a,m_0,b_1,m_1,\dots,m_{s-1},b')\] ending at points \(b,b'\in \ell'\), of respective line-lengths \(r, s\) both \(\le \frac{k}{2}-1\). Suppose for contradiction that \(b\neq b'\). Concatenating \(\pi_1\) and the reverse of \(\pi_2\) with the node \(\ell'\) placed between them produces a closed walk \(W\) in \(\mathcal{B}\). Consider a minimal nonempty closed subwalk \(W' \subseteq W\) that contains an edge of \(\ell'\), which is a simple cycle (and hence non-backtracking). We have \[\texttt{line-length}(W') \le r+1+s \le 2 \cdot \left(\frac{k}{2} - 1\right) + 1 \le k-1.\] Hence the total length of \(W'\) in \(\mathcal{B}\) is \(|W'| \le 2k\). Moreover, the only line in \(W'\) parallel to \(\ell\) is \(\ell'\), since both \(\pi_1\) and \(\pi_2\) are \(\ell\)-transverse. This contradicts Lemma 2. Thus we have \(b=b'\), completing the proof. ◻

Lemma 4. For any edge \(e\), the edge set \(F_e \cup \{e\}\) has maximum degree \(1\).

Proof. Let \(e =: \{a, \ell\}\). We analyze \(\deg_{F_e}(v)\) in cases:

Suppose that \(v\) corresponds to a point (rather than a line) in the incidence system. Since \(v\) lies on exactly one line \(\ell'\) parallel to \(\ell\) (or \(v\) lies on \(\ell\) itself), the only edge containing \(v\) that might be in \(F_e\) is \((v, \ell')\), so \(\deg_{F_e}(v) \le 1\).
Suppose that \(v\) corresponds to a line in the incidence system that is not parallel to \(\ell\). Then by construction, \(\deg_{F_e}(v) = 0\).
Suppose that \(v\) corresponds to a line in the incidence system that is parallel to \(\ell\). By Lemma 3, there is at most one point \(b \in v\) that is the endpoint of an \(\ell\)-transverse path from \(a\) of line-length \(\le \frac{k}{2}-1\). Hence \(v\) is incident to at most one edge of \(F_e\).
Suppose that \(v = \ell\). By construction, the only edge in \(F_e \cup \{e\}\) incident to \(v\) is \(e\) itself.

◻

2.3 Correctness of Fault Set \(F_e\)↩︎

Our next goal is to prove that each edge \(e\) does not participate in any cycles of length \(\le 2k\) in the graph \(\mathcal{B}\setminus F_e\).

Figure 4: A depiction of the “path-straightening” technique used to prove Lemma 5.

Lemma 5 (Path straightening). Let \(\pi\) be an \(\ell\)-transverse \(a \leadsto b\) path in \(\mathcal{B}\) that uses lines with \(z\) distinct slope vectors. Then there is an \(\ell\)-transverse path \(\pi'\) with the same endpoints \(a \leadsto b\) that has line-length \(\le z\).

Proof. Let \(\pi'\) be an \(a \leadsto b\) path in \(\mathcal{B}\) of minimum length, among the paths with the property that every slope vector used by a line in \(\pi'\) is also used by at least one line in \(\pi\). Note that, since \(\pi\) is \(\ell\)-transverse, this implies that \(\pi'\) is \(\ell\)-transverse as well. Let the vertex sequence of \(\pi'\) be \[\pi'=(a=a_0,\ell_0,a_1,\dots,\ell_{s-1},a_s=b).\] If all lines \(\{\ell_i\}\) used by \(\pi'\) have pairwise distinct slope vectors, then since \(\pi'\) has at most \(z\) distinct slope vectors, we get \(s \le z\). So \(\pi'\) has line-length \(\le z\) and it satisfies the lemma.

So, for the remaining part of the proof, assume towards contradiction that not all lines \(\{\ell_i\}\) have distinct slope vectors. For each index \(i\), let \(\Delta_i := a_{i+1} - a_i\). We may therefore describe the sequence of point-nodes along \(\pi'\) as \[\left(a, a + \Delta_0, a + \Delta_0 + \Delta_1, \dots, a + \sum \limits_{i=0}^{s-1} \Delta_i = b\right).\] Next, let \(\phi\) be an arbitrary permutation on \([s]\). We define \(\pi_{\phi}\) as the walk in \(\mathcal{B}\) whose sequence of point-nodes is \[\left(a, a + \Delta_{\phi(0)}, a + \Delta_{\phi(0)} + \Delta_{\phi(1)}, \dots, a + \sum \limits_{i=0}^{s-1} \Delta_{\phi(i)} = b\right).\] Note that adjacent point-nodes in this sequence differ by some vector \(\Delta_i\), which is the slope of the line \(\ell_i\), and so by construction there is indeed a line that contains these adjacent points. This confirms that there is a unique walk \(\pi_{\phi}\) with this sequence of point-nodes, so \(\pi_{\phi}\) is well defined.

We assumed that a slope vector is used in \(\pi'\) at least twice, so by choice of \(\phi\), we may have \[\Delta_{\phi(0)} = \lambda \cdot \Delta_{\phi(1)}\] for some scalar \(\lambda \in [p]\). Thus, we may delete the second point-node along \(\pi_{\phi}\), giving a shorter sequence \[\left(a, a + \Delta_{\phi(0)} + \Delta_{\phi(1)}, \dots, a + \sum \limits_{i=0}^{s-1} \Delta_{\phi(i)} = b\right).\] The difference between the first two point nodes is \((\lambda + 1) \cdot \Delta_{\phi(1)}\), so these points are still connected by a line of a viable slope vector. If \(\lambda = -1\) then we simply omit that step, which still results in a shorter walk. Thus there is a corresponding \(a \leadsto b\) walk of length shorter than \(\pi'\). Deleting closed subwalks yields a path that contradicts minimality of the length of \(\pi'\), completing the proof. ◻

Figure 5: Geometric view of the cycle-hitting argument. The solid orange path is the chosen \ell-transverse arc of the cycle, and the dashed orange path is the straightened path with the same endpoints. — Figure 5: Geometric view of the cycle-hitting argument. The solid orange path is the chosen \(\ell\)-transverse arc of the cycle, and the dashed orange path is the straightened path with the same endpoints.

Lemma 6. Every cycle \(C\) in \(\mathcal{B}\) of length at most \(2k\) that contains an edge \(e=\{a,\ell\}\) also contains an edge of \(F_e\).

Proof. Let the vertex sequence of \(C\) be \[C=(a,\ell,a_1,\ell_1,a_2,\ell_2,\dots,a_{r-1},\ell_{r-1},a_r=a)\] with \(r \le k\). By Lemma 2, at least one of the other lines in \(C\) is parallel to \(\ell\). Let \(\ell_i\) be such a line, with the index \(i\) selected as large as possible. Our goal will now be to argue that \(\{a_{i+1},\ell_i\}\in F_e\).

There are \(r\) distinct lines in \(C\). By Lemma 2, each slope vector that is used by any of these \(r\) lines is used by at least two of them, so there are at most \(\frac{r}{2}\) distinct slope vectors used by lines in \(C\). Now consider the subpath \(\pi \subseteq C\) with vertex sequence \[\pi=(a_r,\ell_{r-1},a_{r-1},\dots,\ell_{i+1},a_{i+1}).\] By maximal choice of \(i\), this is an \(\ell\)-transverse path, and hence does not contain any lines whose slope vector matches \(\ell\). So there are at most \(\frac{r}{2}-1\) distinct slope vectors used by the lines in \(\pi\). Thus, by Lemma 5, there is an \(\ell\)-transverse path \(\pi'\) with the same endpoints \((a_r, a_{i+1})\) that has line-length at most \(\frac{r}{2}-1 \le \frac{k}{2}-1\). Thus, by construction, the set \(F_e\) associated to \(e=\{a=a_r, \ell\}\) will include the edge \((a_{i+1}, \ell_i) \in C\). ◻

2.4 Proof Wrapup↩︎

The following theorem certifies our lower bound for the special case \(f=1\):

Theorem 4. The only \(1\)-DFT \((2k-1)\)-spanner of \(\mathcal{B}\) is \(\mathcal{B}\) itself.

Proof. Let \(H\) be a proper subgraph of \(\mathcal{B}\), and we will show that \(H\) is not a \(1\)-DFT \((2k-1)\)-spanner of \(\mathcal{B}\). Consider an edge \[e=\{u,v\}\in E(\mathcal{B})\setminus E(H).\]

Let \(F_e\) denote the set associated to this edge (as in Definition 4). By Lemma 4, the set \(F_e\) has maximum degree \(1\). Next, let \(\pi\) be a shortest \(u \leadsto v\) path in the graph \(H \setminus F_e\). Since \(e \notin E(H)\), we have \(e \notin \pi\), and so \(\pi \cup \{e\}\) is a cycle in \(\mathcal{B}\). This cycle contains \(e\) but it does not contain any edge of \(F_e\). By Lemma 6, this means \(\pi \cup \{e\}\) contains \(>2k\) edges. Thus \(\pi\) contains \(>2k-1\) edges, so we have \[|E(\pi)| = \operatorname{dist}_{H\setminus F_e}(u,v) > 2k-1.\] On the other hand, \(e\notin F_e\), so we have \(\operatorname{dist}_{\mathcal{B}\setminus F_e}(u,v)=1.\) This implies that \(H\) is not a \(1\)-DFT \((2k-1)\)-spanner of \(\mathcal{B}\). ◻

We now upgrade the previous lower bound to an arbitrary degree parameter \(f\) using a standard cloud-blowup technique, which has appeared in many previous papers on fault tolerance [22], [28], [32].

Figure 6: A lifted edge in the cloud blowup. Each base vertex is replaced by a cloud of f copies, and each base edge e=\{u,v\} is replaced by the complete bipartite graph \mathcal{L}(e) between C(u) and C(v). — Figure 6: A lifted edge in the cloud blowup. Each base vertex is replaced by a cloud of \(f\) copies, and each base edge \(e=\{u,v\}\) is replaced by the complete bipartite graph \(\mathcal{L}(e)\) between \(C(u)\) and \(C(v)\).

Definition 5 (Cloud blowup). For an integer \(f \ge 1\), the \(f\)-cloud blowup of the base graph is \[\mathcal{B}^{\langle f \rangle} := \mathcal{B}\times [f],\] where \([f]\) denotes the edgeless graph on \(f\) vertices, and \(\times\) denotes the \(f\)-cloud blowup operation defined below. In other words, it is the graph obtained from \(\mathcal{B}\) by the following steps:

For each vertex \(x\in V(\mathcal{B})\), create a “cloud” of \(f\) nodes, \(C(x):=\{(x,i): i\in [f]\}\).
For each base edge \(\{x,y\}\in E(\mathcal{B})\), lift it to a complete bipartite graph between the clouds \(C(x)\) and \(C(y)\). That is, \[\mathcal{L}(\{x,y\}):=\left\{\{(x,i),(y,j)\} \mid i,j\in [f]\right\} \quad \text{and} \quad E\big(\mathcal{B}^{\langle f\rangle}\big) := \bigcup \limits_{\{x,y\} \in E(\mathcal{B})} \mathcal{L}(\{x,y\}).\]

The following lemma computes how the cloud blowup affects the parameters of the graph:

Lemma 7 (Size of Blown-Up Graph). Letting \(2n\) be the number of vertices in \(\mathcal{B}\), the corresponding blown-up graph \(\mathcal{B}^{\langle f \rangle}\) has \(N := 2nf\) vertices and \(\Theta(f^{1-1/k}N^{1+1/k})\) edges.

Proof. Each node in \(\mathcal{B}\) corresponds to \(f\) copies in \(\mathcal{B}^{\langle f \rangle}\), and each edge in \(\mathcal{B}\) corresponds to \(f^2\) edges in \(\mathcal{B}^{\langle f \rangle}\). Thus we have \[\begin{align} \left|E\left(\mathcal{B}^{\langle f \rangle}\right)\right| &= f^2 \cdot \left|E\left(\mathcal{B}\right)\right|\\ &= \Theta\left( f^2 n^{1+1/k} \right) \tag*{Lemma \ref{lem:bksize}}\\ &= \Theta\left( f^{1-1/k} (nf)^{1+1/k}\right)\\ &= \Theta\left( f^{1-1/k} N^{1+1/k}\right). \tag*{\qedhere} \end{align}\] ◻

From the previous lemma, it suffices to prove that \(\mathcal{B}^{\langle f \rangle}\) is the only \(f\)-DFT \((2k-1)\)-spanner of itself. To do so, let us first define lifted fault sets:

Definition 6 (Lifted Fault Sets \(\widehat{F}_e\)). For an edge \(e \in E(\mathcal{B})\) and an edge \(\widehat{e} \in \mathcal{L}(e)\), we define \(\widehat{F}_{\widehat{e}}\) to be the set of all lifted edges from \(F_e \cup \{e\}\), except for \(\widehat{e}\) itself. That is: \[\widehat F_{\widehat e} := \left(\bigcup_{g \in F_e} \mathcal{L}(g)\right) \cup \big(\mathcal{L}(e) \setminus \{\widehat e\}\big).\]

The next lemma shows that the lifted fault sets have degree \(\le f\):

Lemma 8 (Lifted fault set has maximum degree \(f\)). For any edge \(\widehat{e}\), the corresponding edge set \(\widehat F_{\widehat e}\) has maximum degree \(\le f\) in \(\mathcal{B}^{\langle f\rangle}\).

Proof. Since \(F_e \cup \{e\}\) has maximum degree \(1\) in the base graph, each base vertex \(x\in V(\mathcal{B})\) is incident to at most one edge of \(F_e \cup \{e\}\). Hence each lifted vertex in \(\mathcal{B}^{\langle f \rangle}\) is incident to at most one lifted biclique, and within that biclique it is incident to at most \(f\) edges. ◻

We are finally ready to wrap up the proof:

Theorem 5 (Cloud-blowup lower bound). For any positive integer \(f\), the only \(f\)-DFT \((2k-1)\)-spanner of \(\mathcal{B}^{\langle f \rangle}\) is \(\mathcal{B}^{\langle f \rangle}\) itself.

Proof. Since the following cloud-lift is standard in the previous literature, we will sketch parts of the proof. Let \(H\) be a proper subgraph of \(\mathcal{B}^{\langle f \rangle}\). Choose a missing lifted edge \[\widehat e=\{(u,i),(v,j)\} \in E\left(\mathcal{B}^{\langle f \rangle}\right) \setminus E(H),\] and let \(e=\{u,v\}\in E(\mathcal{B})\) be the corresponding base edge; that is, \(\widehat{e} \in \mathcal{L}(e)\). Consider the associated fault set \(\widehat F_{\widehat e}\). By the previous lemma, \(\widehat F_{\widehat e}\) has maximum degree at most \(f\). Next, let \(\pi\) be a shortest \((u, i) \leadsto (v, j)\) path in the graph \(H \setminus \widehat{F}_{\widehat{e}}\). Projecting \(\pi \cup \{\widehat e\}\) to the base graph yields a closed walk in \(\mathcal{B}\) containing \(e\) and avoiding \(F_e\). Choose a closed subwalk of minimum positive length that contains \(e\); this is a cycle, still contains \(e\), and still avoids \(F_e\). By Lemma 6, this cycle has length greater than \(2k\). Hence \(\pi\) has length greater than \(2k-1\), and so \[|E(\pi)| = \operatorname{dist}_{H \setminus \widehat{F}_{\widehat{e}}}((u,i),(v,j)) > 2k-1.\] On the other hand, \(\widehat{e} \notin \widehat{F}_{\widehat{e}}\), so we have \(\operatorname{dist}_{\mathcal{B}^{\langle f \rangle} \setminus \widehat{F}_{\widehat{e}}}((u,i),(v,j)) = 1.\) This implies that \(H\) is not an \(f\)-DFT \((2k-1)\)-spanner of \(\mathcal{B}^{\langle f \rangle}\). ◻

References↩︎

[1]

R. Ahmed et al., “Graph spanners: A tutorial review,” Computer Science Review, vol. 37, p. 100253, 2020.

[2]

D. Peleg and A. A. Schäffer, “Graph spanners,” Journal of Graph Theory, vol. 13, no. 1, pp. 99–116, 1989.

[3]

I. Althöfer, G. Das, D. Dobkin, D. Joseph, and J. Soares, “On sparse spanners of weighted graphs,” Discrete & Computational Geometry, vol. 9, no. 1, pp. 81–100, 1993.

[4]

P. Erdős, “Extremal problems in graph theory,” in Proceedings of the symposium on theory of graphs and its applications, 1963, pp. 29–36.

[5]

R. Wenger, “Extremal Graphs with no C4’s, C6’s, or C10’s,” Journal of Combinatorial Theory, Series B, vol. 52, no. 1, pp. 113–116, 1991.

[6]

J. Tits, “Sur la trialité et certains groupes qui s’ en déduisent,” Publications Mathématiques de l’IHÉS, vol. 2, pp. 13–60, 1959.

[7]

D. Conlon, “Extremal numbers of cycles revisited,” The American Mathematical Monthly, vol. 128, no. 5, pp. 464–466, 2021.

[8]

W. Feit and G. Higman, “The nonexistence of certain generalized polygons,” Journal of Algebra, vol. 1, no. 2, pp. 114–131, 1964.

[9]

T. Szabó, Lecture notes, FU Berlin“Even cycles.” 2018, [Online]. Available: http://discretemath.imp.fu-berlin.de/DMIII-2018/notes-evencycles.pdf.

[10]

C. Levcopoulos, G. Narasimhan, and M. Smid, “Efficient algorithms for constructing fault-tolerant geometric spanners,” in Proceedings of the thirtieth annual ACM symposium on theory of computing, 1998, pp. 186–195.

[11]

T. Lukovszki, “New results on fault tolerant geometric spanners,” in Workshop on algorithms and data structures, 1999, pp. 193–204.

[12]

A. Czumaj and H. Zhao, “Fault-tolerant geometric spanners,” Discrete & Computational Geometry, vol. 32, no. 2, pp. 207–230, 2004.

[13]

G. Narasimhan and M. Smid, Geometric spanner networks. Cambridge University Press, 2007.

[14]

K. Buchin, S. Har-Peled, and D. Oláh, “A spanner for the day after,” Discrete & Computational Geometry, vol. 64, no. 4, pp. 1167–1191, 2020.

[15]

S. Solomon, “From hierarchical partitions to hierarchical covers: Optimal fault-tolerant spanners for doubling metrics,” in Proceedings of the forty-sixth annual ACM symposium on theory of computing, 2014, pp. 363–372.

[16]

P. Bose, V. Dujmovic, P. Morin, and M. Smid, “Robust geometric spanners,” SIAM Journal on Computing, vol. 42, no. 4, pp. 1720–1736, 2013.

[17]

T.-H. H. Chan, M. Li, and L. Ning, “Sparse fault-tolerant spanners for doubling metrics with bounded hop-diameter or degree,” Algorithmica, vol. 71, no. 1, pp. 53–65, 2015.

[18]

T.-H. H. Chan, M. Li, L. Ning, and S. Solomon, “New doubling spanners: Better and simpler,” SIAM Journal on Computing, vol. 44, no. 1, pp. 37–53, 2015.

[19]

H. Le, S. Solomon, and C. Than, “Optimal fault-tolerant spanners in euclidean and doubling metrics: Breaking the \(\Omega\) (log n) lightness barrier,” in 64th IEEE annual symposium on foundations of computer science, FOCS 2023, santa cruz, CA, USA, november 6-9, 2023, 2023, pp. 77–97, doi: 10.1109/FOCS57990.2023.00013.

[20]

S. Chechik, M. Langberg, D. Peleg, and L. Roditty, “Fault tolerant spanners for general graphs,” SIAM Journal on Computing, vol. 39, no. 7, pp. 3403–3423, 2010.

[21]

M. Dinitz and R. Krauthgamer, “Fault-tolerant spanners: Better and simpler,” in Proceedings of the 30th annual ACM SIGACT-SIGOPS symposium on principles of distributed computing, 2011, pp. 169–178.

[22]

G. Bodwin, M. Dinitz, M. Parter, and V. V. Williams, “Optimal vertex fault tolerant spanners (for fixed stretch),” in Proceedings of the 29th annual ACM-SIAM symposium on discrete algorithms (SODA), 2018, pp. 1884–1900.

[23]

G. Bodwin and S. Patel, “A trivial yet optimal solution to vertex fault tolerant spanners,” in Proceedings of the 2019 ACM symposium on principles of distributed computing, 2019, pp. 541–543.

[24]

M. Dinitz and C. Robelle, “Efficient and simple algorithms for fault-tolerant spanners,” in Proceedings of the 39th symposium on principles of distributed computing, 2020, pp. 493–500.

[25]

G. Bodwin, M. Dinitz, and C. Robelle, “Optimal vertex fault-tolerant spanners in polynomial time,” in Proceedings of the 2021 ACM-SIAM symposium on discrete algorithms (SODA), 2021, pp. 2924–2938.

[26]

G. Bodwin, M. Dinitz, and C. Robelle, “Partially optimal edge fault-tolerant spanners,” in Proceedings of the 2022 annual ACM-SIAM symposium on discrete algorithms (SODA), 2022, pp. 3272–3286.

[27]

M. Parter, “Nearly optimal vertex fault-tolerant spanners in optimal time: Sequential, distributed and parallel,” in Proceedings of the 54th annual ACM SIGACT symposium on theory of computing (STOC), 2022.

[28]

A. Petruschka, S. Sapir, and E. Tzalik, “Color fault-tolerant spanners,” ACM Transactions on Algorithms, vol. 22, no. 1, pp. 1–21, 2025.

[29]

M. Parter, A. Petruschka, S. Sapir, and E. Tzalik, “Parks and recreation: Color fault-tolerant spanners made local,” in Proceedings of the 2025 annual ACM-SIAM symposium on discrete algorithms (SODA), 2025, pp. 4061–4094.

[30]

A. Petruschka, S. Sapir, and E. Tzalik, “Connectivity Labeling in Faulty Colored Graphs,” in 38th international symposium on distributed computing (DISC 2024), 2024, pp. 36:1–36:22.

[31]

M. Parter and A. Petruschka, “Preserving distances in faulty colored graphs,” arXiv preprint arXiv:2504.17868, 2025.

[32]

G. Bodwin, B. Haeupler, and M. Parter, “Fault-tolerant spanners against bounded-degree edge failures: Linearly more faults, almost for free,” in Proceedings of the 2024 annual ACM-SIAM symposium on discrete algorithms (SODA), 2024, pp. 2609–2642.

[33]

M. Parter and E. Tzalik, “Connectivity certificate against bounded-degree faults: Simpler, better and supporting vertex faults,” in 2025 symposium on simplicity in algorithms (SOSA), 2025, pp. 369–377.

[34]

A. Biniaz, J.-L. De Carufel, A. Maheshwari, and M. Smid, “Metric and geometric spanners that are resilient to degree-bounded edge faults,” arXiv preprint arXiv:2405.18134, 2024.

[35]

F. Lazebnik, V. A. Ustimenko, and A. J. Woldar, “A new series of dense graphs of high girth,” Bulletin of the American Mathematical Society, vol. 32, no. 1, pp. 73–79, 1995.

Author order has been alphabetized by surname in accordance with conference convention, but Aleksey Lopez is the primary and corresponding author for this paper.↩︎
The constructions implying the girth conjecture for \(k \in \{1, 2, 3, 5\}\) arise from highly symmetric incidence structures known as finite generalized polygons. The Feit-Higman Theorem constrains the existence of finite generalized polygons, and in particular, it implies that finite generalized polygons cannot be used to prove the girth conjecture for any further values of \(k\).↩︎
In the setting of vertex faults (but not edge faults), we remark that the upper bounds and lower bounds both work by reduction to \(\texttt{ex}(n, C_{\le 2k})\), and hence proving an unconditional tight lower bound would be equivalent to proving the girth conjecture itself [22], [23]. In the setting of edge faults, for higher fault tolerance parameters \(f\), the lower bounds can also be proved by conditioning on a certain bipartite extension of the girth conjecture; see [26], Section 2.1 for discussion.↩︎
Again, the upper and lower bounds in the color-fault model work by reduction to \(\texttt{ex}(n, C_{\le 2k})\), and so proving an unconditional lower bound is equivalent to proving the girth conjecture [28].↩︎
The Wenger graphs also imply the girth conjecture for \(k \in \{1, 2, 3\}\), but not for \(k=5\): although they do not have \(C_{10}\) subgraphs, they do have \(C_8\) subgraphs.↩︎
Recall: a simple path is one that does not repeat nodes.↩︎
The expression \(\frac{k}{2}-1\) is not necessarily integral, but line-length is necessarily integral, so this is equivalent to an upper bound on line-length of \(\le \lfloor \frac{k}{2}-1\rfloor\). Since the floor symbols are not technically necessary, we will omit them here and for other possibly-non-integral expressions encountered as upper bounds in the rest of this paper.↩︎
Recall: a walk is closed if it starts and ends at the same node, and it is non-backtracking if it never uses the same edge twice in a row with opposite orientations.↩︎

Unconditional Lower Bounds for Degree Fault Tolerant Spanners