# BioSysBio:abstracts/2007/Naoki Matsumaru/AppendixC

### From OpenWetWare

## Contents |

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

Given an undirected graph where is a set of *N* vertices and *E* is a set of edges, an algebraic chemistry can be constructed as described in Appendix B, where is a set of 2*N* molecular species and 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 be a set of vertices. We call the set of species that is induced by
*I*.

In other words, where *b*_{i} = 1 when and *b*_{i} = 0 otherwise.

### Lemma

- In the reaction network constructed as described in Appendix B, no organization can contain species and 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*S*_{I}of species is an organization.

### Proof

#### left to right

Let be a maximal independent set (MIS) and *S*_{I} be the set of species induced by *I*. We have to show that *S*_{I} is an organization, i.e. closed and self-maintaining.

*Closure:* Assume that *S*_{I} is not closed, i.e. there exists a reaction that produces a species that is not in the set *S*_{I}. If the reaction has the form for a edge , then we know and thus . Since that reaction is assumed to violate the closure property, . We know then from the lemma. Because set *S*_{I} contains both and , set *I* must include both *v*_{j} and *v*_{j}. This leads to a contradiction that set *I* is a MIS and there is an edge .

On the other hand, the reaction can have the form . In that case we know that for all neighbors *v*_{p} of vertex *v*_{k}. This means no vertexes *v*_{p} neighboring vertex *v*_{k} are included in set *I*. However, the vertex *v*_{k} is not included in the set since species should not be in the set *S*_{I}. 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 *S*_{I}. Therefore, this set is closed.

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

#### Right to left

Given a set of vertices *I* and its induced set of species *S*_{I}, which is an organization, we need to show that *I* is a MIS.

Given two vertexes *v*_{p} and *v*_{q} from the set *I*, we know that and . If there exists an edge , the reaction would produce inside the organization *S*_{I}, which is impossible since . Therefore, we conclude that and *I* is an independent set.

If *I* were not a "maximal" IS, we could add a vertex to *I*, and would still be an IS. In other words, there exists *p* such that a set is still an organization. Because of the presence of species , set *S*'_{I} must contain for all neighbors *v*_{q} of *v*_{p} to be closed due to the reactions in . However, this leads to a contradiction that the original set *S*_{I} is not closed since the set also contains those species but does not contain , produced by the reactions in .
Thus, there does not exist such an index *p*.

### Proof of the lemma

Let be an organization, and suppose the organization contains and simultaneously ().

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

satisfying the following three conditions:

- if
- if
- if where .

where is a stoichiometric matrix.

Because of the third condition, the sum of the production rates *f*_{i} with respect to the species in the organization should be bigger than zero:

We write the reaction indices as :

The stoichiometric coefficients *m*_{ij} in the reactions of type and sum up to 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 are negative. If organization *O* contains both and at the same time, the flux for reaction 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.