# BioSysBio:abstracts/2007/Thorsten Lenser/AppendixC

## Proof of exact association between maximal independent sets and organizations of size N

Given an undirected graph $G=\langle V, E\rangle$ where $V=\{v_1 \dots v_N\}$ is a set of N vertices and E is a set of edges, an algebraic chemistry $\langle {\mathcal M}, {\mathcal R}\rangle$ can be constructed as described in Appendix B, where ${\mathcal M}= \{a_1 \dots a_{2N}\}=\{s_i^0,s_i^1|i=1 \dots N\}$ is a set of 2N molecular species and ${\mathcal R}=\{(A_j \rightarrow B_j)\}$ is a set of reaction rules. Here, we show with a proof that the constructed reaction network contains organizations with N 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 $I \subset V$ be a set of vertices. We call $S_{I} = \{ s_{i}^{1} | v_i \in I\} \cup \{s_{i}^{0} | v_i \notin I\}$ the set of species that is induced by I.

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

### Lemma

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

Proof of this lemma is given below.

### Theorem

Set I of vertices is a maximal independent set if and only if the induced set SI of species is an organization.

### Proof

#### left to right

Let $I \subset V$ be a maximal independent set (MIS) and SI be the set of species induced by I. We have to show that SI is an organization, i.e. closed and self-maintaining.

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

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

From these arguments, no reaction can produce new species that is not in the set SI. Therefore, this set is closed.

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

#### Right to left

Given a set of vertices I and its induced set of species SI, which is an organization, we need to show that I is a MIS.

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

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

### Proof of the lemma

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

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

$\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$

satisfying the following three conditions:

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

where $\mathbf{M}=(m_{ij})$ is a stoichiometric matrix.

Because of the third condition, the sum of the production rates fi with respect to the species in the organization should be bigger than zero:

$\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$

We write the reaction indices as $\mathcal V, \mathcal N, \mathcal D$:

$\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}$ $= \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}$

The stoichiometric coefficients mij in the reactions of type $\mathcal V$ and $\mathcal N$ sum up to 0:

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

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 $\mathcal D$ are negative. If organization O contains both $s_k^0$ and $s_k^1$ at the same time, the flux for reaction $(s_{k}^0 + s_{k}^1 \to \emptyset)\in {\mathcal D}$ 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 N can exist.