On the dependence of the existence of the positive steady states on the rate coefficients for deficiency-one mass action systems: single linkage class

Abstract

The Deficiency-One Theorem states that there exists a unique positive steady state in each positive stoichiometric class for weakly reversible deficiency-one mass action systems with one linkage class (regardless of the values of the rate coefficients). The non-emptiness of the set of positive steady states does not remain valid if we omit the weak reversibility. A recently published paper provided an equivalent condition to the existence of a positive steady state for deficiency-one mass action systems that are not weakly reversible, but still has only one linkage class. Based on that result, we characterise in this paper those of these mass action systems for which the non-emptiness of the set of positive steady states holds regardless of the values of the rate coefficients. Also, we provide an equivalent condition to the existence of rate coefficients such that the set of positive steady states is nonempty for the resulting mass action system.

1 Introduction

The foundations of chemical reaction network theory (CRNT) was developed by Feinberg, Horn, and Jackson [12–16, 20, 21] in the 1970s. Several results are available concerning the existence and/or the uniqueness of the positive steady states of mass action systems [1–4, 7–10, 14, 15]. A recent result provides an equivalent condition to the non-emptiness of the set of positive steady states for single linkage class deficiency-one mass action systems that are not weakly reversible, see [3, Theorem III.7] and [4, Theorems 3.11 and 3.19]. For such mass action systems, the non-emptiness of the set of positive steady states may depend on the values of the rate coefficients. In this paper, we characterise those of these chemical reaction networks, which has the property that the non-emptiness of the set of positive steady states does not depend on the values of the rate coefficients. The main graph theoretical tool we use is the Matrix-Tree Theorem, see [27, Theorem 3.6]. We remark that there are several recent papers in the field of CRNT that makes use of the Matrix-Tree Theorem, see e.g. [6, 11, 17, 18, 22, 26]. Finally, we mention here that a potential application of our results is to check the satisfaction of one of the assumptions of the main result of [25] (see the theorem at the bottom of page 1390 in [25]). A certain robustness property is proven there for deficiency-one mass action systems that are not weakly reversible, admit a positive steady state, and satisfy another (easily checkable) condition.

The rest of this paper is organised as follows. After a brief section on notations, we provide an overview of the required notations from CRNT in Sect. 3. The primary goal of this paper is to investigate the dependence of the non-emptiness of the set of positive steady states on the rate coefficients for deficiency-one mass action systems that are not weakly reversible, but still has only one linkage class. In Sect. 4, we examine this dependence under some extra assumptions on the graph of complexes (the directed graph that encodes the reactions). In Sect. 4.1, we assume that the reactions form a “chain”, while in Sect. 4.2, we pose the condition that the graph of complexes is “tree-like”. In Sects. 5 and 6, we generalise the results of Sect. 4 (i.e., in these sections we omit the restrictive assumptions on the structure of the graph of complexes that were posed in Sect. 4). As it will become apparent, especially in Sects. 4, 5 and 6, we need more involved graph theoretical arguments. Therefore, Appendices 7, 8, and 9 are devoted to summarise the purely graph theoretical notions and results that are used throughout this paper.

2 Notations

Denote by $\mathbb{R }, \mathbb{R }_+$, and $\mathbb{R }_{\ge 0}$ the set of real, positive real, and nonnegative real numbers, respectively, i.e., $\mathbb{R }_+=\{x\in \mathbb{R }~|~x>0\}$ and $\mathbb{R }_{\ge 0}=\{x\in \mathbb{R }~|~x\ge 0\}$. For $v\in \mathbb{R }^p$, the $i$th coordinate of $v$ is denoted by $v_i$ ($i \in \{1, \ldots , p\}$). For a matrix $A\in \mathbb{R }^{p\times q}$, the $j$th column and the $(i,j)$th entry of $A$ are denoted by $A_{\cdot j}$ and $A_{ij}$, respectively ($i \in \{1, \ldots , p\}, j \in \{1, \ldots , q\}$). For a matrix $A$, we denote by $A^{\top }, \ker A$, and $\mathrm{ran }A$ the transpose, the kernel, and the range of $A$, respectively. For a square matrix $A$, denote by $\det A$ the determinant of $A$.

For any finite set $X, X_0 \subseteq X$, and function $g : X \rightarrow \mathbb{R }$ we define $g(X_0)$ by

$$\begin{aligned} g(X_0) = \sum _{x \in X_0} g(x). \end{aligned}$$

(1)

We make this convention in order to ease the notation in several situations.

For any set $A$, denote the cardinality of $A$ by $|A|$.

We also summarise here the graph theoretical notations that will be used throughout this paper. For more details on these, please refer to Appendix 7. Let $D = (V, A)$ be a directed graph for the rest of this section. For $i, j \in V$, the set of directed paths from $i$ to $j$ is denoted by $\overrightarrow{i,j}$. For a directed path $P$ we denote by $V[P]$ the vertex set of $P$ (we use the notation $V[P]$ even if the vertex set of the directed graph in question is denoted by some other symbol than $V$) and by ${\mathrm{len}}(P)$ the length of $P$. For $i_1, i_2, i_3 \in V, P \in \overrightarrow{i_1, i_2}$, and $Q \in \overrightarrow{i_2, i_3}$, denote by $\mathrm{con }(P, Q)$ the concatenation of $P$ and $Q$.

For $U \subseteq V$ let us denote by ${\varrho }^{\mathrm{in }}_D(U)$ and ${\varrho }^{\mathrm{out }}_D(U)$ set of arcs that enter $U$ and leave $U$, respectively. For a function $z : A \rightarrow \mathbb{R }$, denote by $\hbox \mathrm{excess}_z$ the excess function associated to $D$ and $z$. For $i \in V$ we use the notations ${\varrho }^{\mathrm{in }}(i), {\varrho }^{\mathrm{out }}(i)$, and $\hbox \mathrm{excess}_z(i)$ instead of ${\varrho }^{\mathrm{in }}(\{i\}), {\varrho }^{\mathrm{out }}(\{i\})$, and $\hbox \mathrm{excess}_z(\{i\})$, respectively. For $U \subseteq V$, denote by $\mathcal{T }_D(U)$ the set of $U$-branchings in $D$. Finally, for $i, j \in V$ and $U \subseteq V$ let us define ${\mathcal{T }}^{ij}_D(U)$ by

$$\begin{aligned} \mathcal{T }^{ij}_{D}(U) = \{\widetilde{A} \in \mathcal{T }_{D}(U)\,|\, \hbox {there exists a directed path from} \,i\, \hbox {to} \,j \,\hbox {in} (V,\widetilde{A})\}. \end{aligned}$$

(2)

3 Preliminaries from CRNT

In this section we provide a brief overview of the basic notions of CRNT used in this paper. However, since the results of this paper rely heavily on the earlier result [4, Theorem 3.11], we assume some familiarity of the reader with these notions. Therefore, this section is rather a summary of the notions and notations used later on in this paper. The interested reader should consult e.g. [15, Sections 2 and 3] for a fuller discussion on these basic notions, while a short introduction can be found e.g. in [4, Section 2]. The latter reference uses almost the same notations as the present paper.

A chemical reaction network (or just reaction network) is a triple $(\mathcal{X },\mathcal{C },{\mathcal{R }})$ of three nonempty finite sets, where

• $\mathcal{X } = \{X_1, \ldots , X_n\}$ is the set of species,

• $\mathcal{C } = \{C_1, \ldots , C_c\}$ is the set of complexes, and

• ${\mathcal{R }} \subseteq \{ (C_i,C_j) \in \mathcal{C } \times \mathcal{C } ~|~ i, j \in \{1, \ldots , c\}, i \ne j \}$ is the set of reactions.

Roughly speaking, the complexes are linear combinations of the species with nonnegative integer coefficients. A convenient way to specify the set of complexes is to provide an $n \times c$ matrix, denoted by $B$, whose entries are nonnegative integers, the rows refer to the species, and the columns refer to the complexes. In order to ease the notation, we identify the sets $\mathcal{C }$ and $\{1, 2, \ldots , c\}$. Accordingly, we mostly write $i$ and $(i,j)$ instead of $C_i$ and $(C_i, C_j)$, respectively ($i, j \in \{1, 2, \ldots , c\}$).

The directed graph $(\mathcal{C },\mathcal{R })$ is called the graph of complexes. Certain properties of this directed graph will play a central role in this paper. For further reference, let us denote $(\mathcal{C },\mathcal{R })$ by the symbol $\mathcal{D }$.

A mass action system is a quadruple $(\mathcal{X }, \mathcal{C }, {\mathcal{R }}, \kappa )$, where $(\mathcal{X }, \mathcal{C }, {\mathcal{R }})$ is a chemical reaction network and $\kappa : {\mathcal{R }} \rightarrow \mathbb{R }_+$ is any function. For $(i,j) \in {\mathcal{R }}$, the value $\kappa _{(i,j)}$ is called the rate coefficient of the reaction $(i,j)$. In the sequel, we write $\kappa _{ij}$ instead of $\kappa _{(i,j)}$. We consider a continuous-time continuous-state deterministic model, where the state of the system represents the concentrations of the species and the time-evolution of the state is described by the ordinary differential equation

$$\begin{aligned} \dot{x}(\tau )=\sum _{(i,j)\in {\mathcal{R }}} \left( \kappa _{ij}\prod _{s=1}^n x_s(\tau ) ^{B_{si}}\right) \cdot (B_{\cdot j}-B_{\cdot i}) \end{aligned}$$

(3)

with state space $\mathbb{R }^n_{\ge 0}$. We will use another form of (3) in the sequel. For this aim, we next introduce the matrix $I_{\kappa } \in \mathbb{R }^{c\times c}$ and the function $\Theta : \mathbb{R }^n_{\ge 0}\rightarrow \mathbb{R }^c_{\ge 0}$. Let us extend the function $\kappa : {\mathcal{R }} \rightarrow \mathbb{R }_+$ to $\mathcal{C } \times \mathcal{C }$ such that $\kappa _{ij}=0$ for $(i,j)\in (\mathcal{C }\times \mathcal{C })\backslash {\mathcal{R }}$ (we do not make any distinction in notation between the original function and its extension). Define the matrix $I_{\kappa }\in \mathbb{R }^{c\times c}$ by

$$\begin{aligned} I_{\kappa }= \left[ \begin{array}{cccc} \kappa _{11}-\sum \nolimits _{i=1}^c \kappa _{1i} &{} \qquad \qquad \kappa _{21} &{} \cdots &{} \qquad \qquad \kappa _{c1} \\ \qquad \qquad \kappa _{12} &{} \kappa _{22}-\sum \nolimits _{i=1}^c \kappa _{2i} &{} \cdots &{} \qquad \qquad \kappa _{c2} \\ \qquad \qquad \vdots &{} \qquad \qquad \vdots &{} \ddots &{} \qquad \qquad \vdots \\ \qquad \qquad \kappa _{1c} &{} \qquad \qquad \kappa _{2c} &{} \cdots &{} \kappa _{cc}-\sum \nolimits _{i=1}^c \kappa _{ci} \end{array} \right] \in \mathbb{R }^{c\times c}\end{aligned}$$

(4)

and the function $\Theta : \mathbb{R }^n_{\ge 0}\rightarrow \mathbb{R }^c_{\ge 0}$ by

$$\begin{aligned} \Theta (x)= \left[ \begin{array}{c} \prod \nolimits _{s=1}^nx_s^{B_{s1}} \\ \prod \nolimits _{s=1}^nx_s^{B_{s2}} \\ \vdots \\ \prod \nolimits _{s=1}^nx_s^{B_{sc}} \end{array} \right] ~~(x\in \mathbb{R }^n_{\ge 0}). \end{aligned}$$

Note that both the rows and the columns of $I_{\kappa }$ and the coordinate functions of $\Theta$ correspond to the vertices of the directed graph $(\mathcal{C },\mathcal{R })$, i.e., to the complexes. With these notations, (3) can be written equivalently as

$$\begin{aligned} \dot{x}(\tau ) = B \cdot I_{\kappa } \cdot \Theta (x(\tau )). \end{aligned}$$

The main object we are interested in in this paper is the set of positive steady states of a mass action system, denoted by $E^{\kappa }_+$. Let us define $E^{\kappa }_+$ by

$$\begin{aligned} E^{\kappa }_+ = \{ x \in \mathbb{R }^n_+~|~ B \cdot I_{\kappa } \cdot \Theta (x)=0 \}. \end{aligned}$$

We have included the symbol $\kappa$ in the notation $E^{\kappa }_+$, because our primary goal in this paper is to investigate the dependence of the non-emptiness of the set of positive steady states on the rate coefficients.

We use the usual terminology of the theory of directed graphs in the sequel. We have also collected the required ones in Appendix 7. Denote by $\ell$ the number of weak components of the directed graph $(\mathcal{C },\mathcal{R })$. The weak components of $(\mathcal{C },\mathcal{R })$ are called linkage classes in CRNT. In case all the linkage classes of $(\mathcal{C },\mathcal{R })$ are strongly connected, the network is called weakly reversible in CRNT. Denote by $t$ the number of absorbing strong components of the directed graph $(\mathcal{C },\mathcal{R })$. Since each weak component contains at least one absorbing strong component, we have $\ell \le t$.

A useful fact is that if $\ell = t$ then $\mathrm{ran }I_{\kappa }$ does not depend on $\kappa$ (see e.g. [4, Corollary 2.6]). Based on this, we define the deficiency, denoted by $\delta$, of a reaction network of the type $\ell = t$ by $\delta = \dim (\ker B \cap \mathrm{ran }I_{\kappa })$.

The following theorem is a classical result in CRNT, it is called the Deficiency-Zero Theorem, see e.g. [14, Theorem 6.1.1].

Theorem 3.1

Let $(\mathcal{X }, \mathcal{C }, {\mathcal{R }})$ be a chemical reaction network with $\ell = t = 1$ and $\delta = 0$. Then the following statements hold.

• (a) If $(\mathcal{C }, {\mathcal{R }})$ is strongly connected then for all $\kappa : {\mathcal{R }} \rightarrow \mathbb{R }_+$ we have $E^{\kappa }_+ \ne \emptyset$.

• (b) If $(\mathcal{C }, {\mathcal{R }})$ is not strongly connected then for all $\kappa : {\mathcal{R }} \rightarrow \mathbb{R }_+$ we have $E^{\kappa }_+ = \emptyset$.

The also classical Deficiency-One Theorem has been augmented recently, see [14, Theorem 6.2.1] and [4, Theorem 3.19]. To state the theorem, we need some further notations, which will then be used throughout this paper. For a chemical reaction network with $\ell =t=1$, denote by $\mathcal{C }^{\prime }$ the set of complexes, which are in the terminal strong linkage class of $(\mathcal{C },{\mathcal{R }})$ and let $\mathcal{C }^{\prime \prime }=\mathcal{C }\backslash \mathcal{C }^{\prime }$. Let $c^{\prime }=|\mathcal{C }^{\prime }|$ and $c^{\prime \prime }=|\mathcal{C }^{\prime \prime }|$ (thus, $c^{\prime \prime } = c - c^{\prime }$). With this, $I_{\kappa } \in \mathbb{R }^{c\times c}, \Theta : \mathbb{R }^n\rightarrow \mathbb{R }^c$, and any vector $v \in \mathbb{R }^c$ can be considered the block forms

$$\begin{aligned}&I_{\kappa }=\left[ \begin{array}{c@{\quad }c} I^{\prime }_{\kappa } &{} * \\ 0&{} I^{\prime \prime }_{\kappa } \\ \end{array} \right] \in \mathbb{R }^{(c^{\prime } + c^{\prime \prime }) \times (c^{\prime } + c^{\prime \prime })},~~ \Theta = \left[ \begin{array}{c} \Theta ^{\prime } \\ \Theta ^{\prime \prime } \end{array}\right] :\mathbb{R }^n\rightarrow \mathbb{R }^{c^{\prime }+c^{\prime \prime }},~~\hbox {and}\\&v= \left[ \begin{array}{c} v^{\prime } \\ v^{\prime \prime } \end{array}\right] \in \mathbb{R }^{c^{\prime }+c^{\prime \prime }}, \end{aligned}$$

where $I^{\prime }_{\kappa } \in \mathbb{R }^{c^{\prime } \times c^{\prime }}, \Theta ^{\prime }:\mathbb{R }^n\rightarrow \mathbb{R }^{c^{\prime }}$, and $v^{\prime }\in \mathbb{R }^{c^{\prime }}$ correspond to the complexes in $\mathcal{C }^{\prime }$, while $I^{\prime \prime }_{\kappa } \in \mathbb{R }^{c^{\prime \prime } \times c^{\prime \prime }}, \Theta ^{\prime \prime }:\mathbb{R }^n\rightarrow \mathbb{R }^{c^{\prime \prime }}$, and $v^{\prime \prime }\in \mathbb{R }^{c^{\prime \prime }}$ correspond to the complexes in $\mathcal{C }^{\prime \prime }$. There are several ways to prove that $I_{\kappa }^{\prime \prime }$ is invertible (provided that $\mathcal{C }^{\prime \prime } \ne \emptyset$), see e.g. [4, Lemma 2.5].

Primarily, we are interested in this paper in mass action systems for which $\ell = t = 1$ and $\delta = 1$ hold. For such systems, the linear subspace $\ker B \cap \mathrm{ran }I_{\kappa }$ is one-dimensional and does not depend on $\kappa$ (recall that for systems with $\ell = t$ we have $\delta = \dim (\ker B \cap \mathrm{ran }I_{\kappa })$). For systems that are moreover not weakly reversible, let us fix $h \in \mathbb{R }^c$ such that

$$\begin{aligned} 0\ne h \in \ker B \cap \mathrm{ran }I_{\kappa } ~ \hbox {and} ~ h(\mathcal{C }^{\prime \prime }) \le 0, \end{aligned}$$

(5)

where the notation $h(\mathcal{C }^{\prime \prime })$ is understood in accordance with (1), i.e., the sum of certain coordinates of $h$ is non-positive, where the summation goes for those complexes that are out of the absorbing strong component of $(\mathcal{C }, {\mathcal{R }})$.

With these notations in hand, we are ready to state the Deficiency-One Theorem in its augmented form (see [3, Theorem III.7] and [4, Theorems 3.11 and 3.19]).

Theorem 3.2

Let $(\mathcal{X }, \mathcal{C }, {\mathcal{R }})$ be a chemical reaction network with $\ell = t = 1$ and $\delta = 1$. Then the following statements hold.

• (a) If $(\mathcal{C }, {\mathcal{R }})$ is strongly connected then for all $\kappa : {\mathcal{R }} \rightarrow \mathbb{R }_+$ we have $E^{\kappa }_+ \ne \emptyset$.

• (b) Assume that $(\mathcal{C }, {\mathcal{R }})$ is not strongly connected. Let $h \in \mathbb{R }^c$ be as in (5) and fix $\kappa : {\mathcal{R }} \rightarrow \mathbb{R }_+$. Then

  $$\begin{aligned} E^{\kappa }_+ \ne \emptyset ~ \hbox {if and only if all the coordinates of} ~ (I_{\kappa }^{\prime \prime })^{-1}h^{\prime \prime } ~ \hbox {are positive}. \end{aligned}$$

Seemingly, there is some freedom in the choice of $h$ (it is chosen from a one-dimensional linear subspace of $\mathbb{R }^c$). On the one hand, if $h(\mathcal{C }^{\prime \prime }) < 0$ then $h$ is determined up to a positive scalar multiplier. However, it is clear that the choice of this positive scalar multiplier does not affect the condition $(I_{\kappa }^{\prime \prime })^{-1}h^{\prime \prime } \in \mathbb{R }_+^{c^{\prime \prime }}$. On the other hand, if $h(\mathcal{C }^{\prime \prime }) = 0$ then $h$ is determined up to a nonzero scalar multiplier. However, it is easy to see that $(I_{\kappa }^{\prime \prime })^{-1}h^{\prime \prime } \in \mathbb{R }_+^{c^{\prime \prime }}$ implies $h(\mathcal{C }^{\prime \prime }) < 0$ (indeed, let $\vartheta ^{\prime \prime } = (I_{\kappa }^{\prime \prime })^{-1}h^{\prime \prime }$ and take the sum of the coordinates on both sides of $I_{\kappa }^{\prime \prime }\vartheta ^{\prime \prime } = h^{\prime \prime }$). Thus, again, this nonzero scalar multiplier does not affect the condition $(I_{\kappa }^{\prime \prime })^{-1}h^{\prime \prime } \in \mathbb{R }_+^{c^{\prime \prime }}$.

As a side remark, we also mention that both in Theorems 3.1 and 3.2, once $E^{\kappa }_+ \ne$ holds, there is exactly one positive steady state in each positive stoichiometric class.

Thus, if the reaction network satisfies $\ell = t = 1$ and $\delta = 0$ then the non-emptiness of $E^{\kappa }_+$ does not depend on $\kappa$. Also, if the reaction network satisfies $\ell = t = 1$ and $\delta = 1$, and moreover $(\mathcal{C }, {\mathcal{R }})$ is strongly connected then, again, the non-emptiness of $E^{\kappa }_+$ does not depend on $\kappa$. However, by Theorem 3.2 $(b)$, we have a different situation for mass action systems for which the underlying reaction network satisfies $\ell = t = 1$ and $\delta = 1$, but $(\mathcal{C }, {\mathcal{R }})$ is not strongly connected. For these mass action systems, the non-emptiness of $E^{\kappa }_+$ may depends on $\kappa$. We used the word “ may”, because for such mass action systems three different kind of phenomena can occur:

• $E^{\kappa }_+ \ne \emptyset$ for all $\kappa$ (i.e., for all $\kappa$ all the coordinates of $(I_{\kappa }^{\prime \prime })^{-1}h^{\prime \prime }$ are positive),

• $E^{\kappa }_+ = \emptyset$ for all $\kappa$ (i.e., for all $\kappa$ there exists a non-positive coordinate of $(I_{\kappa }^{\prime \prime })^{-1}h^{\prime \prime }$), and

• the non-emptiness of $E^{\kappa }_+$ depends on $\kappa$ (i.e., there exists $\kappa$ such that all the coordinates of $(I_{\kappa }^{\prime \prime })^{-1}h^{\prime \prime }$ are positive and there also exists $\kappa$ such that there exists a non-positive coordinate of $(I_{\kappa }^{\prime \prime })^{-1}h^{\prime \prime }$).

It is demonstrated in [4, Analysis of Examples 3.7, 3.8, and 3.9] that all of these three phenomena can indeed occur. The aim of the present paper is to provide characterisations of the above cases. Namely, we will formulate equivalent conditions to the statements

(6)

(7)

In Sect. 4 we examine the above questions under some extra assumptions on $(\mathcal{C },{\mathcal{R }})$. In Sect. 4.1 we will assume that $(\mathcal{C },{\mathcal{R }})$ is a “chain”. As a generalisation of the results of Sect. 4.1, we will assume in Sect. 4.2 that $(\mathcal{C },{\mathcal{R }})$ is “tree-like”. As a matter of fact, we will obtain a recursive formula for the coordinates of $(I_{\kappa }^{\prime \prime })^{-1}h^{\prime \prime }$ (the matrix $I_{\kappa }^{\prime \prime }$ has some special properties in these cases, which makes it possible to handle the computation of its inverse). Based on the obtained recursive formula, we will deduce equivalent conditions both for (6) and (7). In Sects. 5 and 6 we will assume only that $(\mathcal{C }, {\mathcal{R }})$ satisfies $\ell = t = 1$, but is not strongly connected. Under this assumption, we provide equivalent conditions to (6) and (7) for these general cases in Sects. 5 and 6, respectively.

4 Special cases

We always assume in the rest of this paper that the reaction network under consideration satisfies $\ell = t = 1$ and $\delta = 1$, but is not strongly connected. Thus, $\mathcal{C }^{\prime \prime } \ne \emptyset$. Since we will apply Theorem 3.2 $(b)$, we fix $h \in \mathbb{R }^c$ as in (5) (recall that $\ell = t$ implies that $\mathrm{ran }I_{\kappa }$ does not depend on $\kappa$, and hence, $h$ is not influenced by $\kappa$). Also, let $\vartheta \in \mathbb{R }^c$ be such that

$$\begin{aligned} I_{\kappa } \vartheta = h. \end{aligned}$$

(8)

Thus, $\vartheta$ depends on $\kappa$. Since $I_{\kappa }$ is block upper triangular, we obtain that $I^{\prime \prime }_{\kappa } \vartheta ^{\prime \prime } = h^{\prime \prime }$. Thus, $\vartheta ^{\prime \prime } = (I_{\kappa }^{\prime \prime })^{-1}h^{\prime \prime }$. By Theorem 3.2 $(b)$, we have

$$\begin{aligned} E^{\kappa }_+ \ne \emptyset \ \hbox {if and only if} \ \vartheta ^{\prime \prime } \in \mathbb{R }_+^{c^{\prime \prime }}. \end{aligned}$$

(9)

Thus, our aim in this section is to obtain a formula for the coordinates of $\vartheta ^{\prime \prime }$.

We formulate a purely graph theoretical lemma, which will be useful in Sects. 4.1 and 4.2. The required graph theoretical notions can be found in Appendix 7.

Lemma 4.1

Let $(V,A)$ be a directed graph and let $\vartheta : V \rightarrow \mathbb{R }$ be any function. Let $\kappa : V \times V \rightarrow \mathbb{R }_{\ge 0}$ be a function for which $\kappa _{ij}>0$ if and only if $(i,j)\in A$. Define $z : A \rightarrow \mathbb{R }$ by $z_{ij}=\kappa _{ij}\vartheta _i$ $((i,j)\in A)$, let $I_\kappa$ be as in (4), and let $h = I_{\kappa }\vartheta$. Then

$$\begin{aligned} \hbox \mathrm{excess}_z(U)=\sum _{j \in U} h_j ~ \hbox {for all} ~ U \subseteq V. \end{aligned}$$

Proof

Fix $j \in V$. Then, by the definitions of the matrix $I_{\kappa }$ and the $\hbox \mathrm{excess}$ function we obtain

$$\begin{aligned} h_j \!= \!\sum _{i \in V} (I_{\kappa })_{ji} \vartheta _i \!=\! \sum _{i \in V \backslash \{j\}} \kappa _{ij}\vartheta _i \!- \!\sum _{i \in V \backslash \{j\}} \kappa _{ji}\vartheta _j \!=\! z(\varrho ^{\mathrm{in }}(j)) \!-\! z(\varrho ^{\mathrm{out }}(j)) \!=\! \hbox \mathrm{excess}_z(j). \end{aligned}$$

With this, the statement of the lemma follows from (55).$\square$

4.1 The case $(\mathcal{C }, {\mathcal{R }})$ is a “chain”

The $(\mathcal{C },\mathcal{R })$) takes the special form

(10)

where we also indicated the rate coefficients. Note that in this case $\mathcal{C }^{\prime } = \{C_1\}$ and $\mathcal{C }^{\prime \prime } = \{C_2,\ldots ,C_c\}$, while the matrix $I_{\kappa }^{\prime \prime }$ is tridiagonal and moreover

$$\begin{aligned} \hbox {the column sums of } I_{\kappa }^{\prime \prime } \hbox { are zero except the one corresponding to } C_2. \end{aligned}$$

(11)

Clearly, (11) is a consequence of the fact that leaving the set $\mathcal{C }^{\prime \prime }$ is only possible through $C_2$ (i.e., using the notations introduced in Appendix 7, $\emptyset \ne \varrho ^{\mathrm{out }}(\mathcal{C }^{\prime \prime }) \subseteq \varrho ^{\mathrm{out }}(C_2)$). Proposition 4.2 below provides a recursive formula for the coordinates of $\vartheta ^{\prime \prime }$.

Proposition 4.2

Let $(\mathcal{X },\mathcal C ,{\mathcal{R }},\kappa )$ be a deficiency-one mass action system for which $(\mathcal{C },\mathcal{R })$ takes the form (10). Let $h$ and $\vartheta$ be as in (5) and (8), respectively. Then

$$\begin{aligned} \vartheta _2&= -\frac{1}{\kappa _{21}}\sum _{i=2}^c h_i ~ \hbox {and}\end{aligned}$$

(12)

$$\begin{aligned} \vartheta _j&= \frac{\kappa _{j-1,j}}{\kappa _{j,j-1}}\vartheta _{j-1} - \frac{1}{\kappa _{j,j-1}}\sum _{i=j}^c h_i~~(j=3,\ldots ,c). \end{aligned}$$

(13)

Proof

Application of Lemma 4.1 with $U = \mathcal{C }^{\prime \prime }$ yields $-\kappa _{21}\vartheta _2 = \sum _{i=2}^c h_i$. This proves (12).

Fix $j \in \{3, \ldots , c\}$. Application of Lemma 4.1 with $U=\{C_j,\ldots ,C_c\}$ yields

$$\begin{aligned} \kappa _{j-1,j}\vartheta _{j-1} - \kappa _{j,j-1}\vartheta _j = \sum _{i=j}^c h_i. \end{aligned}$$

This proves (13).$\square$

As a corollary of Proposition 4.2, we obtain directly a characterisation of those reaction networks in Proposition 4.2 for which there exist rate coefficients such that the resulting mass action system has a positive steady state. Similarly, a characterisation is given for those networks for which the resulting mass action system has a positive steady state regardless of the values of the rate coefficients.

Corollary 4.3

Let $(\mathcal{X },\mathcal{C },{\mathcal{R }})$ be a deficiency-one reaction network for which $(\mathcal{C },{\mathcal{R }})$ takes the form (10). Let $h \in \mathbb{R }^c$ be as in (5). Then there exists $\kappa :{\mathcal{R }}\rightarrow \mathbb{R }_+$ such that $E^{\kappa }_+\ne \emptyset$ if and only if

$$\begin{aligned} \sum _{i=2}^c h_i<0. \end{aligned}$$

Proof

The statement follows directly from (9) and Proposition 4.2.$\square$

Corollary 4.4

Let $(\mathcal{X },\mathcal C ,{\mathcal{R }})$ be a deficiency-one reaction network for which $(\mathcal{C },\mathcal{R })$ takes the form (10). Let $h \in \mathbb{R }^c$ be as in (5). Then for all $\kappa :{\mathcal{R }}\rightarrow \mathbb{R }_+$ we have $E^{\kappa }_+\ne \emptyset$ if and only if

$$\begin{aligned} \begin{aligned}&\sum _{i=2}^c h_i<0 ~ \hbox {and} \\&\sum _{i=j}^c h_i \le 0 ~ \hbox {for all} ~ j \in \{3, \ldots , c\}. \end{aligned} \end{aligned}$$

Proof

The statement follows directly from (9) and Proposition 4.2.$\square$

4.2 The case $(\mathcal{C }, {\mathcal{R }})$ is “tree-like”

In this subsection, we generalise the results obtained in Sect. 4.1. We will not pose in this subsection the condition that the graph of complexes $(\mathcal{C },{\mathcal{R }})$ takes the form (10), rather we assume that $(\mathcal{C },{\mathcal{R }})$ satisfies

$$\begin{aligned}&\ell =t=1 \hbox { and} \,(\mathcal{C },{\mathcal{R }}) \, \hbox {is not strongly connected},\end{aligned}$$

(14)

$$\begin{aligned}&\hbox {there exists a unique}\,l\in \mathcal{C }^{\prime \prime }\,\hbox {such that}\,\varrho ^{\mathrm{out }}(l)\cap \varrho ^{\mathrm{out }}(\mathcal{C }^{\prime \prime })\ne \emptyset ,\,\hbox {and}\end{aligned}$$

(15)

$$\begin{aligned}&\hbox {for all } i\in \mathcal{C }^{\prime \prime } \hbox {there exists a unique directed path from}\,i\,\hbox {to}\,l. \end{aligned}$$

(16)

Thus, by (15), we have $\emptyset \ne \varrho ^{\mathrm{out }}(\mathcal{C }^{\prime \prime }) \subseteq \varrho ^{\mathrm{out }}(l)$. Consider that the graph of complexes $(\mathcal{C },{\mathcal{R }})$ takes the form

(17)

Note that $\mathcal{C }^{\prime } = \{C_1,\ldots ,C_6\}$ and $\mathcal{C }^{\prime \prime } = \{C_7, \ldots , C_{22} \}$ for (17). Also, (17) satisfies (14), (15), and (16) with $l = C_7$.

Clearly, the graph in (10) satisfies (14), (15), and (16) with $l = C_2$. Thus, the results of this subsection are indeed generalisations of the results of Sect. 4.1.

For $j\in \mathcal{C }^{\prime \prime }$ denote by $P_j$ the unique directed path from $j$ to $l$ and for $i \in \mathcal{C }^{\prime \prime }$ define $U(i) \subseteq \mathcal{C }^{\prime \prime }$, called the set of descendants of $i$, by

$$\begin{aligned} U(i) = \{j \in \mathcal{C }^{\prime \prime } ~|~ i \in V[P_j] \}, \end{aligned}$$

i.e., we collect those vertices for which the unique directed path to $l$ traverses $i$. Also, for $j \in \mathcal{C }^{\prime \prime } \backslash \{l\}$ define $p(j) \in V[P_j]$, called the parent of $j$, by the implicit definition

$$\begin{aligned} {\mathrm{len}}(P_{p(j)}) = {\mathrm{len}}(P_j) - 1, \end{aligned}$$

i.e., the parent of $j$ is the second vertex on the unique directed path from $j$ to $l$. For example, for (17) we have $p(C_{20}) = C_{14}$ and $U(C_{20}) = \{C_{20},C_{21},C_{22}\}$.

We are now ready to state and prove the generalisation of Proposition 4.2.

Proposition 4.5

Let $(\mathcal{X },\mathcal{C },{\mathcal{R }},\kappa )$ be a deficiency-one mass action system for which $(\mathcal{C },{\mathcal{R }})$ satisfies (14), (15), and (16). Let $h$ and $\vartheta$ be as in (5) and (8), respectively. Then

$$\begin{aligned} \vartheta _l&= -\frac{1}{\sum _{l^{\prime }\in \mathcal{C }^{\prime }}\kappa _{l,l^{\prime }}}\sum _{i\in \mathcal{C }^{\prime \prime }} h_i,\end{aligned}$$

(18)

$$\begin{aligned} \vartheta _j&= \frac{\kappa _{p(j),j}}{\kappa _{j,p(j)}}\vartheta _{p(j)} - \frac{1}{\kappa _{j,p(j)}}\sum _{i\in U(j)} h_i~~(j\in \mathcal{C }^{\prime \prime }\backslash \{l\}). \end{aligned}$$

(19)

Proof

Application of Lemma 4.1 with $U = \mathcal{C }^{\prime \prime }$ yields $-\sum _{l^{\prime }\in \mathcal{C }^{\prime }}\kappa _{l,l^{\prime }}\vartheta _l = \sum _{i \in \mathcal{C }^{\prime \prime }} h_i$. This proves (18).

Fix $j \in \mathcal{C }^{\prime \prime } \backslash \{l\}$. Application of Lemma 4.1 with $U=U(j)$ yields

$$\begin{aligned} \kappa _{p(j),j}\vartheta _{p(j)} - \kappa _{j,p(j)}\vartheta _j = \sum _{i \in U(j)} h_i. \end{aligned}$$

This proves (19).$\square$

As consequences of Proposition 4.5, we obtain directly the generalisations of Corollaries 4.3 and 4.4.

Corollary 4.6

Let $(\mathcal{X },\mathcal{C },{\mathcal{R }})$ be a deficiency-one reaction network for which $(\mathcal{C },{\mathcal{R }})$ satisfies (14), (15), and (16). Let $h \in \mathbb{R }^c$ be as in (5). Then there exists $\kappa :{\mathcal{R }}\rightarrow \mathbb{R }_+$ such that $E^{\kappa }_+\ne \emptyset$ if and only if

$$\begin{aligned}&\sum _{i\in \mathcal{C }^{\prime \prime }} h_i < 0~\hbox {and} \\&\sum _{i\in U(j)} h_i < 0~\hbox {for all}~j\in \mathcal{C }^{\prime \prime }\backslash \{l\}~\hbox {that satisfies}~\kappa _{p(j),j}=0. \end{aligned}$$

Proof

The statement follows directly from (9) and Proposition 4.5.$\square$

Corollary 4.7

Let $(\mathcal{X },\mathcal{C },{\mathcal{R }})$ be a deficiency-one reaction network for which $(\mathcal{C },{\mathcal{R }})$ satisfies (14), (15), and (16). Let $h \in \mathbb{R }^c$ be as in (5). Then for all $\kappa :{\mathcal{R }}\rightarrow \mathbb{R }_+$ we have $E^{\kappa }_+\ne \emptyset$ if and only if

$$\begin{aligned}&\sum _{i\in \mathcal{C }^{\prime \prime }} h_i<0, \\&\sum _{i\in U(j)} h_i < 0~\hbox {for all}\,j\in \mathcal{C }^{\prime \prime }\backslash \{l\}~\hbox {that satisfies}\,\kappa _{p(j),j}=0,~\hbox {and} \\&\sum _{i\in U(j)} h_i \le 0~\hbox {for all}\,j\in \mathcal{C }^{\prime \prime }\backslash \{l\}~\hbox {that satisfies}~\kappa _{p(j),j}>0. \end{aligned}$$

Proof

The statement follows directly from (9) and Proposition 4.5.$\square$

Note that for (17) we have

$$\begin{aligned} \kappa _{p(j),j}&= 0 \quad \hbox {for} \, j \in \{C_8, C_{10}, C_{11}, C_{12}, C_{14}, C_{15}, C_{18}, C_{19}, C_{20}, C_{21}\} \, \hbox {and} \\ \kappa _{p(j),j}&> 0 \quad \hbox {for} \, j \in \{C_9, C_{13}, C_{16}, C_{17}, C_{22}\}. \end{aligned}$$

Thus, application of Corollary 4.6 yields for (17) that there exists $\kappa : {\mathcal{R }} \rightarrow \mathbb{R }_+$ such that $E_+^{\kappa } \ne \emptyset$ if and only if

$$\begin{aligned}&h_7 \!+\! \cdots + h_{22} < 0, h_8 \!+\! \cdots \!+\! h_{11} < 0, h_{10} \!<\! 0, h_{11} < 0, h_{12} < 0, h_{14} + \cdots + h_{22} < 0, \nonumber \\&h_{15} + \cdots \!+\! h_{19} < 0, h_{18} < 0, h_{19} \!<\! 0, h_{20} \!+\! h_{21} \!+\! h_{22} \!<\! 0, ~\hbox {and}~ h_{21} \!<\! 0. \end{aligned}$$

(20)

Similarly, application of Corollary 4.7 yields for (17) that for all $\kappa : {\mathcal{R }} \rightarrow \mathbb{R }_+$ we have $E_+^{\kappa } \ne \emptyset$ if and only if

$$\begin{aligned}&(20)~\hbox {holds and moreover} \\&h_9 + h_{10} \le 0, h_{13} + \cdots + h_{22} \le 0, h_{16} + \cdots + h_{19} \le 0, h_{17} \le 0, h_{22} \le 0. \end{aligned}$$

5 The existence of rate coefficients such that the set of positive steady states is nonempty

In this section we generalise Corollary 4.6. We will assume only that the reaction network under consideration is of deficiency-one and satisfies (14). The main tool we use is the following purely graph theoretical theorem. We provide its proof in Appendix 8. The graph theoretical notions and notations required to understand the statement of Theorem 5.1 are summarized in Appendix 7.

Theorem 5.1

Let $(V,A)$ be a weakly connected directed graph and let $h : V \rightarrow \mathbb{R }$ be a function with $h(V) = 0$. Then there exists a function $z : A \rightarrow \mathbb{R }_+$ such that $\hbox \mathrm{excess}_z = h$ if and only if

$$\begin{aligned} h(U) < 0 \, \hbox {for all} \, \emptyset \ne U \subsetneq V \, \hbox {with} \, \varrho ^{\mathrm{in }}(U) = \emptyset . \end{aligned}$$

(21)

As a corollary of Theorem 5.1, we obtain the generalisation of Corollary 4.6.

Corollary 5.2

Let $(\mathcal{X },\mathcal C ,{\mathcal{R }})$ be a reaction network for which $\ell = t = 1$ and $\delta = 1$. Assume that $(\mathcal{C },\mathcal{R })$ is not strongly connected and let $h \in \mathbb{R }^c$ be as in (5). Then there exists $\kappa : {\mathcal{R }} \rightarrow \mathbb{R }_+$ such that $E_+^{\kappa } \ne \emptyset$ if and only if

$$\begin{aligned} h(\widetilde{\mathcal{C }}) < 0 \hbox { for all } \emptyset \ne \widetilde{\mathcal{C }} \subsetneq \mathcal{C } \hbox { such that } \varrho ^{\mathrm{in }}\,(\widetilde{\mathcal{C }})=\emptyset . \end{aligned}$$

(22)

Proof

To prove that (22) is necessary, let $\kappa : {\mathcal{R }} \rightarrow \mathbb{R }_+$ be such that $E_+^{\kappa } \ne \emptyset$. Then, by Theorem 3.2 $(b)$, we have $(I_{\kappa }^{\prime \prime })^{-1}h^{\prime \prime } \in \mathbb{R }_+^{c^{\prime \prime }}$. Let $\vartheta \in \mathbb{R }^c$ be such that $I_{\kappa } \vartheta = h$ and define $z : {\mathcal{R }} \rightarrow \mathbb{R }$ by $z_{ij} = \kappa _{ij} \vartheta _i$. Since $\vartheta ^{\prime \prime } = (I_{\kappa }^{\prime \prime })^{-1}h^{\prime \prime }$, we have $\vartheta ^{\prime \prime }_i > 0$ for all $i \in \mathcal{C }^{\prime \prime }$. Also, let $\emptyset \ne \widetilde{\mathcal{C }} \subsetneq \mathcal{C }$ be such that $\varrho ^{\mathrm{in }}(\widetilde{\mathcal{C }})=\emptyset$. Then clearly $\widetilde{\mathcal{C }} \subseteq \mathcal{C }^{\prime \prime }$ and $\varrho ^{\mathrm{out }}(\widetilde{\mathcal{C }}) \ne \emptyset$. Thus, by Lemma 4.1, we have

$$\begin{aligned} h(\widetilde{\mathcal{C }}) = \hbox \mathrm{excess}_z (\widetilde{\mathcal{C }}) = - z(\varrho ^{\mathrm{out }}(\widetilde{\mathcal{C }})) = - \sum _{(i,j) \in \varrho ^{\mathrm{out }}(\widetilde{\mathcal{C }})} \kappa _{ij} \vartheta _i < 0. \end{aligned}$$

To prove the sufficiency of (22), let $\kappa : {\mathcal{R }} \rightarrow \mathbb{R }_+$ be such that $\hbox \mathrm{excess}_{\kappa } = h$ (see Theorem 5.1). Also, define $\vartheta \in \mathbb{R }^c$ by $\vartheta _i = 1$ $(i \in \mathcal{C })$. Then clearly $I_{\kappa } \vartheta = h$ (recall (4)). Thus, $(I_{\kappa }^{\prime \prime })^{-1}h^{\prime \prime } = \vartheta ^{\prime \prime } \in \mathbb{R }_+^{c^{\prime \prime }}$ and therefore Theorem 3.2 $(b)$ concludes the proof.$\square$

Consider that the graph of complexes takes the form

(23)

Application of Corollary 5.2 to a reaction network for which the graph of complexes is (23) yields that there exists $\kappa : {\mathcal{R }} \rightarrow \mathbb{R }_+$ such that $E_+^{\kappa } \ne \emptyset$ if and only if

$$\begin{aligned}&h_5 + h_6 + h_7 < 0, h_7 < 0, h_7 + h_8 < 0, h_7 + h_8 + h_9 < 0,\\&h_5 + h_6 + h_7 + h_8 < 0, ~ \hbox {and} ~ h_5 + h_6 + h_7 + h_8 + h_9 <0. \end{aligned}$$

By Corollary 5.2, the sets of interest are $\emptyset \ne \widetilde{\mathcal{C }} \subsetneq \mathcal{C }$ for which $\varrho ^{\mathrm{in }}(\widetilde{\mathcal{C }})=\emptyset$. Therefore, we conclude this section by some comments on these sets (see Proposition 5.3 and Corollary 5.4 below). To this end, let us define for $i \in \mathcal{C }^{\prime \prime }$ the set $R(i) \subseteq \mathcal{C }^{\prime \prime }$ by

$$\begin{aligned} R(i) = \{j \in \mathcal{C }^{\prime \prime } \,|\, \hbox {there exists a directed path from} \,j \,\hbox {to} \,i\}. \end{aligned}$$

(24)

Proposition 5.3

Assume that $(\mathcal{C }, {\mathcal{R }})$ satisfies (14) and for $i \in \mathcal{C }^{\prime \prime }$ let $R(i)$ be as in (24). Then

• (a) for all $i \in \mathcal{C }^{\prime \prime }$ we have $i \in R(i)$,

• (b) for all $i \in \mathcal{C }^{\prime \prime }$ the set $R(i)$ is the disjoint union of some strong linkage classes,

• (c) if $i_1 \in \mathcal{C }^{\prime \prime }$ and $i_2 \in \mathcal{C }^{\prime \prime }$ are in the same strong linkage class then $R(i_1) = R(i_2)$,

• (d) for all $i \in \mathcal{C }^{\prime \prime }$ we have $\emptyset \ne R(i) \subsetneq \mathcal{C }$ and $\varrho ^{\mathrm{in }}(R(i))=\emptyset$,

• (e) if $\emptyset \ne \widetilde{\mathcal{C }} \subsetneq \mathcal{C }$ is such that $\varrho ^{\mathrm{in }}(\widetilde{\mathcal{C }})=\emptyset$ and $i \in \widetilde{\mathcal{C }}$ then $R(i) \subseteq \widetilde{\mathcal{C }}$, and

• (f) for all $i_1, i_2 \in \mathcal{C }^{\prime \prime }$ we have $\emptyset \ne R(i_1) \cup R(i_2) \subsetneq \mathcal{C }$ and $\varrho ^{\mathrm{in }}(R(i_1) \cup R(i_2))=\emptyset$.

Proof

All the statements are trivial.$\square$

Corollary 5.4

Assume that $(\mathcal{C }, {\mathcal{R }})$ satisfies (14) and for $i \in \mathcal{C }^{\prime \prime }$ let $R(i)$ be as in (24). Let $\emptyset \ne \widetilde{\mathcal{C }} \subsetneq \mathcal{C }$ be such that $\varrho ^{\mathrm{in }}(\widetilde{\mathcal{C }})=\emptyset$. Then there exists $J \subseteq \mathcal{C }^{\prime \prime }$ such that $\widetilde{\mathcal{C }} = \cup _{i \in J} R(i)$.

Proof

The statement follows directly from Proposition 5.3 $(a)$ and $(e)$.$\square$

For (23) we have

$$\begin{aligned} R(5) = R(6) = \{5, 6, 7\}, R(7) = \{7\}, R(8) = \{7, 8\}, ~ \hbox {and} ~ R(9) = \{7, 8, 9\}. \end{aligned}$$

It can be seen that the sets $\emptyset \ne \widetilde{\mathcal{C }} \subsetneq \mathcal{C }$ for which $\varrho ^{\mathrm{in }}(\widetilde{\mathcal{C }})=\emptyset$ holds for (23) are exactly the sets

$$\begin{aligned} R(5), R(7), R(8), R(9), R(5) \cup R(8), ~ \hbox {and} ~ R(5) \cup R(9). \end{aligned}$$

6 The non-emptiness of the set of positive steady states regardless of the values of the rate coefficients

We generalised Corollary 4.6 in Sect. 5. Our aim in the present section is to generalise Corollary 4.7. Namely, to provide an equivalent condition to the statement “ for all $\kappa :{\mathcal{R }}\rightarrow \mathbb{R }_+$ we have $E^{\kappa }_+\ne \emptyset$” for deficiency-one reaction networks for which the graph of complexes satisfies (14). By Theorem 3.2 $(b)$, the important object is $(I_{\kappa }^{\prime \prime })^{-1}h^{\prime \prime }$, thus it does not restrict the generality if we contract the absorbing strong component of $(\mathcal{C }, {\mathcal{R }})$ into one vertex. So assume throughout this section that

$$\begin{aligned} \mathcal{C }^{\prime } ~ \hbox {is a singleton.} \end{aligned}$$

Also, in order to ease the notation, we identify the set $\mathcal{C }^{\prime }$ with the sole element in that set. (Though it is straightforward to extend all the definitions, proofs, and results of this section to the case $|\mathcal{C }^{\prime }| \ge 2$, we still suppose $|\mathcal{C }^{\prime }| = 1$ in order to avoid unnecessary technical complications.)

The rest of this section is organised as follows. After providing a formula for the entries of $(I_{\kappa }^{\prime \prime })^{-1}$ (see Theorem 6.1), we prove the generalisation of Corollary 4.7 (see Corollary 6.2). As it will be demonstrated on (32), the obtained result contains certain redundancies. We will get rid of these redundancies in three steps (see Corollaries 6.6, 6.11, 6.12). After some further manipulation, we arrive to Theorem 6.14, which is the main result of this paper. Finally, we provide some additional results related to the condition that appears in Theorem 6.14 (see Propositions 6.15 and 6.16).

We first provide a formula for the entries of the inverse of $I_{\kappa }^{\prime \prime }$ via the Matrix-Tree Theorem. This formula in some other context and with slightly different notations also appears in [23, Appendix]. Please refer to Appendix 9 for more on the Matrix-Tree Theorem.

Theorem 6.1

Assume that $(\mathcal{C }, {\mathcal{R }})$ satisfies (14). Fix $i, j \in \mathcal{C }^{\prime \prime }$. Then

$$\begin{aligned} ((I_{\kappa }^{\prime \prime })^{-1})_{ji} = -\frac{\sum _{\widetilde{\mathcal{R }} \in \mathcal{T }_\mathcal{D }^{ij}(\mathcal{C }^{\prime } \cup \{j\})}\kappa _{\widetilde{\mathcal{R }}}}{\sum _{\widetilde{\mathcal{R }} \in \mathcal{T }_\mathcal{D }(\mathcal{C }^{\prime })}\kappa _{\widetilde{\mathcal{R }}}}, \end{aligned}$$

(25)

where the summation in the enumerator goes for those $(\mathcal{C }^{\prime } \cup \{j\})$-branchings $\widetilde{\mathcal{R }}$ in $\mathcal{D } = (\mathcal{C }, {\mathcal{R }})$ for which there exists a directed path from $i$ to $j$ in $(\mathcal{C }, \widetilde{\mathcal{R }})$, while the summation in the denominator goes for the $\mathcal C ^{\prime }$-branchings $\widetilde{\mathcal{R }}$ in $\mathcal D = (\mathcal C , \mathcal{R })$ (see Appendix 7 for the definitions of these standard graph theoretical terms). The symbol $\kappa _{\widetilde{\mathcal{R }}}$ is a shorthand notation for the product $\prod _{a \in \widetilde{\mathcal{R }}} \kappa _a$.

Proof

Application of Theorem 9.3 to the transpose of $I_{\kappa }$ twice yield

$$\begin{aligned} ((I_{\kappa }^{\prime \prime })^{-1})_{ji} = ((I_{\kappa }^{\prime \prime \top })^{-1})_{ij}&= \frac{(-1)^{i+j} d_{ji}(I_{\kappa }^{\prime \prime \top })}{\det I_{\kappa }^{\prime \prime \top }} = \frac{(-1)^{i+j} d_\mathcal{C ^{\prime } \cup \{j\}, \mathcal C ^{\prime } \cup \{i\}}(I_{\kappa }^{\top })}{d_\mathcal{C ^{\prime }, \mathcal C ^{\prime }}(I_{\kappa }^{\top })} \\&= \frac{(-1)^{c-|\mathcal C ^{\prime }|-1}\sum _{\widetilde{\mathcal{R }} \in \mathcal T _\mathcal{D }^{ij}(\mathcal C ^{\prime } \cup \{j\})}\kappa _{\widetilde{\mathcal{R }}}}{(-1)^{c-|\mathcal C ^{\prime }|}\sum _{\widetilde{\mathcal{R }} \in \mathcal T _\mathcal{D }(\mathcal C ^{\prime })}\kappa _{\widetilde{\mathcal{R }}}}, \end{aligned}$$

where $d_{Q_1, Q_2}(Z)$ denotes the determinant of that matrix, which is obtained from $Z$ by deleting the rows with index in $Q_1$ and the columns with index in $Q_2$.$\square$

See Fig. 1 for an illustration of the notions appearing in Theorem 6.1.

Fig. 1

An example of a graph of complexes $\mathcal D = (\mathcal C , \mathcal{R })$ with $\mathcal C = \{C_1, C_2, C_3, C_4\}$ and $\mathcal C ^{\prime } = \{C_1\}$ (on the left), the three $1$-branchings in $\mathcal D$ (in the middle), and the five $\{1, 4\}$-branchings in $\mathcal D$ (on the right). Note that $|\mathcal T ^{24}_\mathcal{D }(\{1,4\})| = 3, |\mathcal T ^{34}_\mathcal{D }(\{1,4\})| = 4$, and $|\mathcal T ^{44}_\mathcal{D }(\{1,4\})| = 5$. Thus, e.g. for $i=2$ and $j=4$ the enumerator in (25) is the sum of $3$ products and each of these products has $2$ factors, namely, $\kappa _{23}\kappa _{34} + \kappa _{24}\kappa _{32} + \kappa _{24}\kappa _{34}$

Let us introduce the notation $L_\mathcal{D }(\kappa ) = \sum _{\widetilde{\mathcal{R }} \in \mathcal T _\mathcal{D }(\mathcal C ^{\prime })}\kappa _{\widetilde{\mathcal{R }}}$. Thus, e.g. for the example in Fig. 1 we have

$$\begin{aligned} L_\mathcal{D }(\kappa ) = \kappa _{21}\kappa _{32}\kappa _{43} + \kappa _{21}\kappa _{32}\kappa _{42} + \kappa _{21}\kappa _{34}\kappa _{42}. \end{aligned}$$

From this point on, let $h$ and $\vartheta$ be as in (5) and (8), respectively. As a consequence of Theorem 6.1, for $j\in \mathcal C ^{\prime \prime }$ we have

$$\begin{aligned} \vartheta _j = \left[ (I_{\kappa }^{\prime \prime })^{-1}h^{\prime \prime }\right] _j&= -\frac{1}{L_\mathcal{D }(\kappa )}\sum _{i\in \mathcal C ^{\prime \prime }}h_i\left( \sum _{\widetilde{\mathcal{R }}\in \mathcal T ^{ij}_\mathcal{D }(\mathcal C ^{\prime } \cup \{j\})}\kappa _{\widetilde{\mathcal{R }}}\right) \\&= -\frac{1}{L_\mathcal{D }(\kappa )} \sum _{\widetilde{\mathcal{R }} \in \mathcal T _\mathcal{D }(\mathcal C ^{\prime } \cup \{j\})}\left( \kappa _{\widetilde{\mathcal{R }}} \cdot h(V[\widetilde{\mathcal{R }},j])\right) , \end{aligned}$$

where $V[\widetilde{\mathcal{R }},j]$ denotes the vertex set of the $j$-arborescence of the $(\mathcal C ^{\prime } \cup \{j\})$-branching $\widetilde{\mathcal{R }}$ (see Appendix 7). Note that for a vertex $j \in \mathcal C ^{\prime \prime }$ and a set $U \subseteq \mathcal C ^{\prime \prime }$ there exists a $(\mathcal C ^{\prime } \cup \{j\})$-branching $\widetilde{\mathcal{R }}$ such that $V[\widetilde{\mathcal{R }},j] = U$ if and only if

$$\begin{aligned}&\hbox {for all}~i^{\prime }\in U~\hbox {there exists}~P \in \overrightarrow{i^{\prime },j}~\hbox {such that}~V[P] \subseteq U~\hbox {and}\end{aligned}$$

(26)

$$\begin{aligned}&\hbox {for all}~i^{\prime }\in \mathcal C ^{\prime \prime }\backslash U~\hbox {there exists}~P \in \overrightarrow{i^{\prime },\mathcal C ^{\prime }} \hbox {such that}~V[P] \subseteq \mathcal C \backslash U. \end{aligned}$$

(27)

Let us define the set $\mathcal C _{j-\mathrm{inarb }}^{\prime \prime }$ by

$$\begin{aligned} \mathcal C _{j-\mathrm{inarb }}^{\prime \prime } = \{ U \subseteq \mathcal C ^{\prime \prime } ~|~ U ~\hbox { satisfies } (26) \hbox { and } (27)\}. \end{aligned}$$

(28)

With this, we have

$$\begin{aligned} \vartheta _j = -\frac{1}{L_\mathcal{D }(\kappa )}\sum _{U \in \mathcal C ^{\prime \prime }_{j-\mathrm{inarb }}} \left( h(U)\sum _{\begin{array}{c} \widetilde{\mathcal{R }}\in \mathcal T _\mathcal{D }(\mathcal C ^{\prime } \cup \{j\})\\ V[\widetilde{\mathcal{R }},j]=U \end{array}}\kappa _{\widetilde{\mathcal{R }}}\right) . \end{aligned}$$

Corollary 6.2

Let $(\mathcal X ,\mathcal C ,\mathcal{R })$ be a reaction network for which $\ell = t = 1$ and $\delta = 1$. Assume that $(\mathcal C ,\mathcal{R })$ is not strongly connected and let $h \in \mathbb{R }^c$ be as in (5). Then for all $\kappa :\mathcal{R }\rightarrow \mathbb{R }_+$ we have $E^{\kappa }_+\ne \emptyset$ if and only if

$$\begin{aligned} \hbox {for all}~j\in \mathcal C ^{\prime \prime } \hbox {and} {\left\{ \begin{array}{ll} \hbox {for all}~U\in \mathcal C _{j-\mathrm{inarb }}^{\prime \prime } \ \hbox {we have}~h(U)\le 0 \ \hbox {and} \\ \hbox {there exists}~U\in \mathcal C _{j-\mathrm{inarb }}^{\prime \prime } ~\hbox {such that}~h(U) < 0.\\ \end{array}\right. } \end{aligned}$$

(29)

Proof

Since $L_\mathcal{D }(\kappa )$ is a positive number, it suffices to show that (29) is equivalent to

$$\begin{aligned} \hbox {for all } \kappa \!:\!\mathcal{R }\!\rightarrow \!\mathbb{R }_+\hbox { and for all } j \in \mathcal C ^{\prime \prime } \hbox {we have} \sum _{U \in \mathcal C ^{\prime \prime }_{j-\mathrm{inarb }}} \left( h(U)\sum _{\begin{array}{c} \widetilde{\mathcal{R }}\in \mathcal T _\mathcal{D }(\mathcal C ^{\prime } \cup \{j\})\\ V[\widetilde{\mathcal{R }},j]=U \end{array}}\kappa _{\widetilde{\mathcal{R }}}\right) \!<\! 0.\nonumber \\ \end{aligned}$$

(30)

It is obvious that (29) implies (30).

To prove the other direction, assume that (30) holds and fix $j \in \mathcal C ^{\prime \prime }$. It is clear that the case $h(U) = 0$ for all $U \in \mathcal C ^{\prime \prime }_{j-\mathrm{inarb }}$ would contradict (30). Thus, it suffices to exclude that there exists $U \in \mathcal C ^{\prime \prime }_{j-\mathrm{inarb }}$ such that $h(U) > 0$. Suppose by contradiction that $\overline{U} \in \mathcal C ^{\prime \prime }_{j-\mathrm{inarb }}$ is such that $h(\overline{U}) > 0$. If there is no other element of $\mathcal C ^{\prime \prime }_{j-\mathrm{inarb }}$ than $\overline{U}$ then we obviously get a contradiction with (30). So suppose for the rest of this proof that $\overline{U}$ is not the only element of $\mathcal C ^{\prime \prime }_{j-\mathrm{inarb }}$. Then

$$\begin{aligned}&\sum _{U \in \mathcal C ^{\prime \prime }_{j-\mathrm{inarb }}} \left( h(U)\sum _{\begin{array}{c} \widetilde{\mathcal{R }}\in \mathcal T _\mathcal{D }(\mathcal C ^{\prime } \cup \{j\})\\ V[\widetilde{\mathcal{R }},j]=U \end{array}}\kappa _{\widetilde{\mathcal{R }}}\right) = h(\overline{U})\sum _{\begin{array}{c} \widetilde{\mathcal{R }}\in \mathcal T _\mathcal{D }(\mathcal C ^{\prime } \cup \{j\})\\ V[\widetilde{\mathcal{R }},j]=\overline{U} \end{array}}\kappa _{\widetilde{\mathcal{R }}} \nonumber \\&\quad + \sum _{U \in \mathcal C ^{\prime \prime }_{j-\mathrm{inarb }} \backslash \{\overline{U}\}} \left( h(U)\sum _{\begin{array}{c} \widetilde{\mathcal{R }}\in \mathcal T _\mathcal{D }(\mathcal C ^{\prime } \cup \{j\})\\ V[\widetilde{\mathcal{R }},j]=U \end{array}}\kappa _{\widetilde{\mathcal{R }}}\right) , \end{aligned}$$

(31)

where the first term is positive and is not affected by $\kappa |_{\varrho ^{\mathrm{in }}(\overline{U}) \cup \varrho ^{\mathrm{out }}(\overline{U})}$, while for all $U \in \mathcal C ^{\prime \prime }_{j-\mathrm{inarb }} \backslash \{\overline{U}\}$ and for all $\widetilde{\mathcal{R }}\in \mathcal T _\mathcal{D }(\mathcal C ^{\prime } \cup \{j\})$ such that $V[\widetilde{\mathcal{R }},j]=U$, we have $\widetilde{\mathcal{R }} \cap (\varrho ^{\mathrm{in }}(\overline{U}) \cup \varrho ^{\mathrm{out }}(\overline{U})) \ne \emptyset$. Thus, by setting the values of $\kappa |_{\varrho ^{\mathrm{in }}(\overline{U}) \cup \varrho ^{\mathrm{out }}(\overline{U})}$ close enough to zero, we can achieve that the absolute value of the second term of the right hand side of (31) is smaller than the (positive) value of the first term in the same. This contradicts (30).$\square$

Note that Corollary 6.2 is a generalisation of Corollary 4.7. However, there are certain redundancies in the set of conditions in (29), and therefore our aim in the rest of this section is to get rid of these. In order to illustrate the result of Corollary 6.2 and also the redundancy in (29), consider that the graph of complexes takes the form

(32)

One can check by short calculation that

$$\begin{aligned} \begin{array}{ccccccl} \mathcal C ^{\prime \prime }_{2-\mathrm{inarb }} = &{} \{ &{} \{2,3,4,5,6,7,8\} &{} &{} &{} &{} \}, \\ \mathcal C ^{\prime \prime }_{3-\mathrm{inarb }} = &{} \{ &{} \{3,4\}, &{} \{3,4,7,8\} &{} &{} &{} \}, \\ \mathcal C ^{\prime \prime }_{4-\mathrm{inarb }} = &{} \{ &{} \{4\}, &{} \{3,4\}, &{} \{4,7,8\}, &{} \{3,4,7,8\} &{} \}, \\ \mathcal C ^{\prime \prime }_{5-\mathrm{inarb }} = &{} \{ &{} \{5\}, &{} \{5,6\}, &{} \{5,6,7,8\} &{} &{} \}, \\ \mathcal C ^{\prime \prime }_{6-\mathrm{inarb }} = &{} \{ &{} \{6\}, &{} \{5,6\}, &{} \{6,7,8\}, &{} \{5,6,7,8\} &{} \}, \\ \mathcal C ^{\prime \prime }_{7-\mathrm{inarb }} = &{} \{ &{} \{7,8\} &{} &{} &{} &{} \}, ~ \hbox {and} \\ \mathcal C ^{\prime \prime }_{8-\mathrm{inarb }} = &{} \{ &{} \{8\}, &{} \{7,8\} &{} &{} &{} \}. \\ \end{array} \end{aligned}$$

(33)

Note however that e.g. the set $\{3,4,7,8\} \in \mathcal C ^{\prime \prime }_{3-\mathrm{inarb }}$ is the disjoint union of the sets $\{3,4\} \in \mathcal C ^{\prime \prime }_{3-\mathrm{inarb }}$ and $\{7,8\} \in \mathcal C ^{\prime \prime }_{7-\mathrm{inarb }}$. Hence, once we require that $h(\{3,4\}) \le 0$ and $h(\{7,8\}) \le 0$, it is unnecessary to require also $h(\{3,4,7,8\}) \le 0$, because then it is automatically satisfied. Similarly, one may easily see for (32) that for all $j \in \mathcal C ^{\prime \prime }$ and for all $U \in \mathcal C ^{\prime \prime }_{j-\mathrm{inarb }}$, the set $U$ is the disjoint union of some of the sets

$$\begin{aligned} \{2,3,4,5,6,7,8\}, \{3,4\}, \{4\}, \{5\}, \{6\}, \{7,8\}, ~ \hbox {and} ~ \{8\}. \end{aligned}$$

Moreover, such a partition of $U$ is unique. Thus, for (32) the following are equivalent.

$$\begin{aligned}&\hbox {For all}~j\in \mathcal C ^{\prime \prime } ~\hbox {and for all}~U\in \mathcal C _{j-\mathrm{inarb }}^{\prime \prime } ~\hbox {we have}~ h(U)\le 0. \end{aligned}$$

(34)

$$\begin{aligned}&\hbox {We have } h(\{2,3,4,5,6,7,8\}) \le 0, h(\{3,4\}) \le 0, h(\{4\}) \le 0,\nonumber \\&\hbox {h}(\{5\}) \le 0, \hbox {h}(\{6\}) \le 0, \hbox {h}(\{7,8\}) \le 0, \hbox { and}~ \hbox {h}(\{8\}) \le 0 \\&\hbox {(i.e., we require the non-positivity of } h \hbox { only for the first sets in each row of } (33)).\nonumber \end{aligned}$$

(35)

We formulate in the following lemma that the above mentioned facts about (32) hold generally.

Lemma 6.3

Assume that $(\mathcal C , \mathcal{R })$ satisfies (14). For $j \in \mathcal C ^{\prime \prime }$ let $\mathcal C ^{\prime \prime }_{j-\mathrm{inarb }}$ be as in (28). For $i \in \mathcal C$ let us define $U(i) \subseteq \mathcal C$ by

$$\begin{aligned} U(i)=\{k\in \mathcal C \,|\, {\textit{for all }} P \in \overrightarrow{k,\mathcal C ^{\prime }} {\textit{ we have }} i \in V[P]\}, \end{aligned}$$

(36)

i.e., $k \in \mathcal C$ is an element of $U(i)$ if all the directed paths from $k$ to $\mathcal C ^{\prime }$ must traverse $i$ (clearly, for $i \in \mathcal C ^{\prime \prime }$ we have $U(i) \subseteq \mathcal C ^{\prime \prime }$). Then

• (a) for all $j \in \mathcal C ^{\prime \prime }$ we have $U(j) \in \mathcal C ^{\prime \prime }_{j-\mathrm{inarb }}$ and

• (b) for all $j \in \mathcal C ^{\prime \prime }$ and for all $U \in \mathcal C ^{\prime \prime }_{j-\mathrm{inarb }}$ there exists a unique $\mathcal I _U \subseteq \mathcal C ^{\prime \prime }$ such that

  $$\begin{aligned} U = \mathop {{\bigcup }^{*}}\limits _{i \in \mathcal I _U} U(i), \end{aligned}$$

where the symbol $^*$ stresses that if $i, i^{\prime } \in \mathcal I _U$ and $i \ne i^{\prime }$ then $U(i) \cap U(i^{\prime }) = \emptyset$.

The proof of Lemma 6.3 is carried out right after the proof of Lemma 6.4 below. Clearly, we have $U(\mathcal C ^{\prime }) = \mathcal C$, but we will use the set $U(\mathcal C ^{\prime })$ only after Theorem 6.14. Before that, we will be interested in the collection $\{U(i) ~|~ i \in \mathcal C ^{\prime \prime }\}$. We remark that the notation $U(i)$ is in accordance with the similar one in Sect. 4.2. Note that for the reaction network (32) we have

$$\begin{aligned}&U(2) = \{2,3,4,5,6,7,8\}, U(3) = \{3,4\}, U(4) = \{4\}, U(5) = \{5\},\\&U(6) = \{6\}, U(7) = \{7,8\}, ~ \hbox {and} ~ U(8) = \{8\}. \end{aligned}$$

Before we prove Lemma 6.3, we explore some properties of the collection $\{U(i)~|~i\in \mathcal C ^{\prime \prime }\}$ in the following lemma. Note that for all $k\in \mathcal C ^{\prime \prime }$ there exists a directed path from $k$ to $\mathcal C ^{\prime }$ (i.e., for all $k \in \mathcal C ^{\prime \prime }$ we have $\overrightarrow{k,\mathcal C ^{\prime }} \ne \emptyset$).

Lemma 6.4

Assume that $(\mathcal C , \mathcal{R })$ satisfies (14). Let $i, i^{\prime } \in \mathcal C ^{\prime \prime }$ and define $U(i)$ and $U(i^{\prime })$ as in (36). Then

• (a) $i \in U(i)$,

• (b) if $i^{\prime } \in U(i)\backslash \{i\}$ then $U(i^{\prime }) \subseteq U(i) \backslash \{i\}$,

• (c) if $i \ne i^{\prime }$ then either $U(i) \subsetneq U(i^{\prime })$ or $U(i) \supsetneq U(i^{\prime })$ or $U(i) \cap U(i^{\prime }) = \emptyset$, and

• (d) $\varrho ^{\mathrm{out }}(U(i))\subseteq \varrho ^{\mathrm{out }}(i)$ (i.e., all the arcs that leave $U(i)$ have tail $i$).

Proof

Statement $(a)$ is trivial.

To prove statement $(b)$, assume that $i^{\prime }\in U(i)\backslash \{i\}$ and let $i^{\prime \prime }\in U(i^{\prime })$. Then all the directed paths from $i^{\prime \prime }$ to $\mathcal C ^{\prime }$ traverse $i^{\prime }$ and since $i^{\prime }\in U(i)$, they must also traverse $i$. This proves that $U(i^{\prime })\subseteq U(i)$. To prove $(b)$, it remains to show that $i\notin U(i^{\prime })$. However, it is also obvious, because $i^{\prime }\in U(i)$ guarantees that there exists a directed path from $i^{\prime }$ to $\mathcal C ^{\prime }$, which traverses $i$. Since there cannot be vertex repetition in a directed path and $i\ne i^{\prime }$, this also shows that there exists a directed path from $i$ to $\mathcal C ^{\prime }$ that does not traverse $i^{\prime }$.

To show $(c)$, suppose that $U(i)\cap U(i^{\prime })\ne \emptyset$ and let $i^{\prime \prime }\in U(i)\cap U(i^{\prime })$. Then all the directed paths from $i^{\prime \prime }$ to $\mathcal C ^{\prime }$ must traverse both $i$ and $i^{\prime }$. Note that the order of $i$ and $i^{\prime }$ on these directed paths must be the same, otherwise we could easily construct two directed paths from $i^{\prime \prime }$ to $\mathcal C ^{\prime }$, one of which avoids $i$ and the other one avoids $i^{\prime }$. As a consequence, either $i\in U(i^{\prime })\backslash \{i^{\prime }\}$ or $i^{\prime }\in U(i)\backslash \{i\}$. In both cases we are done by $(b)$.

To prove $(d)$, suppose by contradiction that there exist $i^{\prime }\in U(i)\backslash \{i\}$ and $i^{\prime \prime }\in \mathcal C \backslash U(i)$ such that $(i^{\prime },i^{\prime \prime })\in \mathcal{R }$. Then there exists $P\in \overrightarrow{i^{\prime \prime },\mathcal C ^{\prime }}$ such that $i \notin V[P]$. Therefore $\mathrm{con }(i^{\prime },P)\in \overrightarrow{i^{\prime },\mathcal C ^{\prime }}$ is a directed path that avoids $i$, contradicting $i^{\prime }\in U(i)$ (see Appendix 7 for the definition of the concatenation).$\square$

Proof of Lemma 6.3

To prove $(a)$, fix $j \in \mathcal C ^{\prime \prime }$ and let $i^{\prime } \in \mathcal C ^{\prime \prime }$. Assume first that $i^{\prime } \in U(j)$ and let $P \in \overrightarrow{i^{\prime },\mathcal C ^{\prime }}$. By Lemma 6.4 $(d), V[P^{i^{\prime }:j}] \subseteq U(j)$ ($P^{i^{\prime }:j}$ denotes the part of $P$ from $i^{\prime }$ to $j$, see Appendix 7). Assume now that $i^{\prime } \in \mathcal C ^{\prime \prime } \backslash U(j)$. We need to show that there exists a directed path from $i^{\prime }$ to $\mathcal C ^{\prime }$ that avoids $U(j)$. Suppose by contradiction that for all $P \in \overrightarrow{i^{\prime },\mathcal C ^{\prime }}$ we have $V[P] \cap U(j) \ne \emptyset$. Then, by Lemma 6.4 $(d)$, it follows that $j \in V[P]$, which contradicts $i^{\prime } \notin U(j)$.

It is left to prove $(b)$. Fix $j \in \mathcal C ^{\prime \prime }$ and $U \in \mathcal C ^{\prime \prime }_{j-\mathrm{inarb }}$. For $i \in U$, we have $U(i) \subseteq U$, because otherwise there would be an element $i^{\prime } \in U(i) \backslash U$, for which there does not exist a directed path from $i^{\prime }$ to $\mathcal C ^{\prime }$, which avoids $U$. Since we also have $i \in U(i)$ (see Lemma 6.4 $(a)$), it holds that $U = \cup _{i \in U} U(i)$. From this and Lemma 6.4 $(c)$ it follows that $U$ is indeed the disjoint union of some $U(i)$’s and this partition is unique. Namely those $U(i)$’s take part in the partition, which are maximal inside $U$.$\square$

We obtain the following corollary, which is the first step towards the simplification of (29).

Corollary 6.5

Assume that $(\mathcal C , \mathcal{R })$ satisfies (14) and let $h \in \mathbb{R }^c$ be arbitrary. For $i, j \in \mathcal C ^{\prime \prime }$ let $\mathcal C ^{\prime \prime }_{j-\mathrm{inarb }}$ be as in (28) and let $U(i)$ be as in (36). Then the following two statements are equivalent.

• (A) For all $j\in \mathcal C ^{\prime \prime }$ and for all $U\in \mathcal C _{j-\mathrm{inarb }}^{\prime \prime }$ we have $h(U)\le 0$.

• (B) For all $i\in \mathcal C ^{\prime \prime }$ we have $h(U(i))\le 0$.

Proof

Suppose that $(A)$ holds. Then $(B)$ follows directly from Lemma 6.3 $(a)$.

Now suppose that $(B)$ holds. Statement $(A)$ is then obtained immediately from Lemma 6.3 $(b)$.$\square$

Corollary 6.6

Let $(\mathcal X ,\mathcal C ,\mathcal{R })$ be a reaction network for which $\ell = t = 1$ and $\delta = 1$. Assume that $(\mathcal C ,\mathcal{R })$ is not strongly connected and let $h \in \mathbb{R }^c$ be as in (5). For $i, j \in \mathcal C ^{\prime \prime }$ let $\mathcal C ^{\prime \prime }_{j-\mathrm{inarb }}$ be as in (28) and let $U(i)$ be as in (36). Then for all $\kappa :\mathcal{R }\rightarrow \mathbb{R }_+$ we have $E^{\kappa }_+\ne \emptyset$ if and only if

$$\begin{aligned} {\left\{ \begin{array}{ll} {\textit{for all}} \ i \in \mathcal C ^{\prime \prime } \ {\textit{we have}} \ h(U(i))\le 0 \hbox { and} \\ {\textit{for all}} \ j\in \mathcal C ^{\prime \prime } \ {\textit{there exists}} \ i \in \cup _{U \in \mathcal C ^{\prime \prime }_{j-\mathrm{inarb }}} \mathcal I _U \ {\textit{such that}} \ h(U(i)) < 0, \\ \end{array}\right. } \end{aligned}$$

(37)

where $\mathcal I _U$ is the unique subset of $\mathcal C ^{\prime \prime }$ such that $U = \cup _{i^{\prime } \in \mathcal I _U}^* U(i^{\prime })$ (see Lemma 6.3 $(b)$).

Proof

The equivalence is a direct consequence of Corollary 6.2, Lemma 6.3 $(b)$, and Corollary 6.5.$\square$

In order to ease the notation in (37), we define for $j \in \mathcal C ^{\prime \prime }$ the set $W(j)$ by

$$\begin{aligned} W(j) = \bigcup _{U \in \mathcal C ^{\prime \prime }_{j-\mathrm{inarb }}} \mathcal I _U. \end{aligned}$$

(38)

By Lemmas 6.3 $(b)$ and 6.4 $(c)$, for $i, j \in \mathcal C ^{\prime \prime }$ and $U \in \mathcal C ^{\prime \prime }_{j-\mathrm{inarb }}$ we have

$$\begin{aligned} i \!\in \! \mathcal I _U ~ \hbox {if and only if} ~ i \!\in \! U ~ \hbox {and there does not exist} ~ i^{\prime } \!\in \! U \backslash \{i\} ~ \hbox {such that} ~ i \!\in \! U(i^{\prime }).\nonumber \\ \end{aligned}$$

(39)

To illustrate the result of Corollary 6.6, note that for the reaction network (32) we have

$$\begin{aligned}&\{2,3,4,5,6,7,8\} = U(2), \\&\{3,4\} = U(3), \{3,4,7,8\} = U(3) \cup ^* U(7), \\&\{4\} = U(4), \{3,4\} = U(3), \{4,7,8\} = U(4) \cup ^* U(7), \{3,4,7,8\} = U(3) \cup ^* U(7), \\&\{5\} = U(5), \{5,6\} = U(5) \cup ^* U(6), \{5,6,7,8\} = U(5) \cup ^* U(6) \cup ^* U(7), \\&\{6\} = U(6), \{5,6\} = U(5) \cup ^* U(6), \{6,7,8\} = U(6) \cup ^* U(7), \\&\{5,6,7,8\} = U(5) \cup ^* U(6) \cup ^* U(7), \{7,8\} = U(7), ~ \hbox {and} \\&\{8\} = U(8), \{7,8\} = U(7). \end{aligned}$$

Thus,

$$\begin{aligned} \begin{array}{llll} \mathcal I _{\{2,3,4,5,6,7,8\}} = \{2\}, &{} &{} &{} \\ \mathcal I _{\{3,4\}} = \{3\}, &{} \mathcal I _{\{3,4,7,8\}} = \{3, 7\}, &{} &{} \\ \mathcal I _{\{4\}} = \{4\}, &{} \mathcal I _{\{3,4\}} = \{3\}, &{} \mathcal I _{\{4,7,8\}} = \{4, 7\}, &{}\mathcal I _{\{3,4,7,8\}} = \{3, 7\}, \\ \mathcal I _{\{5\}} = \{5\}, &{} \mathcal I _{\{5,6\}} = \{5, 6\}, &{} \mathcal I _{\{5,6,7,8\}} = \{5, 6, 7\}, &{} \\ \mathcal I _{\{6\}} = \{6\}, &{} \mathcal I _{\{5,6\}} = \{5, 6\}, &{} \mathcal I _{\{6,7,8\}} = \{6, 7\}, &{}\mathcal I _{\{5,6,7,8\}} = \{5, 6, 7\}, \\ \mathcal I _{\{7,8\}} = \{7\}, ~ \hbox {and} &{} &{} &{} \\ \mathcal I _{\{8\}} = \{8\}, &{} \mathcal I _{\{7,8\}} = \{7\}, &{} &{} \\ \end{array} \end{aligned}$$

and therefore

$$\begin{aligned}&W(2) = \{2\}, W(3) = \{3, 7\}, W(4) = \{3, 4, 7\}, W(5) = \{5, 6, 7\},\nonumber \\&W(6) = \{5, 6, 7\}, W(7) = \{7\}, \, \hbox {and} \, W(8) = \{7, 8\}. \end{aligned}$$

(40)

Since

$$\begin{aligned} W(7) \subseteq W(3), W(7) \subseteq W(4), W(7) \subseteq W(5), W(7) \subseteq W(6), \, \text{ and } \, W(7) \subseteq W(8), \end{aligned}$$

once we require that there exist $i_2 \in W(2)$ and $i_7 \in W(7)$ such that $h(U(i_2)) < 0$ and $h(U(i_7)) < 0$ hold, it is unnecessary to require also e.g. that there exists $i_4 \in W(4)$ such that $h(U(i_4)) < 0$, because that is automatically satisfied. Our aim is to get rid of these sort of redundancies in Corollary 6.6. For this, we first take a closer look at the collection $\{W(j) ~|~ j \in \mathcal C ^{\prime \prime }\}$ in Proposition 6.8. During the proof of that proposition, we will use the following corollary of Menger’s Theorem.

Theorem 6.7

Let $D = (V,A)$ be a directed graph and let $s, t$ be such that $(s,t) \notin A$. Then there exists $P_1, P_2 \in \overrightarrow{s, t}$ such that $V[P_1] \cap V[P_2] = \{s,t\}$ if and only if for all $i \in V \backslash \{s, t\}$ there exists $P \in \overrightarrow{s, t}$ such that $i \notin V[P]$.

Proof

The result is a direct consequence of Theorem 7.1. See [24, Section 9.1] for more on Menger’s Theorem.$\square$

Proposition 6.8

Assume that $(\mathcal C , \mathcal{R })$ satisfies (14). Let $j \in \mathcal C ^{\prime \prime }$ and let $W(j)$ be as in (38). Then

$$\begin{aligned} W(j)\!=\!\{i\!\in \!\mathcal C ^{\prime \prime }\,|\,\hbox {there exist } P_j\!\in \!\overrightarrow{i,j} \hbox { and } P_\mathcal{C ^{\prime }}\!\in \!\overrightarrow{i,\mathcal C ^{\prime }} \,\hbox {such that } V[P_j]\cap V[P_\mathcal{C ^{\prime }}]\!=\!\{i\}\}.\nonumber \\ \end{aligned}$$

(41)

Proof

Denote by $Q(j)$ the set on the right hand side of (41). We will show (41) by showing that both $W(j) \subseteq Q(j)$ and $W(j) \supseteq Q(j)$ hold.

First we prove that $W(j) \subseteq Q(j)$ holds. By (38) and (39), we obtain for $i \in \mathcal C ^{\prime \prime }$ that $i \in W(j)$ if and only if

$$\begin{aligned} \hbox {there exists } U \!\in \! \mathcal C ^{\prime \prime }_{j-\mathrm{inarb }} \hbox { such that } i \!\in \! U \hbox {and for all } i^{\prime } \!\in \! U \backslash \{i\} \hbox { we have } i \!\notin \! U(i^{\prime }).\qquad \end{aligned}$$

(42)

To obtain an equivalent description of $Q(j)$, we will apply Theorem 6.7 for the directed graph

$$\begin{aligned} \widehat{\mathcal{D }} = ({\mathcal{C }} \cup \{\mathfrak{c }\}, {{\mathcal{R }}} \cup \{(j, {\mathfrak{c }}), ({\mathcal{C }}^{\prime }, {\mathfrak{c }})\}), \end{aligned}$$

where $\mathfrak{c }$ is an auxiliary vertex. Thus, we have added the arcs $(j, \mathfrak{c })$ and $(\mathcal C ^{\prime }, \mathfrak{c })$ to $\mathcal{R }$. Application of Theorem 6.7 with $s = i \in \mathcal C ^{\prime \prime } \backslash \{j\}$ and $t = \mathfrak{c }$ yields that for $i \in \mathcal C ^{\prime \prime } \backslash \{j\}$ that we have $i \in Q(j)$ if and only if

$$\begin{aligned} \overrightarrow{i,j} \!\ne \! \emptyset \hbox { and for all } i^{\prime } \!\in \! \mathcal C ^{\prime \prime } \backslash \{i\} \hbox { we have } i \notin U(i^{\prime }) \hbox { or there exists } P \!\in \! \overrightarrow{i,j} \hbox { such that } i^{\prime } \notin V[P],\nonumber \\ \end{aligned}$$

(43)

where the “or” is inclusive. Using (26), it is obvious that (42) implies (43) for $i \in \mathcal C ^{\prime \prime } \backslash \{j\}$. Thus, taking also into account that $j \in Q(j)$ holds obviously, we obtain the inclusion $W(j) \subseteq Q(j)$.

It is left to prove $W(j) \supseteq Q(j)$. Fix $i \in Q(j), P_j \in \overrightarrow{i,j}$, and $P_\mathcal{C ^{\prime }} \in \overrightarrow{i,\mathcal C ^{\prime }}$ such that $V[P_j] \cap V[P_\mathcal{C ^{\prime }}] = \{i\}$. Let

$$\begin{aligned} U = \{ i^{\prime } \in \mathcal C ^{\prime \prime } ~|~ \hbox {there exists} ~ P \in \overrightarrow{i^{\prime },j} ~ \hbox {such that} ~ V[P] \cap V[P_\mathcal{C ^{\prime }}] \subseteq \{i\} \}, \end{aligned}$$

(44)

i.e., we collect those vertices, from which it is possible to reach $j$ without traversing $P_\mathcal{C ^{\prime }}$ except maybe in $i$. It is trivial that $U$ in (44) satisfies (26). Also, it is easy to see that $U$ in (44) fulfills (27). Thus, we have $U\in \mathcal C _{j-\mathrm{inarb }}^{\prime \prime }$. The only thing it is left to check is that $i \in \mathcal I _U$. Clearly, $i \in U$ and $(V[P_\mathcal{C ^{\prime }}] \backslash \{i\}) \cap U = \emptyset$. Hence, there does not exist $i^{\prime } \in U \backslash \{i\}$ such that $i \in U(i^{\prime })$. Thus, by (39), we obtain that $i \in \mathcal I _U$. This concludes the proof of the inclusion $W(j) \supseteq Q(j)$.$\square$

In case $j_1,j_2\in \mathcal C ^{\prime \prime }$ are such that $W(j_1)\subseteq W(j_2)$, it is redundant in Corollary 6.6 to require that there exists $i \in W(j_2)$ such that $h(U(i))<0$, because this already follows if we require the same for $j_1$ instead of $j_2$. In order to get rid of these kind of redundancies, we take a closer look at the collection $\{ W(j) ~ | ~ j \in \mathcal C ^{\prime \prime } \}$. The following lemma is the key.

Lemma 6.9

Assume that $(\mathcal C , \mathcal{R })$ satisfies (14). For $j \in \mathcal C ^{\prime \prime }$ let $W(j)$ be as in (38). Fix $j_1, j_2 \in \mathcal C ^{\prime \prime }$ such that $j_1 \in W(j_2)$. Then $W(j_1) \subseteq W(j_2)$.

Proof

Let $j_3 \in W(j_1)$. Our aim is to show that $j_3$ is also an element of $W(j_2)$. If $j_3 = j_2$ then $j_3 \in W(j_2)$ trivially holds, so let us assume for the rest of this proof that $j_3 \ne j_2$. Similarly to the proof of Proposition 6.8, we will apply Theorem 6.7 to the directed graph

$$\begin{aligned} \widehat{\mathcal{D }} = ({\mathcal{C }} \cup \{\mathfrak{c }\}, {{\mathcal{R }}} \cup \{(j_2, {\mathfrak{c }}), ({\mathcal{C }}^{\prime }, {\mathfrak{c }})\}), \end{aligned}$$

where $\mathfrak{c }$ is an auxiliary vertex. Let

$$\begin{aligned}&P_{j_2} \in \overrightarrow{j_1, j_2} ~ \hbox {and} ~ P_\mathcal{C ^{\prime }} \in \overrightarrow{j_1, \mathcal C ^{\prime }} ~ \hbox {be such that} ~ V[P_{j_2}] \cap V[P_\mathcal{C ^{\prime }}] = \{j_1\} ~ \hbox {and} \\&Q_{j_1} \in \overrightarrow{j_3, j_1} ~ \hbox {and} ~ Q_\mathcal{C ^{\prime }} \in \overrightarrow{j_3, \mathcal C ^{\prime }} ~ \hbox {be such that} ~ V[Q_{j_1}] \cap V[Q_\mathcal{C ^{\prime }}] = \{j_3\}. \end{aligned}$$

Clearly, once we show that for all $i \in \mathcal C \backslash \{j_3\}$ there exists a directed path from $j_3$ to $\mathfrak{c }$ in $\widehat{\mathcal{D }}$ that does not traverse $i$, we can draw the conclusion $j_3 \in W(j_2)$ by Theorem 6.7.

First let $i \in \mathcal C \backslash V[Q_\mathcal{C ^{\prime }}]$. Then $\mathrm{con }(Q_\mathcal{C ^{\prime }}, \mathfrak{c })$ is a directed path from $j_3$ to $\mathfrak{c }$ in $\widehat{\mathcal{D }}$ that does not traverse $i$.

It is left to treat the case $i \in V[Q_\mathcal{C ^{\prime }}] \backslash \{j_3\}$. Then $i \notin V[P_{j_2}]$ or $i \notin V[P_\mathcal{C ^{\prime }}]$, where the “ or” is inclusive. If $i \notin V[P_{j_2}]$ then $\mathrm{con }(Q_{j_1},P_{j_2},\mathfrak{c })$ is a directed walk from $j_3$ to $\mathfrak{c }$ in $\widehat{\mathcal{D }}$ that does not traverse $i$. If $i \notin V[P_\mathcal{C ^{\prime }}]$ then $\mathrm{con }(Q_{j_1},P_\mathcal{C ^{\prime }},\mathfrak{c })$ is a directed walk from $j_3$ to $\mathfrak{c }$ in $\widehat{\mathcal{D }}$ that does not traverse $i$. In both cases, one may easily construct the desired directed path from the directed walk.$\square$

For $j \in \mathcal C ^{\prime \prime }$, denote by $\mathcal C ^{\prime \prime }(j)$ the vertex set of that strong component of $(\mathcal C ,\mathcal{R })$, which contains $j$. Thus, for (32) we have

$$\begin{aligned} \mathcal C ^{\prime \prime }(2)&= \{2\}, \mathcal C ^{\prime \prime }(3) = \mathcal C ^{\prime \prime }(4) = \{3, 4\}, \mathcal C ^{\prime \prime }(5) = \mathcal C ^{\prime \prime }(6)= \{5, 6\}, ~\\&\hbox {and} ~ \mathcal C ^{\prime \prime }(7) = \mathcal C ^{\prime \prime }(8) = \{7, 8\}. \end{aligned}$$

For $j \in \mathcal C ^{\prime \prime }$ we say that it is possible to leave $\mathcal C ^{\prime \prime }(j)$ through $j$ if $\varrho ^{\mathrm{out }}(j) \cap \varrho ^{\mathrm{out }}(\mathcal C ^{\prime \prime }(j)) \ne \emptyset$. For (32), this property holds with $j \in \{2, 3, 5, 6, 7\}$.

Corollary 6.10

Assume that $(\mathcal C , \mathcal{R })$ satisfies (14). For $j \in \mathcal C ^{\prime \prime }$ let $W(j)$ be as in (38). Let $j \in \mathcal C ^{\prime \prime }$ be such that “ it is possible to leave $\mathcal C ^{\prime \prime }(j)$ through $j$” (i.e., $\varrho ^{\mathrm{out }}(j) \cap \varrho ^{\mathrm{out }}(\mathcal C ^{\prime \prime }(j)) \ne \emptyset$). Then for all $j^{\prime } \in \mathcal C ^{\prime \prime }(j)$ we have $W(j) \subseteq W(j^{\prime })$.

Proof

Fix $j^{\prime } \in \mathcal C ^{\prime \prime }(j)$. There exists a directed path from $j$ to $j^{\prime }$ which uses only vertices in $\mathcal C ^{\prime \prime }(j)$. On the other hand, since $\varrho ^{\mathrm{out }}(j) \cap \varrho ^{\mathrm{out }}(\mathcal C ^{\prime \prime }(j)) \ne \emptyset$, it is possible to reach $\mathcal C ^{\prime }$ from $j$ using only vertices from $\mathcal C \backslash (\mathcal C ^{\prime \prime }(j) \backslash \{j\})$. Hence, by Proposition 6.8, we have $j \in W(j^{\prime })$. Lemma 6.9 concludes the proof.$\square$

It is clear from the above corollary that if $j_1,j_2 \in \mathcal C ^{\prime \prime }$ are such that $\mathcal C ^{\prime \prime }(j_1)=\mathcal C ^{\prime \prime }(j_2), \varrho ^{\mathrm{out }}(j_1) \cap \varrho ^{\mathrm{out }}(\mathcal C ^{\prime \prime }(j_1)) \ne \emptyset$, and $\varrho ^{\mathrm{out }}(j_2) \cap \varrho ^{\mathrm{out }}(\mathcal C ^{\prime \prime }(j_2)) \ne \emptyset$ then $W(j_1) = W(j_2)$. For the reaction network (32) we indeed have $W(5) = W(6)$.

Let $\mathcal J$ be a subset of $\mathcal C ^{\prime \prime }$ for which

$$\begin{aligned} \begin{aligned}&\mathcal J \hbox {contains precisely one element of each non-absorbing strong component of} \\&(\mathcal C ,\mathcal{R }) \,\hbox {and}\,\hbox {for all} j \in \mathcal J \hbox { we have } \varrho ^{\mathrm{out }}(j) \cap \varrho ^{\mathrm{out }}(\mathcal C ^{\prime \prime }(j)) \ne \emptyset . \end{aligned} \end{aligned}$$

(45)

For (32) we have two choices for $\mathcal J$. One is $\{2,3,5,7\}$, while the other one is $\{2,3,6,7\}$. To be concrete, let $\mathcal J = \{2,3,5,7\}$. Due to Corollary 6.10, we have

$$\begin{aligned} W(3) \subseteq W(4), W(5) \subseteq W(6), ~ \hbox {and} ~ W(7) \subseteq W(8), \end{aligned}$$

which is indeed the case (see (40)).

We have thus obtained the following corollary.

Corollary 6.11

Let $(\mathcal X ,\mathcal C ,\mathcal{R })$ be a reaction network for which $\ell = t = 1$ and $\delta = 1$. Assume that $(\mathcal C ,\mathcal{R })$ is not strongly connected and let $h \in \mathbb{R }^c$ be as in (5). For $i, j \in \mathcal C ^{\prime \prime }$ let $U(i)$ and $W(j)$ be as in (36) and (38), respectively. Also, let $\mathcal J$ be as in (45). Then for all $\kappa :\mathcal{R }\rightarrow \mathbb{R }_+$ we have $E^{\kappa }_+\ne \emptyset$ if and only if

$$\begin{aligned} {\left\{ \begin{array}{ll} \textit{for all} \ i \in \mathcal C ^{\prime \prime } \ \textit{we have} \ h(U(i))\le 0 \ \textit{and} \\ \textit{for all} \ j \in \mathcal J \ \textit{there exists} \ i \in W(j) \ \textit{such that} \ h(U(i)) < 0. \\ \end{array}\right. } \end{aligned}$$

(46)

Proof

The equivalence follows directly from (38) and Corollaries 6.6 and 6.10.$\square$

Since for (32) we have made the choice $\mathcal J = \{2,3,5,7\}$, Corollary 6.11 suggests that the sets of importance are $W(2), W(3), W(5)$, and $W(7)$. Recall that

$$\begin{aligned} W(2) = \{2\}, W(3) = \{3, 7\}, W(5) = \{5, 6, 7\}, ~ \hbox {and} ~ W(7) = \{7\}. \end{aligned}$$

(47)

As $7 \in W(3)$ and $7 \in W(5)$, by Lemma 6.9 we have $W(7) \subseteq W(3)$ and $W(7) \subseteq W(5)$ (which is anyway obvious from (47)). Thus, still there is redundancy in Corollary 6.11. Elimination of this redundancy is formulated in the following corollary.

Corollary 6.12

Let $(\mathcal X ,\mathcal C ,\mathcal{R })$ be a reaction network for which $\ell = t = 1$ and $\delta = 1$. Assume that $(\mathcal C ,\mathcal{R })$ is not strongly connected and let $h \in \mathbb{R }^c$ be as in (5). For $i, j \in \mathcal C ^{\prime \prime }$ let $U(i)$ and $W(j)$ be as in (36) and (38), respectively. Also, let $\mathcal J$ be as in (45). Then for all $\kappa :\mathcal{R }\rightarrow \mathbb{R }_+$ we have $E^{\kappa }_+\ne \emptyset$ if and only if

$$\begin{aligned} {\left\{ \begin{array}{ll} \hbox {for all } i \in \mathcal C ^{\prime \prime } \hbox { we have } h(U(i))\le 0 \hbox { and} \\ \hbox {for all } j \!\in \! \mathcal J \hbox { such that } W(j) \!\subseteq \! \mathcal C ^{\prime \prime }(j), \hbox {there exists } i \!\in \! W(j) \hbox { such that } h(U(i)) < 0. \\ \end{array}\right. } \end{aligned}$$

(48)

Proof

If $W(j) \nsubseteq \mathcal C ^{\prime \prime }(j)$ for some $j \in \mathcal J$ then for $j^{\prime } \in W(j) \backslash \mathcal C ^{\prime \prime }(j)$ we have $W(j^{\prime }) \subseteq W(j)$ (see Lemma 6.9). Denote by $j^{\prime \prime }$ the sole element of the singleton $\mathcal J \cap \mathcal C ^{\prime \prime }(j^{\prime })$. Then we have $W(j^{\prime \prime }) \subseteq W(j^{\prime }) \subseteq W(j)$ (see Corollary 6.10). Hence, the statement “there exists $i \in W(j^{\prime \prime })$ such that $h(U(i))<0$” implies that “there exists $i \in W(j)$ such that $h(U(i))<0$”. Thus, the result follows from Corollary 6.11.$\square$

For (32) we have

$$\begin{aligned} \begin{aligned} W(2) = \{2\}&\subseteq \{2\} = \mathcal C ^{\prime \prime }(2), \\ W(3) = \{3,7\}&\nsubseteq \{3,4\} = \mathcal C ^{\prime \prime }(3), \\ W(5) = \{5,6,7\}&\nsubseteq \{5,6\} = \mathcal C ^{\prime \prime }(5), ~ \hbox {and} ~ \\ W(7) = \{7\}&\subseteq \{7,8\} = \mathcal C ^{\prime \prime }(7). \\ \end{aligned} \end{aligned}$$

(49)

To simplify further the condition (48), we examine in the following proposition the collection $\{ U(i) ~|~ i \in W(j) \}$, where $j \in \mathcal C ^{\prime \prime }$ is such that $\varrho ^{\mathrm{out }}(j) \cap \varrho ^{\mathrm{out }}(\mathcal C ^{\prime \prime }(j)) \ne \emptyset$ and $W(j) \subseteq \mathcal C ^{\prime \prime }(j)$.

Lemma 6.13

Assume that $(\mathcal C , \mathcal{R })$ satisfies (14). For $i, j \in \mathcal C ^{\prime \prime }$ let $U(i)$ and $W(j)$ be as in (36) and (38), respectively. Fix $j \in \mathcal C ^{\prime \prime }$ such that $\varrho ^{\mathrm{out }}(j) \cap \varrho ^{\mathrm{out }}(\mathcal C ^{\prime \prime }(j)) \ne \emptyset$ and $W(j) \subseteq \mathcal C ^{\prime \prime }(j)$. Then the sets $\{ U(i) ~|~ i \in W(j) \}$ are disjoint and $\cup _{i \in W(j)}^* U(i) = U(\mathcal C ^{\prime \prime }(j))$, where

$$\begin{aligned} U(\mathcal C ^{\prime \prime }(j))=\{ k \in \mathcal C ^{\prime \prime } ~|~ \hbox {all directed paths from } k \hbox { to } \mathcal C ^{\prime } \hbox { traverse } \mathcal C ^{\prime \prime }(j)\}. \end{aligned}$$

(50)

Proof

First we prove that the sets $\{ U(i) ~|~ i \in W(j) \}$ are disjoint. Let $i_1, i_2 \in W(j)$ be such that $i_1 \ne i_2$. Due to Lemma 6.4 $(c)$, it suffices to show that none of $U(i_1)$ and $U(i_2)$ contains the other one. Suppose by contradiction that $U(i_2) \subseteq U(i_1) \backslash \{i_1\}$. Let $P_j \in \overrightarrow{i_2,j}$ and $P_\mathcal{C ^{\prime }} \in \overrightarrow{i_2,\mathcal C ^{\prime }}$ be such that $V[P_j] \cap V[P_\mathcal{C ^{\prime }}] = \{i_2\}$ (see Proposition 6.8). Since $i_2 \in U(i_1)$ by our hypothesis ($i_2 \in U(i_2)$ by Lemma 6.4 $(a)$), we have $i_1 \in V[P_\mathcal{C ^{\prime }}]$. Since $i_1 \ne i_2$, we have $i_1 \notin V[P_j]$. Let $P \in \overrightarrow{j,\mathcal C ^{\prime }}$ be such that $V[P] \cap \mathcal C ^{\prime \prime }(j) = \{j\}$ (recall that $\varrho ^{\mathrm{out }}(j) \cap \varrho ^{\mathrm{out }}(\mathcal C ^{\prime \prime }(j)) \ne \emptyset$). Then clearly $i_1 \notin V[P]$ (recall that $i_1 \in W(j) \subseteq \mathcal C ^{\prime \prime }(j)$ and the case $i_1 = j$ can trivially be excluded). Thus, $\mathrm{con }(P_j,P) \in \overrightarrow{i_2,\mathcal C ^{\prime }}$ and $i_1 \notin V[\mathrm{con }(P_j,P)]$, contradicting $i_2 \in U(i_1)$. This contradiction proves that the sets $\{ U(i) ~|~ i \in W(j) \}$ are indeed disjoint.

It is left to prove that $\cup _{i \in W(j)}^* U(i) = U(\mathcal C ^{\prime \prime }(j))$. It is obvious that $U(\mathcal C ^{\prime \prime }(j)) \in \mathcal C ^{\prime \prime }_{j-\mathrm{inarb }}$ (one may prove this similarly to the proof Lemma 6.3 $(a)$). Hence, we have $\mathcal I _{U(\mathcal C ^{\prime \prime }(j))} \subseteq W(j)$ (see (38)). Also, note that for $i \in W(j)$ we have $i \in \mathcal C ^{\prime \prime }(j)$ (recall that have we assumed in the lemma that $W(j) \subseteq \mathcal C ^{\prime \prime }(j)$). Thus, for $i \in W(j)$ we obviously have $U(i) \subseteq U(\mathcal C ^{\prime \prime }(j))$. Therefore,

$$\begin{aligned} U(\mathcal C ^{\prime \prime }(j)) = \mathop {{\bigcup }^{*}}\limits _{i \in \mathcal I _{U(\mathcal C ^{\prime \prime }(j))}} U(i) \subseteq \mathop {{\bigcup }^{*}}\limits _{i \in W(j)} U(i) \subseteq U(\mathcal C ^{\prime \prime }(j)). \end{aligned}$$

As a consequence, all the inclusions in the above chain are equality. This concludes the proof of $\cup _{i \in W(j)}^* U(i) = U(\mathcal C ^{\prime \prime }(j))$.$\square$

As a consequence, we obtain Theorem 6.14 below, which is the main result of this paper. Recall that for $i, j \in \mathcal C ^{\prime \prime }$

• $U(i)$ = {$k \in \mathcal C ^{\prime \prime } \,|\,$ all directed paths from $k$ to $\mathcal C ^{\prime }$ traverse $i$},

• $\mathcal C ^{\prime \prime }(j)$ denotes the vertex set of that strong component of $(\mathcal C , \mathcal{R })$ which contains $j$,

• $U(\mathcal C ^{\prime \prime }(j))$ = {$k \in \mathcal C ^{\prime \prime } ~|~$ all directed paths from $k$ to $\mathcal C ^{\prime }$ traverse $\mathcal C ^{\prime \prime }(j)$}, and

• $W(j)$ = {$k\in \mathcal C ^{\prime \prime }~|~$ there exist $P_j\in \overrightarrow{k,j}$ and $P_\mathcal{C ^{\prime }}\in \overrightarrow{k,\mathcal C ^{\prime }}$ such that $V[P_j]\cap V[P_\mathcal{C ^{\prime }}]=\{k\}$}.

Also, recall that $\mathcal J \subseteq \mathcal C ^{\prime \prime }$ is such that $\mathcal J$ contains precisely one element of each non-absorbing strong component of $(\mathcal C , \mathcal{R })$ and for all $j \in \mathcal J$ we have $\varrho ^{\mathrm{out }}(j) \cap \varrho ^{\mathrm{out }}(\mathcal C ^{\prime \prime }(j)) \ne \emptyset$.

Theorem 6.14

Let $(\mathcal X ,\mathcal C ,\mathcal{R })$ be a reaction network for which $\ell = t = 1$ and $\delta = 1$. Assume that $(\mathcal C ,\mathcal{R })$ is not strongly connected and let $h \in \mathbb{R }^c$ be as in (5). For $i, j \in \mathcal C ^{\prime \prime }$ let $U(i), W(j)$, and $U(\mathcal C ^{\prime \prime }(j))$ be as in (36), (38), and (50), respectively. Also, let $\mathcal J$ be as in (45). Then for all $\kappa :\mathcal{R }\rightarrow \mathbb{R }_+$ we have $E^{\kappa }_+\ne \emptyset$ if and only if

$$\begin{aligned} {\left\{ \begin{array}{ll} {\textit{for all}} \ i \in \mathcal C ^{\prime \prime } \ {\textit{we have}} \ h(U(i)) \le 0 \ {\textit{and}} \\ {\textit{for all}} \ j \in \mathcal J \ {\textit{such that}} \ W(j) \subseteq \mathcal C ^{\prime \prime }(j), {\textit{we have}} \ h(U(\mathcal C ^{\prime \prime }(j))) < 0. \\ \end{array}\right. } \end{aligned}$$

(51)

Proof

The statement follows directly from Corollary 6.12 and Lemma 6.13.$\square$

Since for (32) we have $U(\mathcal C ^{\prime \prime }(2)) = U(2)$ and $U(\mathcal C ^{\prime \prime }(7)) = U(7)$ we obtain that for all $\kappa :\mathcal{R }\rightarrow \mathbb{R }_+$ we have $E^{\kappa }_+\ne \emptyset$ if and only if

$$\begin{aligned}&h(\{2,3,4,5,6,7,8\}) < 0, h(\{3,4\}) \le 0, h(\{4\}) \le 0, h(\{5\}) \le 0, \\&h(\{6\}) \le 0, h(\{7,8\}) < 0, ~ \hbox {and} ~ h(\{8\}) \le 0. \end{aligned}$$

Since the condition $W(j) \subseteq \mathcal C ^{\prime \prime }(j)$ appeared in our main result, the rest of this section is devoted to provide an equivalent (and more transparent) condition to that. After some preparations, we will arrive to this equivalent condition in Proposition 6.16. Let us start by defining the set $\mathcal U (j)$ for $j \in \mathcal J$ by

$$\begin{aligned} \mathcal U (j) = \bigcup _{j^{\prime } \in \mathcal C ^{\prime \prime }(j)} U(j^{\prime }). \end{aligned}$$

(52)

Also, let $\mathcal U (\mathcal C ^{\prime }) = U(\mathcal C ^{\prime })$ (thus, $\mathcal U (\mathcal C ^{\prime }) = \mathcal C$). Note that for (32) we have

$$\begin{aligned} \mathcal U (2) = \{2, 3, 4, 5, 6, 7, 8\}, \mathcal U (3) = \{3, 4\}, \mathcal U (5) = \{5, 6\}, ~ \hbox {and} ~ \mathcal U (7) = \{7, 8\}. \end{aligned}$$

The following proposition states that the collection $\{\mathcal{U }(j) ~|~ j \in \mathcal{J }\}$ has a similar property as the collection $\{U(i) ~|~ i \in \mathcal{C }^{\prime \prime }\}$ has.

Proposition 6.15

Assume that $(\mathcal C , \mathcal{R })$ satisfies (14). Let $\mathcal J$ be as in (45) and for $j \in \mathcal J$ let $\mathcal U (j)$ be as in (52). Let $j_1, j_2 \in \mathcal J$ be such that $j_1 \ne j_2$. Then either $\mathcal U (j_1) \subsetneq \mathcal U (j_2)$ or $\mathcal U (j_1) \supsetneq \mathcal U (j_2)$ or $\mathcal U (j_1) \cap \mathcal U (j_2) = \emptyset$.

Proof

Suppose that $\mathcal U (j_1) \cap \mathcal U (j_2) \ne \emptyset$. Let $j_1^{\prime } \in \mathcal C ^{\prime \prime }(j_1)$ and $j_2^{\prime } \in \mathcal C ^{\prime \prime }(j_2)$ be such that $U(j_1^{\prime }) \cap U(j_2^{\prime }) \ne \emptyset$. Then, by Lemma 6.4 $(b)$ and $(iii)$, either $U(j_1^{\prime }) \subsetneq U(j_2^{\prime }) \backslash \{j_2^{\prime }\}$ or $U(j_1^{\prime }) \backslash \{j_1^{\prime }\} \supsetneq U(j_2^{\prime })$. Clearly, the two cases are symmetric. Suppose for the rest of this proof that $U(j_1^{\prime }) \subsetneq U(j_2^{\prime }) \backslash \{j_2^{\prime }\}$. Since $j_1^{\prime }$ and $j_2^{\prime }$ are not in the same strong component, this has the consequence that $\mathcal C ^{\prime \prime }(j_1) \subsetneq U(j_2^{\prime })$. Thus, by Lemma 6.4 $(b)$, we have

$$\begin{aligned} \mathcal U (j_1) = \bigcup _{j^{\prime } \in \mathcal C ^{\prime \prime }(j_1)} U(j^{\prime }) \subseteq U(j_2^{\prime }) \backslash \{j_2^{\prime }\} \subsetneq U(j_2^{\prime }) \subseteq \bigcup _{j^{\prime } \in \mathcal C ^{\prime \prime }(j_2)} U(j^{\prime }) = \mathcal U (j_2), \end{aligned}$$

which concludes the proof.$\square$

A collection $\mathcal Q$ of subsets of a set is called laminar if for all $Q_1, Q_2 \in \mathcal Q$ we have

$$\begin{aligned} Q_1 \subseteq Q_2 ~ \hbox {or} ~ Q_1 \supseteq Q_2 ~ \hbox {or} ~ Q_1 \cap Q_2 = \emptyset . \end{aligned}$$

Thus, by Lemma 6.4 $(c)$ and Proposition 6.15 both the collections

$$\begin{aligned} \{U(i) ~|~ i \in \mathcal{C }^{\prime \prime }\} \cup \{\mathcal{C }\} ~ \hbox {and} ~ \{\mathcal{U }(j) ~|~ j \in \mathcal{J }\} \cup \{\mathcal{C }\} \end{aligned}$$

(53)

are laminar. It is straightforward to associate a branching to a laminar collection $\mathcal Q$ that consists of distinct sets. The vertex set of the branching is $\mathcal Q$ itself, while for $Q_1, Q_2 \in \mathcal Q$ the ordered pair $(Q_1,Q_2)$ is an arc if $Q_1 \subseteq Q_2$ and there does not exist $Q_3 \in \mathcal Q$ such that $Q_1 \subseteq Q_3 \subseteq Q_2$. Denote by $T$ and $\mathcal T$ the arborescences associated to the laminar collections in (53), respectively (since all the other sets of these two collections are contained in $\mathcal C$, the associated branching is actually an arborescence with root $\mathcal C$). We have depicted $T$ and $\mathcal T$ associated to (32) in Fig. 2.

It is also straightforward to associate to a directed graph $D = (V,A)$ an acyclic directed graph, denoted by ${\mathfrak{T }}_D$, in the following way. Denote by $V^1,\ldots ,V^k$ the vertex sets of the strong components of $D$. The vertex set of $\mathfrak{T }_D$ is then $\{V^1, \ldots , V^k\}$, while for $k_1, k_2 \in \{1, \ldots , k\}$ such that $k_1 \ne k_2$, the ordered pair $(V^{k_1}, V^{k_2})$ is an arc of $\mathfrak{T }_D$ if $\varrho ^{\mathrm{out }}_D(V^{k_1}) \cap \varrho ^{\mathrm{in }}_D(V^{k_2}) \ne \emptyset$. We will simply denote by $\mathfrak{T }$ the acyclic directed graph $\mathfrak{T }_{(\mathcal{C },{\mathcal{R }})}$. Thus, the vertex set of $\mathfrak{T }$ is $\{\mathcal{C }^{\prime \prime }(j) ~|~ j \in \mathcal{J }\} \cup \{\mathcal{C }^{\prime }\}$. We have depicted $\mathfrak{T }$ associated to (32) in Fig. 2.

Fig. 2

The arborescences $T$ and $\mathcal{T }$ associated to the laminar families (53) and the acyclic directed graph $\mathfrak{T }$ for (32)

For the sake of simplicity, we perform some natural identifications. We identify from this point on the vertex sets of $T, {\mathcal{T }}$, and ${\mathfrak{T }}$ with the sets ${\mathcal{C }}^{\prime \prime } \cup \{\mathcal{C }^{\prime }\}, {\mathcal{J }} \cup \{\mathcal{C }^{\prime }\}$, and ${\mathcal{J }} \cup \{\mathcal{C }^{\prime }\}$, respectively (recall that $U({\mathcal{C }}^{\prime }) = {\mathcal{C }}$ and ${\mathcal{U }}({\mathcal{C }}^{\prime }) = {\mathcal{C }}$). With these identifications, the arborescence ${\mathcal{T }}$ and the acyclic directed graph $\mathfrak{T }$ has the same vertex set, which makes it possible to depict them at once. We have depicted $T, \mathcal T$, and $\mathfrak{T }$ considering these identifications in Fig. 3.

Fig. 3

The arborescences $T$ and $\mathcal T$ associated to the laminar families (53) and the acyclic directed graph $\mathfrak{T }$ for (32) considering the straightforward identifications of the vertex sets

The following proposition states that for $j \in \mathcal J$ the condition $W(j) \subseteq \mathcal C ^{\prime \prime }(j)$ can be expressed in terms of $\mathcal T$ and $\mathfrak{T }$. For a directed graph $D = (V, A)$ and $j \in V$ let us denote by $R_D(j)$ the set of vertices from which it is possible to reach $j$ in $D$, i.e.,

$$\begin{aligned} R_D(j) = \{ \widetilde{j} \in V ~|~ \hbox {there exists a directed path from } \widetilde{j} \hbox { to } j \hbox { in } D\}. \end{aligned}$$

(54)

It is trivial that for all $j \in \mathcal J$ we have $R_\mathcal{T }(j) \subseteq R_\mathfrak{T }(j)$.

Proposition 6.16

Assume that $(\mathcal C , \mathcal{R })$ satisfies (14). Let $\mathcal J$ be as in (45) and for $j \in \mathcal C ^{\prime \prime }$ let $W(j)$ be as in (38). Also, let the arborescence $\mathcal T$ and acyclic directed graph $\mathfrak{T }$ be as above. Fix $j \in \mathcal J$. Then $W(j) \subseteq \mathcal C ^{\prime \prime }(j)$ if and only if $R_\mathcal{T }(j) = R_\mathfrak{T }(j)$, where $R_\mathcal{T }(j)$ and $R_\mathfrak{T }(j)$ are understood in accordance with (54).

Proof

Assume first that $R_\mathcal{T }(j) = R_\mathfrak{T }(j)$ and suppose by contradiction that $W(j) \backslash \mathcal C ^{\prime \prime }(j) \ne \emptyset$. Let $i \in W(j) \backslash \mathcal C ^{\prime \prime }(j), P_j \in \overrightarrow{i,j}$, and $P_\mathcal{C ^{\prime }} \in \overrightarrow{i,\mathcal C ^{\prime }}$ be such that $V[P_j] \cap V[P_\mathcal{C ^{\prime }}] = \{i\}$ (see Proposition 6.8). Also, let $P \in \overrightarrow{j,\mathcal C ^{\prime }}$ be such that $V[P] \cap \mathcal C ^{\prime \prime }(j) = \{j\}$ (recall that $\varrho ^{\mathrm{out }}(j) \cap \varrho ^{\mathrm{out }}(\mathcal C ^{\prime \prime }(j)) \ne \emptyset$). Then both $P_\mathcal{C ^{\prime }}$ and $\mathrm{con }(P_j,P)$ are directed paths from $i$ to $\mathcal C ^{\prime }$ and these two cannot have any common vertex in $\mathcal C ^{\prime \prime }(j)$. Thus, there does not exist $j^{\prime } \in \mathcal C ^{\prime \prime }(j)$ such that $i \in U(j^{\prime })$, and consequently $i \notin \mathcal U (j)$. Let $\overline{j} \in \mathcal J$ be such that $i \in \mathcal C ^{\prime \prime }(\overline{j})$. Then $\overline{j} \in R_\mathfrak{T }(j)$ and $\overline{j} \notin R_\mathcal{T }(j)$, which contradicts $R_\mathcal{T }(j) = R_\mathfrak{T }(j)$.

To show the other direction, assume that $W(j) \subseteq \mathcal C ^{\prime \prime }(j)$ and suppose by contradiction $i \in \mathcal C ^{\prime \prime }$ is such that $\overrightarrow{i,j} \ne \emptyset$ and there does not exist $j^{\prime } \in \mathcal C ^{\prime \prime }(j)$ such that $i \in U(j^{\prime })$. Moreover, assume that $i$ is such that $\overrightarrow{p_T(i),j} = \emptyset$, where $p_T(i) \in \mathcal C$ is the parent of $i$ in $T$ (i.e., $p_T(i)$ is the second vertex on the unique directed path from $i$ to $\mathcal C ^{\prime }$ in $T$). Since $i \in U(i)$, it follows that $i \notin \mathcal C ^{\prime \prime }(j)$. We will show that $i \in W(j)$, which will thus contradict $W(j) \subseteq \mathcal C ^{\prime \prime }(j)$. To show the inclusion $i \in W(j)$, note that the set $\{ i^{\prime } \in \mathcal C ^{\prime \prime } \backslash \{i\} ~|~ i \in U(i^{\prime })\}$ coincides with $V[P] \backslash \{i, \mathcal C ^{\prime }\}$, where $P$ is the unique directed path from $i$ to $\mathcal C ^{\prime }$ in $T$. However, by our assumption on $i$, for all $i^{\prime } \in V[P] \backslash \{i, \mathcal C ^{\prime }\}$ we have $\overrightarrow{i^{\prime },j} = \emptyset$. Thus, taking also into account Proposition 6.8 and (43) in the proof of that proposition, we obtain that $i \in W(j)$. This concludes the proof.$\square$

For the reaction network (32) we have

$$\begin{aligned} R_\mathcal{T }(2)&= \{2, 3, 5, 7\} = \{2, 3, 5, 7\} = R_\mathfrak{T }(2), \\ R_\mathcal{T }(3)&= \{3\} \subsetneq \{3, 7\} = R_\mathfrak{T }(3), \\ R_\mathcal{T }(5)&= \{5\} \subsetneq \{5, 7\} = R_\mathfrak{T }(5), \, \hbox {and} \, \\ R_\mathcal{T }(7)&= \{7\} = \{7\} = R_\mathfrak{T }(7), \end{aligned}$$

which is indeed in accordance with (49).

We conclude this section by some remarks on the collection $\{U(i) ~|~ i \in {\mathcal{C }}^{\prime \prime }\} \cup \{\mathcal{C }\}$. First, note that not only $\{U(i) ~|~ i \in {\mathcal{C }}^{\prime \prime }\} \cup \{\mathcal{C }\}$ determines $T$, but also conversely. Indeed, it is obvious that $U(i) = R_T(i)$ for all $i \in {\mathcal{C }}$. In graph theory, if $j \in U(i)$ then we say that $i$ postdominates $j$. The arborescence $T$ is called the postdominator tree. See e.g. [19] for more on algorithmic issues concerning the dominator/postdominator tree.

Appendices

Appendix A: Some basic notions from the theory of directed graphs

We collect in this section those standard concepts and notations from graph theory that are used throughout this paper. The notions are taken from [24, Sections 3.2, 9.1, and 10.1].

Let $D=(V,A)$ be a directed graph without multiple arcs throughout this section.

For $i_0, i_1, \ldots , i_l \in V$ with $l \in \mathbb{Z }_{\ge 0}$, we say that $P = (i_0, i_1, \ldots , i_l)$ is a directed walk from $i_0$ to $i_l$, or just a directed walk, if $(i_k, i_{k+1}) \in A$ for all $k \in \{0, 1, \ldots , l-1\}$. The length of a directed walk $P = (i_0, i_1, \ldots , i_l)$, denoted by ${\mathrm{len}}(P)$, is $l$. For a directed walk $P = (i_0, i_1, \ldots , i_l)$, we denote by $V[P]$ the vertex set $\{i_0, i_1, \ldots , i_l\}$ (we use the notation $V[P]$ even if the vertex set of the directed graph in question is denoted by some other symbol than $V$). If $i \in V[P]$ for a directed walk $P$ then we say that $P$ traverses $i$, while if $i \notin V[P]$ then we say that $P$ avoids $i$. One can define traversing and avoiding a set $U \subseteq V$ similarly. A directed walk $P = (i_0, i_1, \ldots , i_l)$ is said to be a directed path if $i_0, i_1, \ldots , i_l$ are all distinct. For $i, j \in V$, we denote by $\overrightarrow{i,j}$ the set of directed paths from $i$ to $j$. For a directed path $P = (i_0, i_1, \ldots , i_l)$ and $0 \le k \le m \le l$ we denote by $P^{i_k:i_m}$ the directed path $(i_k, i_{k+1}, \ldots , i_m)$. A directed walk $P = (i_0, i_1, \ldots , i_l)$ is said to be a directed circuit if $l \ge 1, i_0 = i_l$, and $i_0, i_1, \ldots , i_{l-1}$ are all distinct.

For the directed walks $P_1 = (i_0, i_1, \ldots , i_l)$ and $P_2 = (j_0, j_1, \ldots , j_k)$ with $i_l = j_0$, we denote by $\mathrm{con }(P_1,P_2)$ their concatenation, which is defined by $\mathrm{con }(P_1,P_2) = (i_0, \ldots , i_l, j_1, \ldots , j_k)$. Clearly, $\mathrm{con }(P_1,P_2)$ is then a directed walk from $i_0$ to $j_k$.

The directed graph $D$ is called strongly connected if for all $i, j \in V$ we have $\overrightarrow{i,j} \ne \emptyset$, while it is called weakly connected if the underlying undirected graph is connected. The maximal strongly connected subgraphs of $D$ are called the strong components of $D$, while the maximal weakly connected subgraphs of $D$ are called the weak components of $D$. An absorbing strong component of $D$ is a strong component such that there is no arc, which leaves it.

The above definitions are in accordance with the ones in [24, Section 3.2], with the only difference that we have defined a directed walk as a sequence of vertices rather than an alternating sequence of vertices and arcs. This choice is made here, because it suffices all our purposes in this paper if we restrict our attention to directed graphs without multiple arcs.

We use a corollary of the following theorem several times in Sect. 6. See [24, Corollary 9.1a] for a proof of Menger’s Theorem.

Theorem 7.1

(Menger’s Theorem [24]) Let $D = (V,A)$ be a directed graph and let $s$ and $t$ be two nonadjacent vertices of $D$. Then the maximum number of internally vertex-disjoint $s - t$ paths is equal to the minimum size of an $s - t$ vertex-cut.

For $U \subseteq V$, the set of arcs, which enter $U$ and leave $U$ are defined by

$$\begin{aligned} \varrho ^{\mathrm{in }}_D(U)&= \{ (i,j) \in A ~|~ i \in V \backslash U, j \in U \}~\hbox {and} \\ \varrho ^{\mathrm{out }}_D(U)&= \{ (i,j) \in A ~|~ i \in U, j \in V \backslash U \}, \end{aligned}$$

respectively. Denote by $2^V$ the power set of V. For a function $z : A \rightarrow \mathbb{R }$, define the function $\hbox \mathrm{excess}_z:2^V\rightarrow \mathbb{R }$ by

$$\begin{aligned} \hbox \mathrm{excess}_z(U) = z(\varrho ^{\mathrm{in }}(U)) - z(\varrho ^{\mathrm{out }}(U))~~(U\subseteq V), \end{aligned}$$

where $z(\varrho ^{\mathrm{in }}(U))$ and $z(\varrho ^{\mathrm{out }}(U))$ are understood in accordance with (1). For $i\in V$ we use the notations $\varrho ^{\mathrm{in }}(i),\varrho ^{\mathrm{out }}(i)$, and $\hbox \mathrm{excess}_z(i)$ instead of $\varrho ^{\mathrm{in }}(\{i\}),\varrho ^{\mathrm{out }}(\{i\})$, and $\hbox \mathrm{excess}_z(\{i\})$, respectively. Note that $\hbox \mathrm{excess}_z(V) = \hbox \mathrm{excess}_z(\emptyset ) = 0$.

An important and frequently used observation is that

$$\begin{aligned} \hbox \mathrm{excess}_z(U) = \sum _{i\in U} \hbox \mathrm{excess}_z(i) ~ \hbox {for all} ~ U \subseteq V. \end{aligned}$$

(55)

Thus, the excess function satisfies (1).

For a function $h : V \rightarrow \mathbb{R }$, a function $z : A \rightarrow \mathbb{R }$ is called an $h$-transshipment if $\hbox \mathrm{excess}_z = h$.

Let us define $\mathcal A _{D}(U)$ and $\mathcal T _{D}(U)$ by

$$\begin{aligned} \mathcal A _{D}(U)&= \left\{ \widetilde{A} \subseteq A ~\bigg |~ \begin{array}{l} |\varrho ^{\mathrm{out }}_{(V,\widetilde{A})}(k)|=0 \quad \hbox {for all} ~ k \in U ~ \hbox {and} \\ |\varrho ^{\mathrm{out }}_{(V,\widetilde{A})}(k)| = 1 \quad \hbox {for all} ~ k \in V \backslash U \\ \end{array} \right\} ~ \hbox {and} \end{aligned}$$

(56)

$$\begin{aligned} \mathcal T _{D}(U)&= \{ \widetilde{A} \in \mathcal A _D(U) ~|~ (V,\widetilde{A}) ~ \hbox {is acyclic}\}, \end{aligned}$$

(57)

respectively. (A directed graph is called acyclic if it has no directed circuits.) The elements of $\mathcal T _D(U)$ are called $U$-branchings in $D$ (or more precisely $U$-inbranchings in $D$), the set $U$ being called the root set. If $U$ is the singleton $\{j\}$ for some $j \in V$ then a $U$-branching $\widetilde{A}$ is called a $j$-arborescence (or more precisely a $j$-inarborescence). Clearly, if $U = \{j_1, \ldots , j_k\}$ for some positive integer $k$ then for a $U$-branching $\widetilde{A}, (V,\widetilde{A})$ has $k$ weak components, each of them is corresponding to an element of $U$. Denote these weak components by $(V^{j_1},\widetilde{A}^{j_1}), \ldots ,(V^{j_k},\widetilde{A}^{j_k})$. Then $\widetilde{A}^j$ is a $j$-arborescence in the directed graph $(V^j,\{(i, i^{\prime }) \in A ~|~ i, i^{\prime } \in V^j\})$ for all $j \in U$. See Fig. 4 for an illustration of these notions.

Fig. 4

A directed graph $D$ with vertex set $\{1, \ldots , 12\}$ (on the left) and two elements of $\mathcal A _D(\{1,2,3,8\})$ (in the middle and on the right). The one in the middle is not acyclic, and hence, it does not belong to $\mathcal T _D(\{1,2,3,8\})$, while the one on the right is acyclic, so that one is a $\{1,2,3,8\}$-branching in $D$. It is also apparent that the latter one can be decomposed into four arborescences, the roots of these four arborescences are $1, 2, 3$, and $8$, respectively

We also use the following notations in Sects. 6 and 9.2. For $i, j \in V$ let us define $\mathcal A ^{ij}_{D}(U)$ and $\mathcal T ^{ij}_{D}(U)$ by

$$\begin{aligned} \mathcal A ^{ij}_{D}(U)&= \{ \widetilde{A} \in \mathcal A _{D}(U) ~|~ \hbox {there exists a directed path from} \ i \hbox { to } j \hbox { in} (V,\widetilde{A}) \} ~ \hbox {and} \qquad \end{aligned}$$

(58)

$$\begin{aligned} \mathcal T ^{ij}_{D}(U)&= \{ \widetilde{A} \in \mathcal T _{D}(U) ~|~ \hbox {there exists a directed path from} \ i \hbox { to } j \hbox { in} (V,\widetilde{A}) \},\qquad \end{aligned}$$

(59)

respectively.

Appendix B: Proof of Theorem 5.1

The aim of this section is to prove Theorem 5.1. The main tool we will use in that proof is the following theorem (see [24, Corollary 11.2f]), which is a well-known consequence of the Hoffman’s Theorem (see [24, Theorem 11.2]).

Theorem 8.1

Let $D = (V,A)$ be a directed graph, let $d,c: A \rightarrow \mathbb{R }$ with $d \le c$ and let $h: V \rightarrow \mathbb{R }$ with $h(V) = 0$. Then there exists an $h$-transshipment $z$ with $d \le z \le c$ if and only if

$$\begin{aligned} c(\varrho ^{\mathrm{in }}(U)) - d(\varrho ^{\mathrm{out }}(U)) \ge h(U) ~ \hbox {for all} ~ U \subseteq V. \end{aligned}$$

Note that Theorem 5.1 characterises the existence of a positive $h$-transshipment for a function $h : V \rightarrow \mathbb{R }$ with $h(V) = 0$. Compare this to the characterisation of the existence of a nonnegative $h$-transshipment (see [24, Corollary 11.2h]).

Proof of Theorem 5.1

To show that (21) is necessary, let $z: A \rightarrow \mathbb{R }_+$ be an $h$-transshipment and $\emptyset \ne U \subsetneq V$ with $\varrho ^{\mathrm{in }}(U) = \emptyset$. Then

$$\begin{aligned} h(U) = \hbox \mathrm{excess}_z(U) = z(\varrho ^{\mathrm{in }}(U)) - z(\varrho ^{\mathrm{out }}(U)) = - z(\varrho ^{\mathrm{out }}(U)) < 0, \end{aligned}$$

where the inequality holds, because $\varrho ^{\mathrm{out }}(U)$ and $\varrho ^{\mathrm{in }}(U)$ cannot be empty at the same time ($D$ is assumed to be weakly connected and $\emptyset \ne U \subsetneq V$) and the values of $z$ are positive.

To show the sufficiency of (21), assume for the rest of this proof that (21) holds. Clearly, the existence of a positive $h$-transshipment is equivalent to the existence of $0 < \varepsilon \le K$ such that there exists an $h$-transshipment $z$ with $\varepsilon \le z \le K$. By Theorem 8.1, the latter is equivalent to the existence of $0 < \varepsilon \le K$ such that

$$\begin{aligned} K |\varrho ^{\mathrm{in }}(U)| - \varepsilon |\varrho ^{\mathrm{out }}(U)| \ge h(U) ~ \hbox {for all} ~ U \subseteq V. \end{aligned}$$

(60)

Let

$$\begin{aligned} \varepsilon&= \min \left( \left\{ - \frac{h(U)}{|\varrho ^{\mathrm{out }}(U)|} ~\bigg |~ \emptyset \ne U \subsetneq V ~ \hbox {and} ~ \varrho ^{\mathrm{in }}(U) = \emptyset \right\} \cup \{ 1 \} \right) ~ \hbox {and} \end{aligned}$$

(61)

$$\begin{aligned} K&= \max \left( \left\{ \frac{h(U) + \varepsilon |\varrho ^{\mathrm{out }}(U)|}{|\varrho ^{\mathrm{in }}(U)|} ~\bigg |~ \emptyset \ne U \subsetneq V ~ \hbox {and} ~ \varrho ^{\mathrm{in }}(U) \ne \emptyset \right\} \cup \{ \varepsilon \} \right) . \end{aligned}$$

(62)

Note that $\varepsilon > 0$ is guaranteed by (21). Also, we have $\varepsilon \le K$. We show that (60) holds with these specific choices of $\varepsilon$ and $K$.

Both for $U = \emptyset$ and $U = V$ we have $\varrho ^{\mathrm{in }}(U) = \varrho ^{\mathrm{out }}(U) = \emptyset$ and $h(U) = 0$, hence (60) holds in both cases.

Fix for the rest of this proof $\emptyset \ne U \subsetneq V$. In case $\varrho ^{\mathrm{in }}(U) = \emptyset$, (60) is a consequence of (61), while in case $\varrho ^{\mathrm{in }}(U) \ne \emptyset$, (60) follows from (62).

Appendix C: The Matrix-Tree Theorem

There are several versions of the Matrix-Tree Theorem. The one we present in Sect. 9.2 appears in [23, Appendix] as a tool for proving the Markov Chain Tree Theorem. This is slight generalization of Tutte’s result (see [27, Theorem 3.6]), while it is a special case of the All Minors Matrix Tree Theorem (see [5]). The previous applications of the Matrix-Tree Theorem in CRNT used Tutte’s version (see [6, 11, 17, 18, 22, 26]), while we need a slightly more general variation in Sect. 6. We also provide a direct and elementary proof of the Matrix-Tree Theorem in Sect. 9.2, which was worked out by György Michaletzky and the author of this paper.

1.1 A lemma on the number of inversions in bijections

In the proof of the Matrix-Tree Theorem, we use a purely algebraic lemma, which is a special case of a result in [5]. For the sake of completeness, we also present the proof of this lemma.

Fix a positive integer $n$ for this subsection. Let $W_1$ and $W_2$ be nonempty subsets of $V = \{1, \ldots , n\}$ such that $|W_1| = |W_2|$. For a bijection $\pi : W_1 \rightarrow W_2$, we say that $k \in W_1$ and $k^{\prime } \in W_1$ are in inversion if $k < k^{\prime }$ and $\pi (k) > \pi (k^{\prime })$. Denote by $\nu (\pi )$ the number of inversions in $\pi$, i.e.,

$$\begin{aligned} \nu (\pi ) = |\{(k,k^{\prime }) \in W_1 \times W_1 ~|~ k < k^{\prime } ~ \hbox {and} ~ \pi (k) > \pi (k^{\prime })\}|. \end{aligned}$$

As usual, define the sign ${\mathrm{sgn}}(\pi )$ of the bijection $\pi$ by ${\mathrm{sgn}}(\pi ) = (-1)^{\nu (\pi )}$.

Lemma 9.1

Let $i,j \in V$. Let $\sigma : V \backslash \{j\} \rightarrow V \backslash \{i\}$ be a bijection and define the permutation $\overline{\sigma } : V \rightarrow V$ by

$$\begin{aligned} \overline{\sigma }(k) = {\left\{ \begin{array}{ll} \sigma (k), &{} \hbox {if}~k \in V \backslash \{j\}, \\ i, &{} \hbox {if}~k = j \\ \end{array}\right. } (k \in V). \end{aligned}$$

Then ${\mathrm{sgn}}(\overline{\sigma }) = (-1)^{i+j} {\mathrm{sgn}}(\sigma )$.

Proof

We prove this lemma by induction on $j$. To prove the initial step of the induction, let $j=1$. Clearly, $\overline{\sigma }$ inherits all the inversions of $\sigma$. Also, since $\overline{\sigma }(1) = i$, there are exactly $i-1$ elements in $V \backslash \{1\}$ that are in inversion with $1$ under $\overline{\sigma }$. Hence, $\nu (\overline{\sigma }) = \nu (\sigma ) + (i-1)$. As a consequence,

$$\begin{aligned} {\mathrm{sgn}}(\overline{\sigma }) = (-1)^{\nu (\overline{\sigma })} = (-1)^{\nu (\sigma ) + (i-1)} = (-1)^{i-1} (-1)^{\nu (\sigma )} = (-1)^{i+1} {\mathrm{sgn}}(\sigma ). \end{aligned}$$

To prove the inductive step, fix $2 \le j \le n$ and assume that the lemma holds with $j-1$ instead of $j$. Let us define $\pi : V \backslash \{j-1\} \rightarrow V \backslash \{i\}$ by

$$\begin{aligned} \pi (k) = {\left\{ \begin{array}{ll} \sigma (k), &{} \hbox {if} ~ k \in V \backslash \{j-1,j\}, \\ \sigma (j-1), &{} \hbox {if} ~ k = j \\ \end{array}\right. } (k \in V \backslash \{j-1\}). \end{aligned}$$

Clearly, we have $\nu (\pi ) = \nu (\sigma )$. Also, let us define $\overline{\pi } : V \rightarrow V$ by

$$\begin{aligned} \overline{\pi }(k) = {\left\{ \begin{array}{ll} \pi (k), &{} \hbox {if} ~ k \in V \backslash \{j-1\}, \\ i, &{} \hbox {if} ~ k = j-1 \\ \end{array}\right. } (k \in V). \end{aligned}$$

Note that we have defined $\overline{\pi }$ in such a way that $\overline{\pi }|_{V \backslash \{j-1, j\}} = \overline{\sigma }|_{V \backslash \{j-1, j\}}, \overline{\pi }(j) = \overline{\sigma }(j-1)$, and $\overline{\pi }(j-1) = \overline{\sigma }(j) = i$. Thus, for $k, k^{\prime } \in V$ such that $k < k^{\prime }$ we have

$$\begin{aligned} \overline{\pi }(k) > \overline{\pi }(k^{\prime }) ~ \hbox {if and only if} ~ {\left\{ \begin{array}{ll} \overline{\sigma }(k) > \overline{\sigma }(k^{\prime }), &{} \hbox {if} ~ k, k^{\prime } \in V \backslash \{j-1, j\}, \\ \overline{\sigma }(k) > \overline{\sigma }(j-1), &{} \hbox {if} ~ k \in \{1, \ldots , j-2\}, k^{\prime } = j, \\ \overline{\sigma }(k) > \overline{\sigma }(j), &{} \hbox {if} ~ k \in \{1, \ldots , j-2\}, k^{\prime } = j-1, \\ \overline{\sigma }(j-1) > \overline{\sigma }(k^{\prime }), &{} \hbox {if} ~ k = j, k^{\prime } \in \{j+1, \ldots , n\}, \\ \overline{\sigma }(j) \!> \!\overline{\sigma }(k^{\prime }), &{} \hbox {if} ~ k \!=\! j-1, k^{\prime } \in \{j\!+\!1, \ldots , n\}, ~\hbox {and} \\ \overline{\sigma }(j-1) < \overline{\sigma }(j), &{} \hbox {if} ~ k =j-1, k^{\prime } = j. \\ \end{array}\right. } \end{aligned}$$

Hence,

$$\begin{aligned} \nu (\overline{\pi }) = {\left\{ \begin{array}{ll} \nu (\overline{\sigma }) + 1, &{} \hbox {if} ~ \overline{\sigma }(j-1) < \overline{\sigma }(j), \\ \nu (\overline{\sigma }) - 1, &{} \hbox {if} ~ \overline{\sigma }(j-1) > \overline{\sigma }(j). \\ \end{array}\right. } \end{aligned}$$

(63)

Therefore,

$$\begin{aligned} {\mathrm{sgn}}(\overline{\sigma }) = (-1)^{\nu (\overline{\sigma })} \mathop {=}^{(63)} -(-1)^{\nu (\overline{\pi })} = -(-1)^{i + (j-1)} {\mathrm{sgn}}(\pi ) = (-1)^{i+j} {\mathrm{sgn}}(\sigma ), \end{aligned}$$

where we used the inductive hypothesis for $\overline{\pi }$. This concludes the proof.$\square$

The following corollary is a direct consequence of Lemma 9.1.

Corollary 9.2

Let $Q \subseteq V$ and $i,j \in V \backslash Q$. Let $\sigma : V \backslash (Q \cup \{j\}) \rightarrow V \backslash (Q \cup \{i\})$ be a bijection and define the permutation $\overline{\sigma } : V \backslash Q \rightarrow V \backslash Q$ by

$$\begin{aligned} \overline{\sigma }(k) = {\left\{ \begin{array}{ll} \sigma (k), &{} \hbox {if}~k \in V \backslash (Q \cup \{j\}), \\ i, &{} \hbox {if}~k = j \\ \end{array}\right. } (k \in V \backslash Q). \end{aligned}$$

Then ${\mathrm{sgn}}(\overline{\sigma }) = (-1)^{i+j} {\mathrm{sgn}}(\sigma )$.

1.2 The Matrix-Tree Theorem

Fix a positive integer $n$ for this subsection. Associate to a matrix $Z=(z_{ij})_{i,j=1}^n \in \mathbb{R }^{n\times n}$ the directed graph $D(Z) = (V(Z), A(Z))$, where $V(Z)=\{1,\ldots ,n\}$ and $A(Z)=\{(i,j)\in V(Z) \times V(Z)~|~z_{ij}\ne 0\}$. Also, for $Q_1, Q_2 \subseteq \{1,\ldots ,n\}$ with $|Q_1| = |Q_2|$, denote by $d_{Q_1, Q_2}(Z)$ the determinant of that matrix, which is obtained from $Z$ by deleting the rows with index in $Q_1$ and the columns with index in $Q_2$.

Theorem 9.3

(Matrix-Tree Theorem) Let $Z=(z_{ij})_{i,j=1}^n\in \mathbb{R }^{n\times n}$ be a matrix that satisfy

$$\begin{aligned} \sum _{j=1}^n z_{ij} = 0 \quad \hbox {for all} ~ i \in \{1, \ldots , n\}. \end{aligned}$$

(64)

Fix $Q \subseteq \{1,\ldots ,n\}$ and $i, j \in \{1,\ldots ,n\} \backslash Q$. Then

$$\begin{aligned} d_{Q \cup \{j\}, Q \cup \{i\}}(Z)=(-1)^{i+j} (-1)^{n-|Q|-1} \sum _{\widetilde{A} \in \mathcal T ^{ij}_{D(Z)}(Q \cup \{j\})} z_{\widetilde{A}}, \end{aligned}$$

where $\mathcal T ^{ij}_{D(Z)}(Q \cup \{j\})$ is understood as in (59) and the symbol $z_{\widetilde{A}}$ is a shorthand notation for the product $\prod _{a \in \widetilde{A}} z_a$.

Proof

For shorthand notation, let us denote by $S_{ij}$ the set of bijections from $V \backslash (Q \cup \{j\})$ to $V \backslash (Q \cup \{i\})$. For an element $\sigma$ of $S_{ij}$, denote by $\overline{\sigma }$ the permutation of $V \backslash Q$, which is defined by

$$\begin{aligned} \overline{\sigma }(k) = {\left\{ \begin{array}{ll} \sigma (k), &{} \hbox {if}~k \in V \backslash (Q \cup \{j\}), \\ i, &{} \hbox {if}~k = j \\ \end{array}\right. } (k \in V \backslash Q). \end{aligned}$$

Since $\overline{\sigma }$ is a permutation, we may consider its decomposition into disjoint cyclic permutations. This also yields a decomposition of $\sigma$ into cyclic permutations and a “ path bijection” from $i$ to $j$, where the “ path bijection” is coming from the “ deletion” of the assignment $j \mapsto i$ from $\overline{\sigma }$. Denote by

See (65) for an illustration of this decomposition. For this specific example, we have $p_{\sigma }=2$ and $q_{\sigma }=3$.

(65)

For notational convenience, we denote by $z_{h^{\sigma }}$ and $z_{f_l^{\sigma }}$ the product of those entries of $Z$ that correspond to the arcs of the directed path $h^{\sigma }$ and the directed circuit $f_l^{\sigma }$, respectively. (Thus, we implicitly identify the bijections $h^{\sigma }$ and $f_l^{\sigma }$ with the corresponding directed path and directed circuit, respectively.) Also, we identify $g_l^{\sigma }$ with the respective vertex, and thus $z_{g_l^{\sigma },g_l^{\sigma }}$ is the corresponding diagonal entry of $Z$. Then

$$\begin{aligned}&d_{Q \cup \{j\}, Q \cup \{i\}}(Z) = \sum _{\sigma \in S_{ij}} \left[ {\mathrm{sgn}}(\sigma ) \cdot \left( \prod _{k \in V \backslash (Q \cup \{j\})} z_{k,\sigma (k)} \right) \right] \\&\qquad \qquad \qquad \qquad \,\,= \sum _{\sigma \in S_{ij}} \left[ {\mathrm{sgn}}(\sigma ) \cdot z_{h^{\sigma }} \cdot \left( \prod _{l=1}^{p_{\sigma }} z_{f^{\sigma }_l} \right) \cdot \left( \prod _{l=1}^{q_{\sigma }} z_{g_l^{\sigma },g_l^{\sigma }} \right) \right] \\&\qquad \qquad \qquad \qquad \,\,{\mathop {=}\limits ^{(64)}} \sum _{\sigma \in S_{ij}} \left[ {\mathrm{sgn}}(\sigma ) \cdot z_{h^{\sigma }} \cdot \left( \prod _{l=1}^{p_{\sigma }}z_{f^{\sigma }_l} \right) \cdot \left( \prod _{l=1}^{q_{\sigma }}\left\{ -\sum _{k\in V \backslash \{g^{\sigma }_l\}} z_{g^{\sigma }_l,k} \right\} \right) \right] \\&\qquad \qquad \qquad \qquad \,\,= \sum _{\sigma \in S_{ij}} \left[ {\mathrm{sgn}}(\sigma ) \cdot (-1)^{q_{\sigma }} \cdot \left( \sum _{\widetilde{A} \in \mathcal A _{D(Z)}^{ij,\sigma }(Q \cup \{j\})} z_{\widetilde{A}} \right) \right] \\&\qquad \qquad \qquad \qquad \,\,= \sum _{\widetilde{A} \in \mathcal A _{D(Z)}^{ij}(Q \cup \{j\})} z_{\widetilde{A}} \left[ \sum _{\begin{array}{c} \sigma \in S_{ij} \\ h^{\sigma } = h^{\widetilde{A}} \\ f^{\sigma }_1,\ldots , f^{\sigma }_{p_{\sigma }} \subseteq \widetilde{A} \\ \end{array}} {\mathrm{sgn}}(\sigma ) \cdot (-1)^{q_{\sigma }} \right] , \end{aligned}$$

where $h^{\widetilde{A}}$ is the unique directed path from $i$ to $j$ in $(V,\widetilde{A})$ and

$$\begin{aligned} \mathcal A _{D(Z)}^{ij,\sigma }(Q \cup \{j\}) = \left\{ \widetilde{A} \in \mathcal A _{D(Z)}^{ij}(Q \cup \{j\}) ~\bigg |~ \begin{array}{l} f^{\sigma }_1, \ldots , f^{\sigma }_{p_{\sigma }} \subseteq \widetilde{A} ~ \hbox {and the unique directed} \\ \hbox {path from } i \hbox { to } j \hbox { in } (V,\widetilde{A}) \hbox { is given by } h^{\sigma } \\ \end{array}\right\} \end{aligned}$$

(recall (58)). Fix $\widetilde{A} \in \mathcal A _{D(Z)}^{ij}(Q \cup \{j\})$ for the rest of this proof. We claim that

$$\begin{aligned} \sum _{\begin{array}{c} \sigma \in S_{ij} \\ h^{\sigma } = h^{\widetilde{A}} \\ f^{\sigma }_1,\ldots , f^{\sigma }_{p_{\sigma }} \subseteq \widetilde{A} \\ \end{array}} {\mathrm{sgn}}(\sigma ) \cdot (-1)^{q_{\sigma }} = \left\{ \begin{array}{l@{\quad }l} 0, &{} \hbox {if}~\widetilde{A} \notin \mathcal T _{D(Z)}^{ij}(Q \cup \{j\}), \\ (-1)^{i+j}(-1)^{n-|Q|-1}, &{} \hbox {if}~\widetilde{A} \in \mathcal T _{D(Z)}^{ij}(Q \cup \{j\}). \\ \end{array}\right. \nonumber \\ \end{aligned}$$

(66)

By Corollary 9.2,

$$\begin{aligned} {\mathrm{sgn}}(\sigma )&= (-1)^{i+j} {\mathrm{sgn}}(\overline{\sigma })= (-1)^{i+j} (-1)^{{\mathrm{len}}(h^{\sigma })} (-1)^{\sum _{l=1}^{p_{\sigma }} ({\mathrm{len}}(f_l^{\sigma }) - 1)} \nonumber \\&= (-1)^{i+j} (-1)^{n-|Q|-1-p_{\sigma }-q_{\sigma }}. \end{aligned}$$

(67)

Thus, ${\mathrm{sgn}}(\sigma ) \cdot (-1)^{q_{\sigma }} = (-1)^{i+j} (-1)^{n-|Q|-1-p_{\sigma }}$, which depends on $\sigma$ only through $p_{\sigma }$.

If $\widetilde{A} \in \mathcal T _{D(Z)}^{ij}(Q \cup \{j\})$ (i.e., $\widetilde{A}$ is acyclic) then the sum on the left hand side of (66) contains only one term (there is only one element $\sigma \in S_{ij}$ for which $h^{\sigma } = h^{\widetilde{A}}$ and $p_{\sigma } = 0$). Thus, by (67), we obtain (66) for the case $\widetilde{A} \in \mathcal T _{D(Z)}^{ij}(Q \cup \{j\})$.

Assume for the rest of this proof that $\widetilde{A} \notin \mathcal T _{D(Z)}^{ij}(Q \cup \{j\})$. Denote by $m$ the number of directed circuits in $\widetilde{A}$. Since $\widetilde{A} \notin \mathcal T _{D(Z)}^{ij}(Q \cup \{j\})$, we have $m \ge 1$. With this and (67), we have

$$\begin{aligned}&\sum _{\begin{array}{c} \sigma \in S_{ij} \\ h^{\sigma } = h^{\widetilde{A}} \\ f^{\sigma }_1,\ldots , f^{\sigma }_{p_{\sigma }}\subseteq \widetilde{A} \\ \end{array}}{\mathrm{sgn}}(\sigma )\cdot (-1)^{q_{\sigma }}= (-1)^{i+j}(-1)^{n-|Q|-1}\cdot \sum _{\begin{array}{c} \sigma \in S_{ij} \\ h^{\sigma } = h^{\widetilde{A}} \\ f^{\sigma }_1,\ldots , f^{\sigma }_{p_{\sigma }}\subseteq \widetilde{A} \\ \end{array}}(-1)^{p_{\sigma }} \\&\quad = (-1)^{i+j}(-1)^{n-|Q|-1}\cdot \sum _{k=0}^{m}\left( {\begin{array}{c}m\\ k\end{array}}\right) (-1)^k=0, \end{aligned}$$

where the last equality follows from the Binomial Theorem.$\square$