BioSysBio:abstracts/2007/Thorsten Lenser/AppendixC

Proof of exact association between maximal independent sets and organizations of size [math]\displaystyle{ N }[/math]

Given an undirected graph [math]\displaystyle{ G=\langle V, E\rangle }[/math] where [math]\displaystyle{ V=\{v_1 \dots v_N\} }[/math] is a set of [math]\displaystyle{ N }[/math] vertices and [math]\displaystyle{ E }[/math] is a set of edges, an algebraic chemistry [math]\displaystyle{ \langle {\mathcal M}, {\mathcal R}\rangle }[/math] can be constructed as described in Appendix B, where [math]\displaystyle{ {\mathcal M}= \{a_1 \dots a_{2N}\}=\{s_i^0,s_i^1|i=1 \dots N\} }[/math] is a set of [math]\displaystyle{ 2N }[/math] molecular species and [math]\displaystyle{ {\mathcal R}=\{(A_j \rightarrow B_j)\} }[/math] is a set of reaction rules. Here, we show with a proof that the constructed reaction network contains organizations with [math]\displaystyle{ N }[/math] species as the biggest and those organizations imply maximal independent sets in the given graph.

At first, we define the association between a set of vertices and a set of species.

Definition

Let [math]\displaystyle{ I \subset V }[/math] be a set of vertices. We call [math]\displaystyle{ S_{I} = \{ s_{i}^{1} | v_i \in I\} \cup \{s_{i}^{0} | v_i \notin I\} }[/math] the set of species that is induced by [math]\displaystyle{ I }[/math].

In other words, [math]\displaystyle{ S_{I} = \{s_1^{b_1} \dots s_i^{b_i} \dots s_{|I|}^{b_{|I|}} \} }[/math] where [math]\displaystyle{ b_i=1 }[/math] when [math]\displaystyle{ v_i \in I }[/math] and [math]\displaystyle{ b_i=0 }[/math] otherwise.

Lemma

In the reaction network [math]\displaystyle{ \langle {\mathcal M},{\mathcal R} \rangle }[/math] constructed as described in Appendix B, no organization can contain species [math]\displaystyle{ s_{k}^{0} }[/math] and [math]\displaystyle{ s_{k}^{1} }[/math] together. Therefore, no organization with a size (number of species) greater than [math]\displaystyle{ N }[/math] can exist.

Proof of this lemma is given below.

Theorem

Set [math]\displaystyle{ I }[/math] of vertices is a maximal independent set if and only if the induced set [math]\displaystyle{ S_{I} }[/math] of species is an organization.

Proof

left to right

Let [math]\displaystyle{ I \subset V }[/math] be a maximal independent set (MIS) and [math]\displaystyle{ S_I }[/math] be the set of species induced by [math]\displaystyle{ I }[/math]. We have to show that [math]\displaystyle{ S_I }[/math] is an organization, i.e. closed and self-maintaining.

Closure: Assume that [math]\displaystyle{ S_I }[/math] is not closed, i.e. there exists a reaction [math]\displaystyle{ (A_j \rightarrow B_j) \in {\mathcal R} }[/math] that produces a species that is not in the set [math]\displaystyle{ S_{I} }[/math]. If the reaction has the form [math]\displaystyle{ s_j^1 \to s_k^0 (\in {\mathcal N}) }[/math] for a edge [math]\displaystyle{ (v_j,v_k)\in E }[/math], then we know [math]\displaystyle{ s_j^1 \in S_{I} }[/math] and thus [math]\displaystyle{ v_j \in I }[/math]. Since that reaction is assumed to violate the closure property, [math]\displaystyle{ s_k^0 \notin S_I }[/math]. We know then [math]\displaystyle{ s_k^1 \in S_I }[/math] from the lemma. Because set [math]\displaystyle{ S_I }[/math] contains both [math]\displaystyle{ s_j^1 }[/math] and [math]\displaystyle{ s_k^1 }[/math], set [math]\displaystyle{ I }[/math] must include both [math]\displaystyle{ v_j }[/math] and [math]\displaystyle{ v_j }[/math]. This leads to a contradiction that set [math]\displaystyle{ I }[/math] is a MIS and there is an edge [math]\displaystyle{ (v_j,v_k)\in E }[/math].

On the other hand, the reaction can have the form [math]\displaystyle{ s_h^0 + s_l^0 + \dots + s_m^0 \to n_k s_k^1 (\in {\mathcal V}) }[/math]. In that case we know that [math]\displaystyle{ s_p^0\in S_I }[/math] for all neighbors [math]\displaystyle{ v_p }[/math] of vertex [math]\displaystyle{ v_k }[/math]. This means no vertexes [math]\displaystyle{ v_p }[/math] neighboring vertex [math]\displaystyle{ v_k }[/math] are included in set [math]\displaystyle{ I }[/math]. However, the vertex [math]\displaystyle{ v_k }[/math] is not included in the set since species [math]\displaystyle{ s_k^1 }[/math] should not be in the set [math]\displaystyle{ S_I }[/math]. This contradicts the fact that the independent set [math]\displaystyle{ I }[/math] is maximal.

From these arguments, no reaction can produce new species that is not in the set [math]\displaystyle{ S_I }[/math]. Therefore, this set is closed.

Self-maintenance: Consider the flux vector [math]\displaystyle{ \mathbf{v} }[/math] that is 1 for all reactions involving only elements of [math]\displaystyle{ S_I }[/math] on the left-hand side, and 0 for all others. Given this [math]\displaystyle{ \mathbf{v} }[/math], the rate of change of all species in [math]\displaystyle{ S_I }[/math] is 0, since inflow and outflow of these species are of equal size. For all species not in [math]\displaystyle{ S_I }[/math], no reaction takes place, so their concentrations do not change. Therefore, [math]\displaystyle{ \mathbf{v} }[/math] fulfills the self-maintainance condition and [math]\displaystyle{ S_I }[/math] is self-maintaining.

Right to left

Given a set of vertices [math]\displaystyle{ I }[/math] and its induced set of species [math]\displaystyle{ S_I }[/math], which is an organization, we need to show that [math]\displaystyle{ I }[/math] is a MIS.

Given two vertexes [math]\displaystyle{ v_p }[/math] and [math]\displaystyle{ v_q }[/math] from the set [math]\displaystyle{ I }[/math], we know that [math]\displaystyle{ s_p^1 \in S_I }[/math] and [math]\displaystyle{ s_q^1 \in S_I }[/math]. If there exists an edge [math]\displaystyle{ (v_p,v_q) \in E }[/math], the reaction [math]\displaystyle{ s_p^1 \to s_q^0 }[/math] would produce [math]\displaystyle{ s_q^0 }[/math] inside the organization [math]\displaystyle{ S_I }[/math], which is impossible since [math]\displaystyle{ s_q^1 \in S_I }[/math]. Therefore, we conclude that [math]\displaystyle{ (v_p,v_q) \notin E }[/math] and [math]\displaystyle{ I }[/math] is an independent set.

If [math]\displaystyle{ I }[/math] were not a "maximal" IS, we could add a vertex [math]\displaystyle{ v_p \in V }[/math] to [math]\displaystyle{ I }[/math], and [math]\displaystyle{ I \cup \{v_p\} }[/math] would still be an IS. In other words, there exists [math]\displaystyle{ p }[/math] such that a set [math]\displaystyle{ S'_I=((S_I \backslash \{s_p^0\}) \cup \{s_p^1\}) }[/math] is still an organization. Because of the presence of species [math]\displaystyle{ s_p^1 }[/math], set [math]\displaystyle{ S'_I }[/math] must contain [math]\displaystyle{ s_q^0 }[/math] for all neighbors [math]\displaystyle{ v_q }[/math] of [math]\displaystyle{ v_p }[/math] [math]\displaystyle{ (p \neq q) }[/math] to be closed due to the reactions in [math]\displaystyle{ {\mathcal N} }[/math]. However, this leads to a contradiction that the original set [math]\displaystyle{ S_I }[/math] is not closed since the set also contains those species [math]\displaystyle{ s_q^0 }[/math] but does not contain [math]\displaystyle{ s_p^1 }[/math], produced by the reactions in [math]\displaystyle{ {\mathcal V} }[/math]. Thus, there does not exist such an index [math]\displaystyle{ p }[/math].

---

Proof of the lemma

Let [math]\displaystyle{ O \subset {\mathcal M} }[/math] be an organization, and suppose the organization contains [math]\displaystyle{ s_{k}^0 }[/math] and [math]\displaystyle{ s_{k}^1 }[/math] simultaneously ([math]\displaystyle{ s_{k}^{0}, s_{k}^{1} \in O }[/math]).

From the definition of the organization to be self-maintaining, there exists a flux vector

[math]\displaystyle{ \mathbf{v} = (v_{A_1 \rightarrow B_1}, \dots, v_{A_j \rightarrow B_j}, \dots, v_{A_{|{\mathcal R}|} \rightarrow B_{|{\mathcal R}|}})^T }[/math]

satisfying the following three conditions:

• [math]\displaystyle{ v_{A_j \rightarrow B_j} \gt 0 }[/math] if [math]\displaystyle{ A_j \in \mathcal{P}_M(O) }[/math]
• [math]\displaystyle{ v_{A_j \rightarrow B_j} = 0 }[/math] if [math]\displaystyle{ A_j \notin \mathcal{P}_M(O) }[/math]
• [math]\displaystyle{ f_i \geq 0 }[/math] if [math]\displaystyle{ a_i \in O }[/math] where [math]\displaystyle{ (f_1, \dots, f_i, \dots, f_{|{\mathcal M}|})^T = \mathbf{M v} }[/math].

where [math]\displaystyle{ \mathbf{M}=(m_{ij}) }[/math] is a stoichiometric matrix.

Because of the third condition, the sum of the production rates [math]\displaystyle{ f_i }[/math] with respect to the species in the organization should be bigger than zero:

[math]\displaystyle{ \sum_{\{i | a_i \in O\}} f_i = \sum_{\{i | a_i \in O\}} \sum_{j=1}^{|{\mathcal R}|} m_{ij}v_{A_j \rightarrow B_j} \geq 0 }[/math]

We write the reaction indices as [math]\displaystyle{ \mathcal V, \mathcal N, \mathcal D }[/math]:

[math]\displaystyle{ \sum_{\{i | a_i \in O\}} f_i = \sum_{\{i | a_i \in O\}} \sum_{\{j |(A_j \rightarrow B_j)\in {\mathcal V}\}} m_{ij}v_{A_j \rightarrow B_j} + \sum_{\{i | a_i \in O\}} \sum_{\{j |(A_j \rightarrow B_j)\in {\mathcal N}\}} m_{ij}v_{A_j \rightarrow B_j} + \sum_{\{i | a_i \in O\}} \sum_{\{j |(A_j \rightarrow B_j)\in {\mathcal D}\}} m_{ij}v_{A_j \rightarrow B_j} }[/math] [math]\displaystyle{ = \sum_{\{j |(A_j \rightarrow B_j)\in {\mathcal V}\}} \sum_{\{i | a_i \in O\}} m_{ij}v_{A_j \rightarrow B_j} + \sum_{\{j |(A_j \rightarrow B_j)\in {\mathcal N}\}} \sum_{\{i | a_i \in O\}} m_{ij}v_{A_j \rightarrow B_j} + \sum_{\{j |(A_j \rightarrow B_j)\in {\mathcal D}\}} \sum_{\{i | a_i \in O\}} m_{ij}v_{A_j \rightarrow B_j} }[/math]

The stoichiometric coefficients [math]\displaystyle{ m_{ij} }[/math] in the reactions of type [math]\displaystyle{ \mathcal V }[/math] and [math]\displaystyle{ \mathcal N }[/math] sum up to 0:

[math]\displaystyle{ \forall j | (A_j \rightarrow B_j) \in ({\mathcal V} \cup {\mathcal N}) : \sum_{i | a_i \in O} m_{ij} = 0 }[/math]

Thus, the first two sums are equal to zero. It follows that the third term must be non-negative.

However, all the stoichiometric coefficients in reactions of type [math]\displaystyle{ \mathcal D }[/math] are negative. If organization [math]\displaystyle{ O }[/math] contains both [math]\displaystyle{ s_k^0 }[/math] and [math]\displaystyle{ s_k^1 }[/math] at the same time, the flux for reaction [math]\displaystyle{ (s_{k}^0 + s_{k}^1 \to \emptyset)\in {\mathcal D} }[/math] must be set to a positive value. Thus, the sum of the production rates cannot be positive, so at least one production rate has to be negative. This contradicts the definition of the organization. Given this fact, it is obvious that no organization bigger than [math]\displaystyle{ N }[/math] can exist.