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 2N 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.
- Let be a set of vertices. We call the set of species that is induced by I.
In other words, where bi = 1 when and bi = 0 otherwise.
- 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.
- Set I of vertices is a maximal independent set if and only if the induced set SI of species is an organization.
left to right
Let 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 that produces a species that is not in the set SI. 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 SI contains both and , set I must include both vj and vj. 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 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 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 that is 1 for all reactions involving only elements of SI on the left-hand side, and 0 for all others. Given this , 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, 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 and . If there exists an edge , the reaction would produce inside the organization SI, 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 vq of vp to be closed due to the reactions in . However, this leads to a contradiction that the original set SI 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 where .
where 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:
We write the reaction indices as :
The stoichiometric coefficients mij 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.