betaFeedback

WorksMathematics

Upper bounds on all-terminal reliability polynomials in terms of cycle basis lengths

Abstract

Let G=(V(G),E(G))G=(V(G),E(G)) be a connected multigraph with nn vertices and mm edges. The all-terminal reliability polynomial of GG can be written as RG(q)=(1−q)n−1∑i=0dHiqiR_G(q)=(1-q)^{n-1}\sum\limits_{i=0}^{d}H_iq^i where d=m−n+1d=m-n+1 is the cycle rank, each edge fails independently with probability q∈[0,1]q\in[0,1], and H0,…,HdH_0,\ldots,H_d are the associated coefficients. A cycle basis, which consists of cycles that form a basis of the cycle space of a graph, is an important tool for characterizing its cycle structure. The structural properties of cycle bases, together with the associated length optimization problems and construction algorithms, have been extensively studied. In this context, Colbourn posed the following open problem, which concerns upper bounds on the reliability coefficients in terms of cycle-basis lengths: For all-terminal reliability, is it true that if GG has a cycle basis containing cycles of lengths c1,…,cm−n+1c_1,\ldots,\allowbreak c_{m-n+1}, then Hi≤∑I⊆{1,…,m−n+1},∣I∣=i∏j∈I(cj−1)H_i \le\sum\limits_{\substack{I\subseteq\{1,\ldots,m-n+1\},|I|=i}}\prod\limits_{j\in I}(c_j-1)? In this paper, we establish a result that resolves this open problem.

Introduction

Let G=(V(G),E(G))G=(V(G),E(G)) be a connected multigraph with nn vertices and mm edges. Its all-terminal reliability polynomial RG(q)R_G(q) gives the probability that the spanning subgraph consisting of the operational edges is connected. We assume that all vertices remain operational and that

E-mail addresses: [email protected], [email protected], [email protected], [email protected] each edge fails independently with probability qq. A cycle is a nonempty closed walk in which no edge is repeated and no vertex is repeated except that the initial and terminal vertices coincide. In particular, a single loop is permitted as a cycle of length 1, and two parallel edges are permitted as a cycle of length 2. When computing vertex degrees, each loop is counted twice. For an edge set S⊆E(G)S \subseteq E(G), let G−SG-S denote the spanning subgraph obtained by deleting the edges in SS while retaining all vertices. An edge set SS is called a deletable edge set if G−SG-S is connected. An edge ee is called a bridge if G−{e}G-\{e\} is disconnected, and the number of bridges is denoted by bb. For a nonnegative integer hh, let [h]={1,…,h}[h]=\{1,\ldots,h\}, with [0]=∅[0]=\varnothing. For a finite set SS, the notation ∣S∣|S| denotes its cardinality.

The all-terminal reliability polynomial of the graph is defined by

RG(q)=(1−q)n−1∑i=0dHiqi(1)R_G(q)=(1-q)^{n-1}\sum_{i=0}^{d}H_iq^i \tag*{(1)}

where the coefficients HiH_i are uniquely determined by (1). The sequence (H0,…,Hd)(H_0,\ldots,H_d) is called the HH-sequence of the all-terminal reliability polynomial, with the convention that Hi=0H_i=0 for i>di>d. Let G0G_0 denote the graph obtained from GG by deleting all loops, and let LL be the set of loops of GG, with ℓ=∣L∣\ell=|L|. Since deleting loops does not affect connectivity, G0G_0 remains connected and RG(q)=RG0(q)R_G(q)=R_{G_0}(q). It follows from (1) and the uniqueness of the coefficients that the HH-sequence of GG is obtained by appending ℓ\ell zeros to the HH-sequence of G0G_0. In particular, Hi=0H_i=0 whenever d−ℓ<i≤dd-\ell<i\leq d.

Research on upper and lower bounds for the all-terminal reliability polynomial has drawn on shellability, network transformations, coefficient inequalities, and extremal graphs. Ball and Provan [11] exploited the shellable structure of the family of deletable edge sets to derive upper and lower bounds on the all-terminal reliability function, incorporating information on the number of spanning trees and the size and number of minimum cuts. Colbourn and Harms [1] employed linear programming to improve the reliability estimates provided by the Ball–Provan and Lomonosov–Polesskii bounds. Brown et al. [6] investigated the effects of network transformations on the HH-coefficients of the all-terminal reliability polynomial and established efficiently computable coefficientwise upper and lower bounds, which they incorporated as additional constraints to strengthen the Ball–Provan method. For HH-sequences arising from graphs, Brown and Colbourn [7] established several non-Stanley-type inequalities, which provide new coefficient constraints for reliability estimation. Brown et al. [8] exploited the connection between chip-firing processes on graphs and reliability HH-sequences, together with structural information about the corresponding monomial representations, to improve the all-terminal reliability bounds obtained by the Ball–Provan method. For sparse graphs, Romero [14] considered connected simple graphs with prescribed numbers of vertices and edges whose cycle rank is at most 4. Using uniformly least reliable graphs and previously known uniformly most reliable graphs, Romero obtained optimal universal upper and lower bounds on reliability for this class of graphs. Building on earlier results, Colbourn [2] investigated the coefficients of the all-terminal reliability polynomial and posed the following open problem.

Problem 1.1. [2] For all-terminal reliability, is it true that if GG has a cycle basis containing cycles of lengths c1,…,cm−n+1c_1,\ldots,c_{m-n+1}, then

Hi≤∑I⊆{1,…,m−n+1}∣I∣=i∏j∈I(cj−1)?H_i \le\sum_{\substack{I\subseteq\{1,\ldots,m-n+1\}\\ |I|=i}}\prod_{j\in I}(c_j-1)?

Define a cactus graph to be a connected graph in which each edge belongs to at most one cycle, and let Z2\mathbb{Z}_2 denote the field with two elements. We investigate this problem and obtain the following theorem:

Theorem 1.2. Let B={C1,…,Cd}\mathcal{B}=\{C_1,\ldots,C_d\} be an arbitrary cycle basis of GG over Z2\mathbb{Z}_2, and let cj=∣E(Cj)∣≥1c_j=|E(C_j)|\ge1 denote the length of CjC_j. Then, for every 0≤i≤d0\le i\le d, the coefficients in (1) satisfy

0≤Hi≤∑I⊆[d]∣I∣=i∏j∈I(cj−1).(2)0\le H_i\le\sum_{\substack{I\subseteq[d]\\ |I|=i}}\prod_{j\in I}(c_j-1). \tag*{(2)}

Where, equality holds in the second inequality simultaneously for all ii if and only if GG is a cactus graph.

Remark. For i>d−ℓi>d-\ell, equality holds in the first inequality if and only if the connected multigraph obtained from GG by deleting all loops has cycle rank at most i−1i-1. For 0≤i≤d−ℓ0\le i\le d-\ell, we have Hi>0H_i>0. In particular, if GG is loopless, then the first inequality is strict throughout the stated range.

Brown and Colbourn [7], in their study of upper and lower bounds on network reliability, used an expansion of the all-terminal reliability polynomial according to the size of the failed edge set, namely the FF-form. Huh [9] also used this representation in studying the log-concavity of matroid hh-vectors and its applications to network reliability. Thus, (1) can be rewritten as follows:

RG(q)=∑i=0dFiqi(1−q)m−i.(3)R_G(q)=\sum_{i=0}^{d}F_iq^i(1-q)^{m-i}. \tag*{(3)}

Here, FiF_i is the number of deletable edge sets containing ii edges, and Fi=0F_i=0 for i>di>d. For example, F0=1F_0=1, F1F_1 is the number of non-bridge edges in GG, and FdF_d is the number of spanning trees of GG. A spanning tree is a connected acyclic subgraph that contains all vertices and has one fewer edge than vertices; let τ(G)\tau(G) denote the number of spanning trees of GG. From (1) and (3), we obtain

H0=1,H1=n−1−b,∑i=0dHi=Fd=τ(G).(4)H_0=1,\qquad H_1=n-1-b,\qquad\sum_{i=0}^{d}H_i=F_d=\tau(G). \tag*{(4)}

The above discussion and Theorem 1.2 yield the following result.

Corollary 1.1. Under the assumptions of Theorem 1.2, for every 0≤i≤d0\le i\le d, we have

Fi≤∑I⊆[d]∣I∣=i∏j∈Icj.F_i\le\sum_{\substack{I\subseteq[d]\\ |I|=i}}\prod_{j\in I}c_j.

Equality always holds when i=0i = 0; for each 1≤i≤d1 \le i \le d, equality holds if and only if GG is a cactus graph.

In particular, setting i=di = d in (4) yields

τ(G)=Fd≤∏j=1dcj(5)\tau(G) = F_d \le\prod_{j=1}^{d} c_j \tag*{(5)}

with equality if and only if GG is a cactus graph.

Remark. Bortoletto et al. [3] previously established (5) in their study of the geometric structure of periodic timetables.

The paper is organized as follows. Section 2 introduces cycle spaces, independent sets of matroids, and the associated quotient algebras, and presents the lemmas that are needed for the subsequent proofs. In Section 3, we establish upper bounds on the coefficients of the all-terminal reliability polynomial in terms of the lengths of the cycles in an arbitrary binary cycle basis, from which we further derive upper bounds on the numbers of deletable edge sets and spanning trees. Section 4 summarizes the main results and poses further related questions.

Preliminaries

In this section, we retain the notation introduced in Section 1 and present the definitions and lemmas that are needed to prove the main theorem.

Let span⁡Z2\operatorname{span}_{\mathbb{Z}_2} and dim⁡Z2\dim_{\mathbb{Z}_2} denote linear span and vector space dimension over the field Z2\mathbb{Z}_2, respectively. Let Z2E(G)\mathbb{Z}_2^{E(G)} denote the vector space over Z2\mathbb{Z}_2 whose coordinates are indexed by the edge set E(G)E(G). For any S⊆E(G)S \subseteq E(G), let χS∈Z2E(G)\chi_S \in\mathbb{Z}_2^{E(G)} denote the characteristic vector of SS, whose coordinate at an edge e∈E(G)e \in E(G) is given by

(χS)e={1,e∈S,0,e∉S.(\chi_S)_e = \begin{cases} 1, & e \in S,\\ 0, & e \notin S. \end{cases}

Fix a spanning tree TT of GG. For each non-tree edge e∈E(G)∖E(T)e \in E(G) \setminus E(T), let CTeC_T^e denote the fundamental cycle associated with ee with respect to TT. If ee is not a loop, then CTeC_T^e consists of ee together with the unique path in TT joining its endpoints; if ee is a loop, then CTeC_T^e is the cycle of length 1 consisting solely of ee.

We next introduce the binary cycle space and its basic properties, and describe a matching between the cycles in a cycle basis and the non-tree edges of a spanning tree.

Definition 2.1. [16] The binary cycle space of GG is defined by

CZ2(G)=span⁡Z2{χC:C is a cycle of G},\mathcal{C}_{\mathbb{Z}_2}(G) = \operatorname{span}_{\mathbb{Z}_2}\{\chi_C : C\text{ is a cycle of }G\},

where χC\chi_C denotes the characteristic vector of the edge set of CC.

A family of cycles B={C1,…,Cd}\mathcal{B} = \{C_1, \ldots, C_d\} is called a binary cycle basis of GG if the corresponding vectors {χC1,…,χCd}\{\chi_{C_1}, \ldots, \chi_{C_d}\} form a basis of CZ2(G)\mathcal{C}_{\mathbb{Z}_2}(G).

Since the only cycle that contains a given loop is the cycle consisting of that loop alone, every binary cycle basis must contain the cycle of length 1 formed by each loop. Removing these cycles leaves a binary cycle basis of the loopless graph G0G_0.

Lemma 2.1. [16] The dimension of the binary cycle space of a connected graph GG equals its cycle rank, that is,

dim⁡Z2CZ2(G)=d=m−n+1.\dim_{\mathbb{Z}_2} \mathcal{C}_{\mathbb{Z}_2}(G) = d = m-n+1.

Moreover, for any spanning tree TT of GG, the characteristic vectors of the fundamental cycles with respect to TT form a basis of the binary cycle space.

Lemma 2.2. [12] Let S={e1,…,ed}⊆E(G)S=\{e_1,\ldots,e_d\}\subseteq E(G) be such that G−SG-S is a spanning tree and let B={C1,…,Cd}\mathcal{B}=\{C_1,\ldots,C_d\} be a binary cycle basis of GG. Then a bijection

f:S⟶B,e∈E(f(e))(e∈S).f:S\longrightarrow\mathcal{B},\qquad e\in E(f(e))\quad(e\in S).

To establish the connection between the deletable edge sets of a graph and its cographic matroid, we introduce the basic notions of matroids, including independent sets, bases, and rank.

Definition 2.2. [10] A matroid MM is an ordered pair (E,I)(E,\mathcal{I}) consisting of a finite set EE and a collection I\mathcal{I} of subsets of EE having the following three properties:

(i) ∅∈I\varnothing\in\mathcal{I};

(ii) If I∈II\in\mathcal{I} and I′⊆II'\subseteq I, then I′∈II'\in\mathcal{I};

(iii) If I1I_1 and I2I_2 are in I\mathcal{I} and ∣I1∣<∣I2∣\lvert I_1\rvert<\lvert I_2\rvert, then there is an element ee of I2−I1I_2-I_1 such that I1∪{e}∈II_1\cup\{e\}\in\mathcal{I}.

We shall call (i) and (ii) the hereditary and independence augmentation properties. The members of I\mathcal{I} are the independent sets of MM, and EE is the ground set of MM. We shall often write I(M)\mathcal{I}(M) for I\mathcal{I} and E(M)E(M) for EE, particularly. A subset of EE that is not in EE is called dependent.

We call a maximal independent set in MM a basis or a base of MM.

Lemma 2.3. [10] If B1B_1 and B2B_2 are bases of a matroid MM, then ∣B1∣=∣B2∣\lvert B_1\rvert=\lvert B_2\rvert.

All bases of a matroid MM have the same size; this common size is called the rank of MM and is denoted by r(M)r(M).

Let WW be a finite set, and let Γ\Gamma be a nonempty family of subsets of WW. We call Γ\Gamma a simplicial complex on WW if F′∈ΓF'\in\Gamma whenever F∈ΓF\in\Gamma and F′⊆FF'\subseteq F. Each member of Γ\Gamma is called a face. By axioms (i) and (ii) of Definition 2.2, I(M)\mathcal{I}(M) contains ∅\varnothing and is closed under taking subsets. Thus, I(M)\mathcal{I}(M) is a simplicial complex, which is called the independence complex of the matroid MM.

To study the coefficients HiH_i using algebraic methods, we introduce a graded quotient algebra associated with GG.

Definition 2.3.[5] Let P=Z2[xe:e∈E(G)]P = \mathbb{Z}_2[x_e : e \in E(G)], where each variable xex_e has degree 1. For any X⊆E(G)X \subseteq E(G), write xX=∏e∈Xxex^X = \prod_{e \in X} x_e, with x∅=1x^\varnothing= 1. A monomial is called squarefree if the exponent of each variable is either 0 or 1. Define

Icut=⟨xS:S⊆E(G), G−S is disconnected⟩,I_{\mathrm{cut}} = \left\langle x^S : S \subseteq E(G),\ G-S\text{ is disconnected} \right\rangle,
Jcyc=⟨∑e∈E(C)xe:C is a cycle of G⟩.J_{\mathrm{cyc}} = \left\langle\sum_{e \in E(C)} x_e : C\text{ is a cycle of }G \right\rangle.

Both IcutI_{\mathrm{cut}} and JcycJ_{\mathrm{cyc}} are homogeneous ideals. Define the graded quotient algebra

A(G)=P/(Icut+Jcyc)=⨁i≥0A(G)i,(6)\mathcal{A}(G) = P/(I_{\mathrm{cut}} + J_{\mathrm{cyc}}) = \bigoplus_{i \ge0} \mathcal{A}(G)_i, \tag*{(6)}

where A(G)i\mathcal{A}(G)_i is the homogeneous component of degree ii. Let xˉe\bar{x}_e denote the image of xex_e in the quotient algebra, and write xˉS=∏e∈Sxˉe\bar{x}^S = \prod_{e \in S} \bar{x}_e, with xˉ∅=1\bar{x}^{\varnothing} = 1.

Fix a binary cycle basis B={C1,…,Cd}\mathcal{B} = \{C_1,\ldots,C_d\} of GG. Since χC1,…,χCd\chi_{C_1},\ldots,\chi_{C_d} form a basis of the binary cycle space of GG, we have

Jcyc=(θ1,…,θd),θj=∑e∈E(Cj)xe,1≤j≤d.(7)J_{\mathrm{cyc}} = (\theta_1,\ldots,\theta_d),\qquad\theta_j = \sum_{e \in E(C_j)} x_e,\qquad1 \le j \le d. \tag*{(7)}

In particular, ∑e∈E(Cj)xˉe=0\sum_{e \in E(C_j)} \bar{x}_e = 0. If ee is a bridge of GG, then G−{e}G-\{e\} is disconnected, so xe∈Icutx_e \in I_{\mathrm{cut}} and hence xˉe=0\bar{x}_e = 0.

Let M(G)M(G) denote the graphic matroid of GG, whose independent sets are the edge sets that contain no cycles. Since GG is connected, the bases of M(G)M(G) are precisely the edge sets of the spanning trees of GG. Its dual matroid M(G)∗M(G)^* is called the cographic matroid of GG, whose bases are the complements of the edge sets of the spanning trees of GG. Consequently, r(M(G)∗)=m−(n−1)=dr(M(G)^*) = m-(n-1)=d.

By axiom (ii) of Definition 2.2, every subset of a basis is independent. Moreover, since the ground set is finite, every independent set can be extended to a basis. Thus, an edge set is independent in M(G)∗M(G)^* if and only if it is contained in a basis. For any S⊆E(G)S \subseteq E(G), we have

S∈I(M(G)∗)⟺there exists a spanning tree T such that S⊆E(G)∖E(T)S \in\mathcal{I}(M(G)^*) \Longleftrightarrow\text{there exists a spanning tree }T\text{ such that }S \subseteq E(G)\setminus E(T)
⟺there exists a spanning tree T such that E(T)⊆E(G)∖S\Longleftrightarrow\text{there exists a spanning tree }T\text{ such that }E(T) \subseteq E(G)\setminus S
⟺G−S is connected.\Longleftrightarrow G-S\text{ is connected}.

Therefore, the independent sets of M(G)∗M(G)^* are precisely the deletable edge sets of GG, and its independence complex is I(M(G)∗)={S⊆E(G):G−S is connected}\mathcal{I}(M(G)^*) = \{S \subseteq E(G) : G-S\text{ is connected}\}. The graded quotient ring Z2[M(G)∗]=P/⟨xS:S⊆E(G), S∉I(M(G)∗)⟩\mathbb{Z}_2[M(G)^*] = P/\langle x^S : S \subseteq E(G),\ S \notin\mathcal{I}(M(G)^*)\rangle is called the Stanley–Reisner ring of the independence complex of the cographic matroid M(G)∗M(G)^*. Define h0,…,hdh_0,\ldots,h_d by

∑S∈I(M(G)∗)t∣S∣(1−t)d−∣S∣=∑i=0dhiti.(8)\sum_{S \in\mathcal{I}(M(G)^*)} t^{|S|}(1-t)^{d-|S|} = \sum_{i=0}^{d} h_i t^i. \tag*{(8)}

The coefficient vector (h0,…,hd)(h_0,\ldots,h_d) is called the hh-vector of I(M(G)∗)\mathcal{I}(M(G)^*).

Lemma 2.4. [5] Let TT be a spanning tree of GG, and set

Θ={∑f∈E(CeT)xf:e∈E(G)∖E(T)}.\Theta= \left\{ \sum_{f \in E(C_e^T)} x_f : e \in E(G) \setminus E(T) \right\}.

Then the quotient algebra admits the graded decomposition

Z2[M(G)∗]/⟨Θ⟩=R0′⊕R1′⊕⋯⊕Rd′.\mathbb{Z}_2[M(G)^*]/\langle\Theta\rangle= R'_0 \oplus R'_1 \oplus\cdots\oplus R'_d.

where ⟨Θ⟩\langle\Theta\rangle denotes the ideal generated by the images of the linear forms in Θ\Theta in Z2[M(G)∗]\mathbb{Z}_2[M(G)^*], and Ri′R'_i denotes the homogeneous component of degree ii of Z2[M(G)∗]/⟨Θ⟩\mathbb{Z}_2[M(G)^*]/\langle\Theta\rangle, namely, the vector space consisting of the images of all homogeneous polynomials of degree ii in this quotient algebra. The dimensions of these homogeneous components form the hh-vector of M(G)∗M(G)^*; that is, dim⁡Z2Ri′=hi\dim_{\mathbb{Z}_2} R'_i = h_i.

Since the bases of M(G)∗M(G)^* are the complements of the edge sets of spanning trees, its independent sets are precisely the deletable edge sets. Hence, for each 0≤k≤d0 \le k \le d, there are exactly FkF_k independent sets of cardinality kk. By (1), (3), and the identity m=n−1+dm = n - 1 + d, we obtain

∑i=0dHiqi=∑k=0dFkqk(1−q)d−k.\sum_{i=0}^{d} H_iq^i = \sum_{k=0}^{d} F_kq^k(1-q)^{d-k}.

(8) also gives

∑i=0dhiqi=∑k=0dFkqk(1−q)d−k.\sum_{i=0}^{d} h_iq^i = \sum_{k=0}^{d} F_kq^k(1-q)^{d-k}.

Therefore, ∑i=0dHiqi=∑i=0dhiqi\sum_{i=0}^{d} H_iq^i = \sum_{i=0}^{d} h_iq^i. Comparing coefficients yields Hi=hiH_i = h_i for every 0≤i≤d0 \le i \le d. Thus, (H0,…,Hd)(H_0,\ldots,H_d) is precisely the hh-vector of the independence complex of M(G)∗M(G)^*.

Lemma 2.5. [5] The images of the squarefree monomials {xS:S⊆E(G)}\{x^S : S \subseteq E(G)\} in the quotient algebra P/(Icut+Jcyc)P/(I_{\mathrm{cut}} + J_{\mathrm{cyc}}) span this algebra.

When GG is loopless, the assertion follows directly from [5]. If GG contains loops, then each loop ee forms a cycle by itself, so xe∈Jcycx_e \in J_{\mathrm{cyc}} and hence x‾e=0\overline{x}_e = 0. Since deleting loops does not affect the connectivity of GG, we have A(G)≅A(G0)\mathcal{A}(G) \cong\mathcal{A}(G_0). Applying Lemma 2.5 to G0G_0 therefore yields the desired spanning result for A(G)\mathcal{A}(G).

To identify the indices for which HiH_i is positive or zero, we state the following result on the hh-vector of a matroid independence complex.

Lemma 2.6. [7] Let MM be a finite matroid of rank rr whose independence complex I(M)\mathcal{I}(M) has hh-vector (h0,…,hr)(h_0,\ldots,h_r). If MM has exactly aa elements that belong to every basis, then

hi>0(0≤i≤r−a),hi=0(r−a<i≤r).h_i > 0 \qquad(0 \le i \le r-a), \qquad h_i = 0 \qquad(r-a < i \le r).

We next recall the third isomorphism theorem for rings, which will be used to handle successive quotients.

Lemma 2.7. [4] Let RR be an associative ring, and let II, JJ be two-sided ideals of RR with I⊆JI \subseteq J. Then J/IJ/I is a two-sided ideal of the quotient ring R/IR/I, and the map

φ:(R/I)/(J/I)⟶R/J,\varphi: (R/I)/(J/I) \longrightarrow R/J,
(r+I)+(J/I)⟼r+J(r + I) + (J/I) \longmapsto r + J

is a ring isomorphism. Consequently, (R/I)/(J/I)≅R/J(R/I)/(J/I) \cong R/J.

We next relate the quotient algebra defined above to the coefficients HiH_i and identify these coefficients with the dimensions of its homogeneous components.

Lemma 2.8. For every i≥0i \ge0, we have

Hi={dim⁡Z2A(G)i,0≤i≤d,0,i>d,H_i = \begin{cases} \dim_{\mathbb{Z}_2} \mathcal{A}(G)_i, & 0 \le i \le d,\\ 0, & i > d, \end{cases}

and

A(G)i={span⁡Z2{xS:S⊆E(G), ∣S∣=i, G−S is connected},0≤i≤d,{0},i>d.\mathcal{A}(G)_i = \begin{cases} \operatorname{span}_{\mathbb{Z}_2}\{x^S : S \subseteq E(G),\ |S| = i,\ G-S\text{ is connected}\}, & 0 \le i \le d,\\ \{0\}, & i > d. \end{cases}

Proof. First, since the independent sets of M(G)∗M(G)^* are precisely the deletable edge sets of GG, for any S⊆E(G)S \subseteq E(G) we have S∉I(M(G)∗)S \notin\mathcal{I}(M(G)^*) if and only if G−SG-S is disconnected. Thus, the Stanley–Reisner ideal of the independence complex of M(G)∗M(G)^* is

⟨xS:S⊆E(G), S∉I(M(G)∗)⟩=⟨xS:S⊆E(G), G−S is disconnected⟩=Icut.\left\langle x^S : S \subseteq E(G),\ S \notin\mathcal{I}(M(G)^*) \right\rangle = \left\langle x^S : S \subseteq E(G),\ G-S\text{ is disconnected}\right\rangle = I_{\mathrm{cut}}.

Consequently, Z2[M(G)∗]=P/Icut\mathbb{Z}_2[M(G)^*] = P/I_{\mathrm{cut}}.

Next, fix a spanning tree TT of GG. Let θe=∑f∈E(CTe)xf\theta_e = \sum_{f\in E(C^e_T)} x_f, so that Θ={θe:e∈E(G)∖E(T)}\Theta= \{\theta_e : e \in E(G) \setminus E(T)\}. Let ⟨Θ⟩P\langle\Theta\rangle_P denote the ideal generated by the linear forms in Θ\Theta in the polynomial ring PP. We now show that ⟨Θ⟩P=Jcyc\langle\Theta\rangle_P = J_{\mathrm{cyc}}.

We first prove that Jcyc⊆⟨Θ⟩PJ_{\mathrm{cyc}} \subseteq\langle\Theta\rangle_P. Let CC be an arbitrary cycle of GG. Since the characteristic vectors of the fundamental cycles CTeC^e_T form a basis of the binary cycle space, there exist coefficients ae∈Z2a_e \in\mathbb{Z}_2 such that

χC=∑e∈E(G)∖E(T)aeχCTe.\chi_C = \sum_{e\in E(G)\setminus E(T)} a_e\chi_{C^e_T}.

For any f∈E(G)f \in E(G), comparing the coordinates indexed by ff on both sides yields

(χC)f=∑e∈E(G)∖E(T)ae(χCTe)f.(9)(\chi_C)_f = \sum_{e\in E(G)\setminus E(T)} a_e(\chi_{C^e_T})_f. \tag*{(9)}

Since (χC)f=1(\chi_C)_f = 1 when f∈E(C)f \in E(C) and (χC)f=0(\chi_C)_f = 0 otherwise, we have

∑f∈E(G)(χC)fxf=∑f∈E(C)1⋅xf+∑f∈E(G)∖E(C)0⋅xf=∑f∈E(C)xf.(10)\sum_{f\in E(G)}(\chi_C)_f x_f = \sum_{f\in E(C)}1\cdot x_f + \sum_{f\in E(G)\setminus E(C)}0\cdot x_f = \sum_{f\in E(C)}x_f. \tag*{(10)}

Combining (9) and (10), we obtain ∑f∈E(C)xf=∑e∈E(G)∖E(T)aeθe\sum_{f\in E(C)}x_f = \sum_{e\in E(G)\setminus E(T)}a_e\theta_e. Each θe\theta_e belongs to ⟨Θ⟩P\langle\Theta\rangle_P, which is closed under addition and multiplication by elements of PP. Hence, the above linear

combination also belongs to ⟨Θ⟩P\langle\Theta\rangle_P, and therefore ∑f∈E(C)xf∈⟨Θ⟩P\sum_{f\in E(C)} x_f \in\langle\Theta\rangle_P. Since CC is arbitrary, ⟨Θ⟩P\langle\Theta\rangle_P contains the linear form associated with every cycle of GG. As JcycJ_{\mathrm{cyc}} is precisely the ideal generated by all these linear forms, we conclude that Jcyc⊆⟨Θ⟩PJ_{\mathrm{cyc}} \subseteq\langle\Theta\rangle_P.

Conversely, every fundamental cycle CeTC_e^T is itself a cycle of GG. Since JcycJ_{\mathrm{cyc}} is the ideal generated by the linear forms associated with all cycles of GG, we have θe=∑f∈E(CeT)xf∈Jcyc\theta_e = \sum_{f\in E(C_e^T)} x_f \in J_{\mathrm{cyc}} for every non-tree edge e∈E(G)∖E(T)e \in E(G) \setminus E(T). Thus, all linear forms in Θ\Theta belong to JcycJ_{\mathrm{cyc}}. Since JcycJ_{\mathrm{cyc}} is an ideal, it also contains all polynomial multiples of these linear forms and all finite sums of such multiples. By the definition of ⟨Θ⟩P\langle\Theta\rangle_P as the ideal generated by the linear forms in Θ\Theta in the polynomial ring PP, it follows that ⟨Θ⟩P⊆Jcyc\langle\Theta\rangle_P \subseteq J_{\mathrm{cyc}}.

Combining the two inclusions yields ⟨Θ⟩P=Jcyc\langle\Theta\rangle_P = J_{\mathrm{cyc}}.

Next, let ⟨Θ⟩\langle\Theta\rangle denote the ideal in P/IcutP/I_{\mathrm{cut}} generated by the images of the linear forms in Θ\Theta. Since every element of IcutI_{\mathrm{cut}} maps to zero in the quotient ring, adding an element of IcutI_{\mathrm{cut}} to an element of ⟨Θ⟩P\langle\Theta\rangle_P does not change its image. Hence, ⟨Θ⟩=(Icut+⟨Θ⟩P)/Icut\langle\Theta\rangle= (I_{\mathrm{cut}} + \langle\Theta\rangle_P)/I_{\mathrm{cut}}. Therefore, by Lemma 2.7 and (6), we have

Z2[M(G)∗]⟨Θ⟩=Z2[M(G)∗](Icut+⟨Θ⟩P)/Icut=P/Icut(Icut+⟨Θ⟩P)/Icut≃PIcut+⟨Θ⟩P=PIcut+Jcyc=A(G).\frac{\mathbb{Z}_2[M(G)^*]}{\langle\Theta\rangle} = \frac{\mathbb{Z}_2[M(G)^*]}{(I_{\mathrm{cut}}+\langle\Theta\rangle_P)/I_{\mathrm{cut}}} = \frac{P/I_{\mathrm{cut}}}{(I_{\mathrm{cut}}+\langle\Theta\rangle_P)/I_{\mathrm{cut}}} \simeq \frac{P}{I_{\mathrm{cut}}+\langle\Theta\rangle_P} = \frac{P}{I_{\mathrm{cut}}+J_{\mathrm{cyc}}} = \mathcal{A}(G).

By Lemma 2.4, it follows that

dim⁡Z2A(G)i=dim⁡Z2Ri′=hi=Hi.\dim_{\mathbb{Z}_2}\mathcal{A}(G)_i=\dim_{\mathbb{Z}_2}R'_i=h_i=H_i.

For i>di>d, we have A(G)i={0}\mathcal{A}(G)_i=\{0\} and Hi=0H_i=0, so dim⁡Z2A(G)i=Hi=0\dim_{\mathbb{Z}_2}\mathcal{A}(G)_i=H_i=0.

Finally, we prove the spanning assertion for each homogeneous component. For i≥0i\ge0, let u∈A(G)iu\in\mathcal{A}(G)_i be arbitrary. By Lemma 2.5, there exist coefficients aS∈Z2a_S\in\mathbb{Z}_2 such that u=∑S⊆E(G)aSxˉSu=\sum_{S\subseteq E(G)}a_S\bar{x}^S. Since Icut+JcycI_{\mathrm{cut}}+J_{\mathrm{cyc}} is a homogeneous ideal, A(G)\mathcal{A}(G) is a graded algebra in which each xˉS\bar{x}^S is homogeneous of degree ∣S∣|S|. Taking the homogeneous component of degree ii on both sides yields u=∑S⊆E(G), ∣S∣=iaSxˉSu=\sum_{S\subseteq E(G),\,|S|=i}a_S\bar{x}^S. If G−SG-S is disconnected, then xS∈Icutx^S\in I_{\mathrm{cut}} and hence xˉS=0\bar{x}^S=0. Omitting these zero terms, we obtain

u=∑S⊆E(G),∣S∣=i,G−S is connectedaSxˉS.u=\sum_{\substack{S\subseteq E(G),\,|S|=i,\\G-S\text{ is connected}}}a_S\bar{x}^S.

Therefore, A(G)i⊆span⁡Z2{xˉS:S⊆E(G), ∣S∣=i, G−S is connected}\mathcal{A}(G)_i\subseteq\operatorname{span}_{\mathbb{Z}_2}\{\bar{x}^S:S\subseteq E(G),\,|S|=i,\,G-S\text{ is connected}\}. Conversely, each xˉS\bar{x}^S in this set belongs to A(G)i\mathcal{A}(G)_i, so their span is also contained in A(G)i\mathcal{A}(G)_i; that is, $\mathcal{A}(G)_i\supseteq\operatorname{span}_{\mathbb{Z}_2}{\bar{x}^S:S\subseteq E(G),,|S|=i,,G-S\text{ is connected}}. Thus,

A(G)i=span⁡Z2{xˉS:S⊆E(G), ∣S∣=i, G−S is connected}.\mathcal{A}(G)_i=\operatorname{span}_{\mathbb{Z}_2}\{\bar{x}^S:S\subseteq E(G),\,|S|=i,\,G-S\text{ is connected}\}.

If G−SG-S is connected, then it has at least n−1n-1 edges, so m−∣S∣≥n−1m-|S|\ge n-1 and hence ∣S∣≤m−n+1=d|S|\le m-n+1=d. Thus, when i>di>d, there is no deletable edge set of cardinality ii, and the set of monomials in the spanning expression above is empty. Since the span of the empty set is the zero space, we obtain A(G)i=span⁡Z2(∅)={0}\mathcal{A}(G)_i=\operatorname{span}_{\mathbb{Z}_2}(\varnothing)=\{0\}. ∴

To estimate the dimensions of higher-degree homogeneous components using dimension bounds for the degree-one subspaces associated with the cycles in a cycle basis, we state two standard dimension estimates for products and sums of subspaces. Inequality (11) follows directly from the tensor product basis theorem in [15], while (12) follows from the dimension estimate for sums of subspaces in [13].

Lemma 2.9. Let AA be a nonzero unital commutative graded algebra over a field KK, let ss be a nonnegative integer, and let V1,…,Vs⊆A1V_1,\ldots,V_s \subseteq A_1 be finite-dimensional subspaces. Denote by V1⋯VsV_1\cdots V_s the KK-vector space spanned by all products v1⋯vsv_1\cdots v_s with vj∈Vjv_j \in V_j. Then

dim⁡K(V1⋯Vs)≤∏j=1sdim⁡KVj.(11)\dim_K(V_1\cdots V_s) \le\prod_{j=1}^{s}\dim_K V_j. \tag*{(11)}

If {Wα}α∈Λ\{W_\alpha\}_{\alpha\in\Lambda} is a finite family of finite-dimensional subspaces of a common KK-vector space, then

dim⁡K(∑α∈ΛWα)≤∑α∈Λdim⁡KWα.(12)\dim_K\left(\sum_{\alpha\in\Lambda}W_\alpha\right) \le\sum_{\alpha\in\Lambda}\dim_K W_\alpha. \tag*{(12)}

By convention, the empty product space for s=0s=0 is K⋅1AK\cdot1_A, and the sum of an empty family of subspaces is {0}\{0\}. The empty numerical product and sum are taken to be 11 and 00, respectively.

Proof of Theorem 1.2

Proof of Theorem 1.2. By Lemma 2.8, for every 0≤i≤d0 \le i \le d, we have Hi=dim⁡Z2A(G)i≥0H_i=\dim_{\mathbb{Z}_2} A(G)_i \ge0. Moreover, A(G)iA(G)_i is spanned by the squarefree monomials xˉS\bar{x}^{S} for which ∣S∣=i|S|=i and G−SG-S is connected. Thus, to prove (2), it suffices to show that

dim⁡Z2A(G)i≤∑I⊆[d]∣I∣=i∏j∈I(cj−1).\dim_{\mathbb{Z}_2} A(G)_i \le\sum_{\substack{I\subseteq[d]\\|I|=i}}\prod_{j\in I}(c_j-1).

To this end, we first match the edges of each deletable edge set to distinct cycles in the given cycle basis and then show that the corresponding monomial lies in the product space determined by these cycles.

We first show that, for every deletable edge set S⊆E(G)S\subseteq E(G), there exists an injection

φ:S⟶[d],e∈E(Cφ(e))(e∈S).\varphi:S\longrightarrow[d],\qquad e\in E(C_{\varphi(e)})\quad(e\in S).

If S=∅S=\varnothing, the empty map suffices. Henceforth, assume that S≠∅S\ne\varnothing. Since G−SG-S is connected, choose a spanning tree TT of G−SG-S. Because all vertices are retained when edges are deleted, TT is also a spanning tree of GG. Moreover, E(T)⊆E(G)∖SE(T)\subseteq E(G)\setminus S, so S⊆E(G)∖E(T)S\subseteq E(G)\setminus E(T). By Lemma 2.2, there exists a bijection

f:E(G)∖E(T)⟶B,e∈E(f(e)).f:E(G)\setminus E(T)\longrightarrow\mathcal{B},\qquad e\in E(f(e)).

For each e∈Se\in S, define φ(e)=j\varphi(e)=j whenever f(e)=Cjf(e)=C_j. Since B={C1,…,Cd}\mathcal{B}=\{C_1,\ldots,C_d\}, each e∈Se\in S determines a unique index φ(e)∈[d]\varphi(e)\in[d]. The injectivity of ff implies that φ\varphi is also injective. For every e∈Se\in S, we have e∈E(f(e))=E(Cφ(e))e\in E(f(e))=E(C_{\varphi(e)}).

Next, for each j∈[d]j \in[d], define

Vj=span⁡Z2{xˉe:e∈E(Cj)}⊆A(G)1.V_j = \operatorname{span}_{\mathbb{Z}_2}\{\bar{x}_e : e \in E(C_j)\} \subseteq A(G)_1.

The space VjV_j is spanned by the images of the cjc_j edge variables corresponding to the edges of CjC_j. By (7), we have ∑e∈E(Cj)xe∈Jcyc\sum_{e \in E(C_j)} x_e \in J_{\mathrm{cyc}}, so ∑e∈E(Cj)xˉe=0\sum_{e \in E(C_j)} \bar{x}_e = 0 in the quotient algebra. Since CjC_j is nonempty, choose any edge e0∈E(Cj)e_0 \in E(C_j). Over the field Z2\mathbb{Z}_2, we have xˉe0=∑e∈E(Cj)∖{e0}xˉe\bar{x}_{e_0} = \sum_{e \in E(C_j)\setminus\{e_0\}} \bar{x}_e, which expresses xˉe0\bar{x}_{e_0} as a linear combination of the images of the remaining cj−1c_j-1 edge variables. Thus, removing xˉe0\bar{x}_{e_0} from the spanning family leaves a family that still spans VjV_j; that is,

Vj=span⁡Z2{xˉe:e∈E(Cj)∖{e0}}.V_j = \operatorname{span}_{\mathbb{Z}_2}\{\bar{x}_e : e \in E(C_j)\setminus\{e_0\}\}.

Since every vector in VjV_j can be expressed as a linear combination of these cj−1c_j-1 vectors, the dimension of VjV_j is at most cj−1c_j-1; that is,

dim⁡Z2Vj≤cj−1.(13)\dim_{\mathbb{Z}_2} V_j \leq c_j-1. \tag*{(13)}

In particular, when cj=1c_j=1, the cycle CjC_j consists of a single loop, so Vj={0}V_j=\{0\} and (13) remains valid.

Next, for each I⊆[d]I \subseteq[d], let

WI=∏j∈IVj=span⁡Z2{∏j∈Ivj:vj∈Vj (j∈I)}.W_I = \prod_{j\in I} V_j = \operatorname{span}_{\mathbb{Z}_2}\left\{\prod_{j\in I}v_j : v_j \in V_j\ (j\in I)\right\}.

By Lemma 2.9 and (13), we obtain

dim⁡Z2WI≤∏j∈Idim⁡Z2Vj≤∏j∈I(cj−1).(14)\dim_{\mathbb{Z}_2} W_I \leq\prod_{j\in I}\dim_{\mathbb{Z}_2} V_j \leq\prod_{j\in I}(c_j-1). \tag*{(14)}

We now prove that A(G)i=∑I⊆[d], ∣I∣=iWIA(G)_i = \sum_{I\subseteq[d],\,|I|=i} W_I.

We first show that A(G)i⊆∑I⊆[d], ∣I∣=iWIA(G)_i \subseteq\sum_{I\subseteq[d],\,|I|=i} W_I. Let SS be a nonempty deletable edge set of cardinality ii. There exists an injection φ:S⟶[d]\varphi:S\longrightarrow[d] such that e∈E(Cφ(e))e\in E(C_{\varphi(e)}) for every e∈Se\in S. Set I=φ(S)I=\varphi(S), so that φ\varphi induces a bijection between SS and II. For each j∈Ij\in I, let e∈Se\in S be the unique edge for which φ(e)=j\varphi(e)=j, and set vj=xˉev_j=\bar{x}_e. Since e∈E(Cj)e\in E(C_j), we have vj∈Vjv_j\in V_j. Thus, the product ∏j∈Ivj\prod_{j\in I}v_j is formed by choosing one element from each VjV_j. By the definition WI=∏j∈IVjW_I=\prod_{j\in I}V_j, we obtain xˉS=∏e∈Sxˉe=∏j∈Ivj∈WI\bar{x}^S=\prod_{e\in S}\bar{x}_e=\prod_{j\in I}v_j\in W_I. When S=∅S=\varnothing, we take I=∅I=\varnothing, and then xˉS=1∈W∅\bar{x}^S=1\in W_{\varnothing}, so the assertion remains valid. By Lemma 2.8, A(G)iA(G)_i is spanned by all monomials xˉS\bar{x}^S for which ∣S∣=i|S|=i and G−SG-S is connected. Each such monomial belongs to some WIW_I with ∣I∣=i|I|=i. Consequently, every element of A(G)iA(G)_i belongs to the sum of these subspaces, which gives A(G)i⊆∑I⊆[d], ∣I∣=iWIA(G)_i\subseteq\sum_{I\subseteq[d],\,|I|=i}W_I.

We next prove that ∑I⊆[d], ∣I∣=iWI⊆A(G)i\sum_{I\subseteq[d],\,|I|=i}W_I\subseteq A(G)_i. Since A(G)A(G) is a graded quotient algebra, its multiplication satisfies A(G)r1A(G)r2⊆A(G)r1+r2A(G)_{r_1}A(G)_{r_2}\subseteq A(G)_{r_1+r_2} for all r1,r2≥0r_1,r_2\geq0. Write I={j1,…,js}I=\{j_1,\ldots,j_s\}, where s=∣I∣=i≥1s=|I|=i\ge1. For each ℓ∈{1,…,s}\ell\in\{1,\ldots,s\}, choose an arbitrary vjℓ∈Vjℓv_{j_\ell}\in V_{j_\ell}. Since Vjℓ⊆A(G)1V_{j_\ell}\subseteq\mathcal{A}(G)_1, repeated application of the multiplication property yields

vj1⋯vjs∈A(G)1+⋯+1=A(G)s.v_{j_1}\cdots v_{j_s}\in\mathcal{A}(G)_1+\cdots+1=\mathcal{A}(G)_s.

Every element of WIW_I is a linear combination of products of the form ∏j∈Ivj\prod_{j\in I}v_j, so WI⊆A(G)s=A(G)iW_I\subseteq\mathcal{A}(G)_s=\mathcal{A}(G)_i. When I=∅I=\varnothing, we have W∅=Z2⋅1⊆A(G)0W_\varnothing=\mathbb{Z}_2\cdot1\subseteq\mathcal{A}(G)_0, so the assertion remains valid. Since each WIW_I with ∣I∣=i|I|=i is contained in A(G)i\mathcal{A}(G)_i, their sum is also contained in A(G)i\mathcal{A}(G)_i. Hence,

∑I⊆[d]∣I∣=iWI⊆A(G)i.\sum_{\substack{I\subseteq[d]\\|I|=i}}W_I\subseteq\mathcal{A}(G)_i.

Combining the two inclusions, we obtain

A(G)i=∑I⊆[d]∣I∣=iWI.(15)\mathcal{A}(G)_i=\sum_{\substack{I\subseteq[d]\\|I|=i}}W_I. \tag*{(15)}

Finally, applying Lemmas 2.8 and 2.9, together with (14) and (15), yields

Hi=dim⁡Z2A(G)i=dim⁡Z2(∑I⊆[d]∣I∣=iWI)≤∑I⊆[d]∣I∣=idim⁡Z2WI≤∑I⊆[d]∣I∣=i∏j∈I(cj−1).H_i=\dim_{\mathbb{Z}_2}\mathcal{A}(G)_i=\dim_{\mathbb{Z}_2}\left(\sum_{\substack{I\subseteq[d]\\|I|=i}}W_I\right)\le\sum_{\substack{I\subseteq[d]\\|I|=i}}\dim_{\mathbb{Z}_2}W_I\le\sum_{\substack{I\subseteq[d]\\|I|=i}}\prod_{j\in I}(c_j-1).

Since HiH_i is nonnegative, we conclude that

0≤Hi≤∑I⊆[d]∣I∣=i∏j∈I(cj−1),0\le H_i\le\sum_{\substack{I\subseteq[d]\\|I|=i}}\prod_{j\in I}(c_j-1),

where d=m−n+1d=m-n+1.

We now show that equality holds in the second inequality in (2) simultaneously for all 0≤i≤d0\le i\le d if and only if GG is a cactus graph. We first prove necessity. Suppose that Hi=∑I⊆[d]∣I∣=i∏j∈I(cj−1)H_i=\sum_{\substack{I\subseteq[d]\\|I|=i}}\prod_{j\in I}(c_j-1) for every 0≤i≤d0\le i\le d. If d=0d=0, then GG is a tree and hence a cactus graph. Henceforth, assume that d≥1d\ge1. Taking i=1i=1 gives H1=∑j=1d(cj−1)H_1=\sum_{j=1}^{d}(c_j-1). Using H1=n−1−bH_1=n-1-b and d=m−n+1d=m-n+1, we obtain

∑j=1dcj=H1+d=(n−1−b)+(m−n+1)=m−b.(16)\sum_{j=1}^{d}c_j=H_1+d=(n-1-b)+(m-n+1)=m-b. \tag*{(16)}

First, we show that the union of the edge sets of the basis cycles is precisely the set of all non-bridge edges of GG. Let ee be an arbitrary non-bridge edge of GG. If ee is a loop, then it forms a cycle CC by itself. Otherwise, since G−{e}G-\{e\} is connected, there exists a simple path between the endpoints of ee that avoids ee. This path, together with ee, forms a cycle CC. Since the characteristic vectors of the cycles in B={C1,…,Cd}\mathcal{B}=\{C_1,\ldots,C_d\} span the binary cycle space, there exist a1,…,ad∈Z2a_1,\ldots,a_d\in\mathbb{Z}_2 such that

χC=∑j=1dajχCj.\chi_C=\sum_{j=1}^{d}a_j\chi_{C_j}.

Suppose that ee belongs to none of the basis cycles. Then (χCj)e=0(\chi_{C_j})_e=0 for every j∈[d]j\in[d], and hence

(χC)e=∑j=1daj(χCj)e=0.(\chi_C)_e=\sum_{j=1}^{d}a_j(\chi_{C_j})_e=0.

This contradicts (χC)e=1(\chi_C)_e = 1, which holds because e∈E(C)e \in E(C). Thus, ee belongs to at least one basis cycle. Since ee was arbitrary, every non-bridge edge belongs to at least one basis cycle.

Choose any edge of a fundamental cycle. If it is a self-loop, deleting it does not affect connectivity; otherwise, after its deletion, its endpoints remain connected via the remaining edges of the cycle. Thus, deleting any edge of a basis cycle leaves GG connected, so every edge of a basis cycle is a non-bridge edge.

Thus, the union of the edge sets of the basis cycles is precisely the set of all non-bridge edges of GG, so

∣⋃j=1dE(Cj)∣=m−b.\left|\bigcup_{j=1}^{d} E(C_j)\right| = m-b.

Combining cj=∣E(Cj)∣c_j = |E(C_j)| with (16), we obtain

∑j=1d∣E(Cj)∣=∑j=1dcj=m−b=∣⋃j=1dE(Cj)∣.\sum_{j=1}^{d} |E(C_j)| = \sum_{j=1}^{d} c_j = m-b = \left|\bigcup_{j=1}^{d} E(C_j)\right|.

Here, ∑j=1d∣E(Cj)∣\sum_{j=1}^{d} |E(C_j)| counts the edges separately for each basis cycle, whereas ∣⋃j=1dE(Cj)∣\left|\bigcup_{j=1}^{d} E(C_j)\right| counts each edge in the union exactly once. If two basis cycles share an edge, then that edge is counted at least twice in ∑j=1d∣E(Cj)∣\sum_{j=1}^{d} |E(C_j)| but only once in ∣⋃j=1dE(Cj)∣\left|\bigcup_{j=1}^{d} E(C_j)\right|. Every other edge in the union is counted at least once in the former expression, so ∑j=1d∣E(Cj)∣>∣⋃j=1dE(Cj)∣\sum_{j=1}^{d} |E(C_j)| > \left|\bigcup_{j=1}^{d} E(C_j)\right|, which contradicts the equality above. Therefore, the edge sets of C1,…,CdC_1,\ldots,C_d are pairwise disjoint.

Let CC be an arbitrary cycle of GG. Since B={C1,…,Cd}\mathcal{B} = \{C_1,\ldots,C_d\} is a binary cycle basis, the edge set of CC can be expressed as the symmetric difference of the edge sets of some basis cycles. Since these edge sets are pairwise disjoint, each edge occurs exactly once among the selected cycles. Hence, their symmetric difference coincides with their union.

We next show that only one basis cycle can be selected. Suppose that at least two basis cycles are selected. If the selected cycles are pairwise vertex-disjoint, then the subgraph they form is disconnected, which contradicts the connectedness of CC. Otherwise, two selected cycles share a vertex, at which each cycle contributes degree 2, with a loop contributing 2 to the degree of its vertex. Since these two cycles have disjoint edge sets, their union has degree 4 at the shared vertex. The subgraph formed by all selected cycles therefore has degree at least 4 at that vertex, which contradicts the fact that every vertex of CC has degree 2. Thus, at most one basis cycle can be selected. Since CC is nonempty, exactly one is selected, so C=CjC = C_j for some j∈[d]j \in[d]. As CC was arbitrary, the cycles of GG are precisely C1,…,CdC_1,\ldots,C_d. Their edge sets are pairwise disjoint, so every edge of GG belongs to at most one cycle. Therefore, GG is a cactus graph.

We next prove sufficiency. Suppose that GG is a cactus graph. Then the edge sets of all its cycles are pairwise disjoint, so their characteristic vectors are linearly independent. Since these vectors also span the binary cycle space of GG, they form a basis of this space. As the binary cycle space has dimension dd, the graph GG has exactly dd cycles. Thus, the binary cycle basis B={C1,…,Cd}\mathcal{B} = \{C_1,\ldots,C_d\} consists of all the cycles of GG. Since every non-bridge edge belongs to a cycle and no bridge belongs to any cycle, E(G)E(G) is the disjoint union of the set of bridges and the edge sets of C1,…,CdC_1,\ldots,C_d. Using cj=∣E(Cj)∣c_j = |E(C_j)| and d=m−n+1d = m-n+1, we obtain

m=b+∑j=1dcj,n−1=m−d=b+∑j=1d(cj−1).m=b+\sum_{j=1}^{d}c_j,\qquad n-1=m-d=b+\sum_{j=1}^{d}(c_j-1).

Delete an arbitrary edge from each CjC_j and retain all bridges. Deleting a loop does not affect connectivity. For each deleted non-loop edge, its endpoints remain connected by the remaining edges of the cycle containing it. Since the cycles have pairwise disjoint edge sets, none of these remaining edges has been deleted, so the resulting spanning subgraph is connected. Moreover, exactly dd distinct edges have been deleted, leaving a spanning subgraph with nn vertices and m−d=n−1m-d=n-1 edges. Hence, this subgraph is a spanning tree of GG. Conversely, every spanning tree is acyclic and therefore omits at least one edge from each CjC_j. Since the complement of its edge set contains exactly dd edges and the dd cycles have pairwise disjoint edge sets, exactly one edge is deleted from each cycle, and all bridges are retained. Thus, the spanning trees of GG are precisely the spanning subgraphs obtained by deleting one edge from each CjC_j and retaining all bridges.

It follows that the spanning subgraph consisting of the operational edges is connected if and only if all bridges are operational and at most one edge fails in each CjC_j. Indeed, if the spanning subgraph consisting of the operational edges is connected, then it contains a spanning tree. All failed edges lie in the complement of the edge set of this tree, so no bridge has failed, and each CjC_j contains at most one failed edge. Conversely, suppose that all bridges are operational and each CjC_j contains at most one failed edge. In each cycle containing a failed edge, select that edge; in each cycle containing no failed edge, select an arbitrary edge. Deleting the selected edges yields a spanning tree, all of whose edges are operational. Therefore, the spanning subgraph consisting of the operational edges is connected.

The probability that all bridges are operational is (1−q)b(1-q)^b. For each CjC_j, the probability that no edge fails is (1−q)cj(1-q)^{c_j}, and the probability that exactly one edge fails is cjq(1−q)cj−1c_jq(1-q)^{c_j-1}. When cj=1c_j=1, the condition that at most one edge fails is always satisfied, and its probability is (1−q)+q=1(1-q)+q=1, which is consistent with the fact that loops do not affect connectivity. Since edges fail independently, and the set of bridges and the edge sets of the cycles are pairwise disjoint, we have

RG(q)=(1−q)b∏j=1d((1−q)cj+cjq(1−q)cj−1)=(1−q)n−1∏j=1d(1+(cj−1)q).R_G(q)=(1-q)^b\prod_{j=1}^{d}\left((1-q)^{c_j}+c_jq(1-q)^{c_j-1}\right)=(1-q)^{n-1}\prod_{j=1}^{d}(1+(c_j-1)q).

Comparing this with (1) gives ∑i=0dHiqi=∏j=1d(1+(cj−1)q)\sum_{i=0}^{d}H_iq^i=\prod_{j=1}^{d}(1+(c_j-1)q). Expanding the product ∏j=1d(1+(cj−1)q)\prod_{j=1}^{d}(1+(c_j-1)q) and comparing the coefficients of qiq^i, we obtain

Hi=∑I⊆[d],∣I∣=i∏j∈I(cj−1),0≤i≤d.H_i=\sum_{\substack{I\subseteq[d],\\ |I|=i}}\prod_{j\in I}(c_j-1),\qquad0\leq i\leq d.

When d=0d = 0, all empty products are taken to be 1, so the conclusion remains valid.

We next show that, for i>d−ℓi > d - \ell, equality holds in the first inequality if and only if the connected multigraph obtained from GG by deleting all loops has cycle rank at most i−1i - 1, and that Hi>0H_i > 0 for 0≤i≤d−ℓ0 \le i \le d - \ell. In particular, if GG is loopless, then the first inequality is strict throughout the stated range.

Since the bases of M(G)∗M(G)^* are precisely the complements of the edge sets of spanning trees of GG, an element belongs to every basis of M(G)∗M(G)^* if and only if the corresponding edge belongs to no spanning tree of GG. No loop belongs to a spanning tree, whereas every non-loop edge is contained in some spanning tree. Thus, M(G)∗M(G)^* has exactly ℓ\ell elements that belong to every basis.

Since r(M(G)∗)=dr(M(G)^*) = d and (H0,…,Hd)(H_0, \ldots, H_d) is the hh-vector of the independence complex of M(G)∗M(G)^*, Lemma 2.6 yields

Hi>0(0≤i≤d−ℓ),Hi=0(d−ℓ<i≤d).H_i > 0 \quad(0 \le i \le d - \ell), \qquad H_i = 0 \quad(d - \ell< i \le d).

The graph obtained by deleting all loops from GG remains connected and has cycle rank

(m−ℓ)−n+1=d−ℓ.(m - \ell) - n + 1 = d - \ell.

Therefore, for i>d−ℓi > d - \ell, equality holds in the first inequality if and only if deleting all loops from GG leaves a connected multigraph of cycle rank at most i−1i - 1; for 0≤i≤d−ℓ0 \le i \le d - \ell, we have Hi>0H_i > 0. In particular, if GG is loopless, then ℓ=0\ell= 0, so the first inequality is strict for every 0≤i≤d0 \le i \le d. □\square

Proof of Corollary 1.1. Set Bk=∑J⊆[d],∣J∣=k∏j∈J(cj−1)B_k = \sum_{\substack{J \subseteq[d],\,|J|=k}}\prod_{j\in J}(c_j - 1) (0≤k≤d)(0 \le k \le d). Substitute q=t/(1+t)q = t/(1 + t) into (1) and (3), and multiply both identities by (1+t)m(1 + t)^m. Using m=n−1+dm = n - 1 + d, we obtain

∑i=0dFiti=∑k=0dHktk(1+t)d−k.\sum_{i=0}^{d} F_i t^i = \sum_{k=0}^{d} H_k t^k(1+t)^{d-k}.

Furthermore, we have

∏j=1d(1+cjt)=∏j=1d((1+t)+(cj−1)t)=∑k=0dBktk(1+t)d−k.\prod_{j=1}^{d}(1+c_jt)=\prod_{j=1}^{d}((1+t)+(c_j-1)t)=\sum_{k=0}^{d}B_k t^k(1+t)^{d-k}.

Comparing the coefficients of tit^i on both sides yields

∑I⊆[d],∣I∣=i∏j∈Icj−Fi=∑k=0i(d−ki−k)(Bk−Hk)≥0.\sum_{\substack{I\subseteq[d],\,|I|=i}}\prod_{j\in I}c_j-F_i =\sum_{k=0}^{i}\binom{d-k}{i-k}(B_k-H_k)\ge0.

Therefore, Fi≤∑I⊆[d],∣I∣=i∏j∈IcjF_i \le\sum_{\substack{I\subseteq[d],\,|I|=i}}\prod_{j\in I}c_j.

Since Bk≥HkB_k \ge H_k by Theorem 1.2. For i=0i = 0, both sides of the asserted bound equal 1. For 1≤i≤d1 \le i \le d, equality forces B1=H1B_1 = H_1, because all summands above are nonnegative and (d−1i−1)>0\binom{d-1}{i-1} > 0. The equality argument in the proof of Theorem 1.2 then implies that GG is a cactus graph.

Conversely, for a cactus graph Theorem 1.2 gives Bk=HkB_k = H_k for every kk, so equality holds for every ii.

In particular, setting i=di = d and using Fd=τ(G)F_d = \tau(G) yields τ(G)≤∏j=1dcj\tau(G) \le\prod_{j=1}^{d} c_j. When d≥1d \ge1, apply the equality characterization for FiF_i above with i=di = d. When d=0d = 0, GG is a tree, τ(G)=1\tau(G) = 1, and the empty product is 11, so the conclusion also holds.

Conclusion

Using a quotient algebra representation associated with the cographic matroid, we establish upper bounds on the coefficients HiH_i of the all-terminal reliability polynomial in terms of the lengths of the cycles in an arbitrary binary cycle basis, thereby providing an affirmative answer to the aforementioned question for binary cycle bases. Through the coefficient transformation relating FiF_i and HiH_i, we further derive upper bounds on the numbers of deletable edge sets and spanning trees. We also prove that the upper bounds on HiH_i are attained simultaneously for all 0≤i≤d0 \le i \le d if and only if GG is a cactus graph. The bounds obtained in this paper depend only on the lengths of the cycles in a cycle basis. Several questions remain for further investigation. How can the number and distribution of edges shared by cycles in a cycle basis be used to obtain sharper upper bounds on the coefficients HiH_i? How can the lengths of the basis cycles and the cutset structure of the graph be used together to improve estimates for the numbers of deletable edge sets and spanning trees? When edges have different failure probabilities, how can the upper bounds on reliability obtained by the cycle-basis method be further sharpened?

Conflicts of Interest:

The authors declare that they have no conflicts of interest.

Data availability statement:

No data were used to support this study.

References

  1. [1]C.J. Colbourn, D.D. Harms, Bounding all-terminal reliability in computer networks, Networks 18 (1988) 1–12.DOI
  2. [2]C.J. Colbourn, Some open problems on reliability polynomials, Congr. Numer. 93 (1993) 187–202.
  3. [3]E. Bortoletto, N. Lindner, B. Masing, The tropical and zonotopal geometry of periodic timetables, Discrete Comput. Geom. 73 (2025) 719–763.
  4. [4]E. Noether, Abstrakter Aufbau der Idealtheorie in algebraischen Zahl- und Funktionenkörpern, Math. Ann. 96 (1927) 26–61.DOI
  5. [5]J.I. Brown, C.J. Colbourn, D.G. Wagner, Cohen–Macaulay rings in network reliability, SIAM J. Discrete Math. 9 (1996) 377–392.DOI
  6. [6]J.I. Brown, C.J. Colbourn, J.S. Devitt, Network transformations and bounding network reliability, Networks 23 (1993) 1–17.DOI
  7. [7]J.I. Brown, C.J. Colbourn, Non-Stanley bounds for network reliability, J. Algebraic Combin. 5 (1996) 13–36.DOI
  8. [8]J.I. Brown, C.J. Colbourn, R.J. Nowakowski, Chip firing and all-terminal network reliability bounds, Discrete Optim. 6 (2009) 436–445.DOI
  9. [9]J. Huh, h-Vectors of matroids and logarithmic concavity, Adv. Math. 270 (2015) 49–59.arxiv.org/abs/1201.2915
  10. [10]J. Oxley, Matroid Theory, second ed., Oxford Graduate Texts in Mathematics, vol. 21, Oxford University Press, Oxford, 2011.
  11. [11]M.O. Ball, J.S. Provan, Bounds on the reliability polynomial for shellable independence systems, SIAM J. Algebraic Discrete Methods 3 (1982) 166–181.DOI
  12. [12]M. van der Meulen, Reconfiguring Electricity Distribution Networks to Minimize Power Loss: NP-hardness and Efficient Approximation Algorithms, Master’s thesis, Radboud University, 2015.
  13. [13]N. Bourbaki, Algebra I: Chapters 1–3, Elements of Mathematics, Springer-Verlag, Berlin, 1989.
  14. [14]P. Romero, Universal reliability bounds for sparse networks, IEEE Trans. Reliab. 71 (2022) 359–369.DOI
  15. [15]S. Lang, Algebra, revised third ed., Graduate Texts in Mathematics, vol. 211, Springer-Verlag, New York, 2002.
  16. [16]T. Kavitha, C. Liebchen, K. Mehlhorn, D. Michail, R. Rizzi, T. Ueckerdt, K.A. Zweig, Cycle bases in graphs: Characterization, algorithms, complexity, and applications, Comput. Sci. Rev. 3 (2009) 199–243.DOI

Paper details

vlnc:W_kf2qj52z
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 11

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents