# RAF Theory

Reflexively Autocatalytic, Food-generated Sets — A Formal Review

## 1. The Computational Surprise

The naïve approach to detecting self-sustaining subsets of a reaction network requires checking all 2|R| subsets—exponential in the number of reactions. Each subset must be tested for simultaneous F-generation and autocatalysis, properties that depend on the closure operator, itself iterative.

Hordijk & Steel (2004) showed this collapses to polynomial time. The mechanism: a fixed-point pruning algorithm that iteratively removes reactions failing the RAF conditions. Because each iteration removes at least one reaction, and removal is monotone (removing a reaction can only shrink the closure, never enlarge it), the algorithm converges in at most |R| iterations.

The transition from 2|R| to O(|R|2 · |X|) is not merely an optimisation. It means the question "does this system sustain itself?" is tractable—a structural property of the RAF definition, not an algorithmic trick.

The monotonicity is essential: if R′ ⊆ R″ then clR′(F) ⊆ clR″(F). This makes the pruning operator a monotone map on a finite lattice, guaranteeing a unique greatest fixed point—the maxRAF.

## 2. Formal Framework

Definition 1 (Catalytic Reaction System)

A CRS is a triple Q = (X, R, C) where:

- X = finite set of molecule types
- R = set of reactions; each r ∈ R has reactant set ρ(r) ⊆ X and product set π(r) ⊆ X
- C ⊆ X × R is the catalysis assignment ((x, r) ∈ C means x catalyzes r)

Definition 2 (Food Set)

F ⊆ X is a designated subset of molecule types assumed freely available from the environment. Food molecules are never consumed—they constitute the boundary conditions of the system.

Definition 3 (Closure)

Given R′ ⊆ R, the closure clR′(F) is the smallest superset of F closed under reactions in R′. Constructively:

W0 = F
Wi+1 = Wi ∪ { π(r) : r ∈ R′, ρ(r) ⊆ Wi }
clR′(F) = ∪i≥0 Wi

Convergence in at most |X| steps (each step adds ≥1 molecule type, or terminates).

Definition 4 (RAF)

A subset R′ ⊆ R is a Reflexively Autocatalytic, F-generated set (RAF) if:

1. F-generated: ∀ r ∈ R′ : ρ(r) ⊆ clR′(F)
2. Reflexively autocatalytic: ∀ r ∈ R′ : ∃ x ∈ clR′(F) such that (x, r) ∈ C

Both conditions reference the same closure—this is the self-referential character that makes RAF detection non-trivial.

## 3. Example CRS

Consider the following system with X = {f1, f2, a, b, c, p, q}, food F = {f1, f2}:

Reaction | Reactants | Products | Catalyst
--- | --- | --- | ---
r1 | f1 + f2 | a | b
r2 | a | b | a
r3 | f1 | c | a
r4 | p | q | q

### Analysis

Closure: clR(F) = {f1, f2, a, b, c}. Reaction r4 requires p ∈ ρ(r4), but p ∉ clR(F)—it cannot fire.

maxRAF = {r1, r2, r3}. All three are F-generated and catalyzed within the closure.

irrRAF = {r1, r2}. This is the autocatalytic core: r1 produces a (catalyzed by b), r2 produces b (catalyzed by a). Mutual dependency — neither alone is a RAF.

Piggybacking: r3 is in the maxRAF but not in any irrRAF. It depends on molecule a (as catalyst) produced by the core, but contributes nothing back. Remove it and {r1, r2} remains a RAF.

## 4. The Detection Algorithm

The maxRAF algorithm is a greatest fixed-point computation. Starting from the full reaction set, it iteratively prunes reactions that violate RAF conditions:

    function maxRAF(X, R, C, F):
        R' ← R                          // start with all reactions
        repeat:
            changed ← false
            W ← closure(R', F)          // compute cl_{R'}(F)
            for each r ∈ R':
                if ρ(r) ⊄ W:              // not F-generated
                    R' ← R' \ {r}
                    changed ← true
                else if ∄ x ∈ W : (x,r) ∈ C:  // no catalyst available
                    R' ← R' \ {r}
                    changed ← true
        until ¬changed
        return R'                        // maxRAF (possibly ∅)

    function closure(R', F):
        W ← F
        repeat:
            W' ← W ∪ { π(r) : r ∈ R', ρ(r) ⊆ W }
            if W' = W: return W
            W ← W'

Complexity: The outer loop runs at most |R| times (each pass removes ≥1 reaction or terminates). Each pass computes closure in O(|R| · |X|) and checks each reaction in O(|X|). Total: O(|R|2 · |X|).

### Algorithm Step-Through

Step 0
Click "Next Step" to begin the algorithm on the example CRS.

## 5. Key Theorems

Theorem 1 (Uniqueness of maxRAF)

Every CRS (X, R, C) with food set F has a unique maximal RAF (possibly empty).

Proof sketch: Let R1, R2 both be RAFs. Then R1 ∪ R2 is also a RAF: clR1∪R2(F) ⊇ clRi(F) for each i, so all reactants remain available and all catalysts remain in the closure. The union of all RAFs is therefore the unique maximum. □

Theorem 2 (Polynomial Detection)

The maxRAF of a CRS can be found in O(|R|2 · |X|) time.

Proof: The pruning algorithm makes at most |R| passes (removing ≥1 reaction per pass). Each pass: closure computation in O(|R| · |X|), plus checking each reaction against the closure in O(|X|). Correctness: the algorithm computes the greatest fixed point of the operator Φ(R′) = {r ∈ R′ : ρ(r) ⊆ clR′(F) ∧ ∃x ∈ clR′(F), (x,r) ∈ C}. By monotonicity (Tarski), this fixed point equals the maxRAF. □

Theorem 3 (Phase Transition)

In a random CRS with n molecule types and catalysis probability p (each molecule catalyzes each reaction independently with probability p):

P(RAF exists) transitions sharply from ≈0 to ≈1 at p ∼ 1/n

In the binary polymer model with maximum length t: threshold at p ∼ 1/(n · √|R|).

This is Kauffman's (1986) original conjecture, proved rigorously by Mossel & Steel (2005) for certain model classes and by simulation for others. The sharpness of the transition increases with n.

Theorem 4 (Sub-RAF Lattice)

The collection of all RAFs of a CRS forms a partially ordered set under set inclusion, with the maxRAF as the unique maximum element. The minimal non-empty elements are the irreducible RAFs (irrRAFs).

Definition 5 (Irreducible RAF)

A RAF R′ is irreducible (an irrRAF) if it contains no proper non-empty sub-RAF. Equivalently: removing any single reaction from R′ destroys the RAF property.

Definition 6 (Constructively Autocatalytic F-generated set — CAF)

A RAF R′ is a CAF if there exists an ordering r1, r2, …, rk of R′ such that for each i:

1. ρ(ri) ⊆ F ∪ ∪j<i π(rj)
2. ∃ x ∈ F ∪ ∪j<i π(rj) with (x, ri) ∈ C

Every CAF is a RAF. Not every RAF is a CAF—a RAF may require circular catalytic dependencies that have no constructive unfolding. CAFs avoid the "chicken-and-egg" problem: each reaction can fire using only products of earlier reactions plus food.

In the example: {r1, r2} is a RAF but NOT a CAF (r1 needs b as catalyst, which requires a, which requires r1). This mutual dependency is exactly the autocatalytic cycle.

### Sub-RAF Lattice for the Example

## 6. Phase Transition Demo

Adjust the catalysis probability p to observe the sharp transition. At low p, no RAF exists. Near the threshold (~0.10–0.15 for this network), a RAF suddenly emerges and grows. This is the Kauffman phase transition in miniature.

Catalysis probability p: 0.000
maxRAF: 0/20 reactions

## 7. The 11-Domain Instance

Application of RAF theory to an 11-domain scientific network. The question: which subsets of domains form self-sustaining intellectual ecosystems, where each domain's development is catalyzed by insights from other domains within the closure?

### Results Summary

Property | Value
--- | ---
Full network RAF | 10/10 reactions in maxRAF
Minimal non-trivial RAFs | {1, 6, 7} and {6, 7, 9}
Keystone domain | 7 (Autocatalysis) — removal collapses ALL non-trivial RAFs
Cluster A internal RAF | {1, 2, 3, 4} — 5/5 reactions, self-contained cycle

### Emergent Property Stack

Loop | Domains | Emergent Property
--- | --- | ---
Dynamics triad | {6, 7, 9} + 8, 10 | Spontaneous computation
Core triad | {1, 6, 7} + 5 | Protected self-organization
Topological cycle | {1, 2, 3, 4} | Topological computation
Instantiation | + 11 | Physical reality
Full stack | All 11 | Conditions for the Flat

Domain 7 (Autocatalysis) appears in both minimal RAFs. Its removal disconnects the catalytic support for every non-trivial self-sustaining subset. This is the formal expression of "keystone" — a single-point-of-failure in the RAF lattice.

## 8. References

1. Kauffman, S. A. (1971). Cellular Homeostasis, Epigenesis and Replication in Randomly Aggregated Macromolecular Systems. J. Cybernetics 1(1): 71–96.
2. Kauffman, S. A. (1986). Autocatalytic sets of proteins. J. Theoretical Biology 119: 1–24.
3. Kauffman, S. A. (1993). The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press.
4. Hordijk, W. & Steel, M. (2004). Detecting autocatalytic, self-sustaining sets in chemical reaction systems. J. Theoretical Biology 227: 451–461.
5. Hordijk, W., Steel, M. & Kauffman, S. (2010). The structure of autocatalytic sets: Evolvability, enablement, and emergence. Acta Biotheoretica 67: 269–281.
6. Steel, M. (2000). The emergence of a self-catalysing structure in abstract origin-of-life models. Applied Mathematics Letters 3: 91–95.
7. Mossel, E. & Steel, M. (2005). Random biochemical networks: The probability of self-sustaining autocatalysis. J. Theoretical Biology 233: 327–336.

RAF Tutorial — Self-contained review for the working physicist. No external dependencies.