Interior operators realizable by autocatalytic networks: an antimatroid characterization

A catalytic reaction system with a food set determines an interior operator on the subsets of its reaction set: each set of reactions is sent to the largest reflexively autocatalytic and food-generated (RAF) subset it contains. Steel (Acta Biotheoretica, 2023) showed that not every interior operator arises in this way when the reaction set is required to be the given ground set, and asked for a set-theoretic characterization of the set systems that are realizable as the RAFs of a catalytic reaction system. We answer this question for same-ground realizations. An interior operator $\psi$ on a finite set $E$ is the maxRAF operator of a catalytic reaction system with reaction set $E$ if and only if its family of fixed sets is the intersection of an antimatroid on $E$ with the family $\mathcal{C}(D)$ of vertex sets of a directed graph $D$ on $E$ in which every vertex has an in-neighbour. The antimatroid records food generation and the digraph records catalysis. Necessity rests on two observations: the food-generated subsets of any catalytic reaction system form an antimatroid, and on a food-generated set the catalysis condition reduces to a fixed digraph. Sufficiency is proved by an explicit construction with exactly one reaction per element of $E$, in which “blocker marker” molecules encode the antimatroid and private catalyst molecules encode the digraph. As consequences, finite antimatroids are exactly the food-generated families of finite catalytic reaction systems; the interior operator whose fixed sets are the empty set and all sets of size at least three has a same-ground realization if and only if $|E|\le 4$, which sharpens Steel’s bound of twelve to the exact threshold; and every interior operator is realizable if two reactions per element are permitted. The main theorem and its corollaries have been formalized and checked in the Lean 4 proof assistant.