HEXAGONbeta

Antimatroid characterization of RAF interior operators

Primarily AI-generated textHuman understanding: some partsmath.CO — Combinatorics

Contributed by Michael Mislan ↗

Version 1 / Oct 20, 2026 / CC BY 4.0

Abstract

Addressing the RAF-realizability question in Section 4 of Mike Steel's Interior Operators and Their Relationship to Autocatalytic Networks (arXiv:2305.16714v4, 2023), we characterize which interior operators on the subsets of a finite set E are maxRAF operators of catalytic reaction systems whose reaction set is exactly E. An interior operator is represented by its family of fixed sets, a union-closed family containing the empty set. A same-ground realization is a system with one reaction per element of E, finitely many molecule types, a food set and a catalysis relation; it realizes the empty set together with its RAFs, the nonempty reaction sets whose reactants arise from food by iterated closure under the selected reactions and whose reactions are each catalysed by a molecule of that closure. Such a family has a same-ground realization if and only if it is the intersection of an accessible union-closed family A and a predecessor-support family. Here A contains the empty set, is closed under unions, and every nonempty member of A has an element whose removal leaves a member of A; the members of A need not cover E. A set S is supported by a predecessor map P on E when every element e of S has some element of S in P(e), loops allowed. The family consisting of the empty set and all subsets of size at least three has a same-ground realization if and only if E has at most four elements. This gives the sharp threshold for the family considered in Proposition 5 and its subsequent remarks in Steel (2023). Both results are formalized in Lean 4 with Mathlib.

Provenance statement

The text is primarily AI-generated. AI systems assisted the mathematical development, computations and Lean formalization under human direction; human understanding covers some parts of the work.

Formalizations

References

  1. Balla, Igor; Bollobás, Béla; Eccles, Tom. Union-closed families of sets. Journal of Combinatorial Theory, Series A, vol. 120, no. 3, pp. 531–544. 2013DOI
  2. Björner, Anders; Ziegler, Günter M. Introduction to greedoids. Matroid Applications, vol. 40, pp. 284–357. 1992
  3. de Moura, Leonardo; Ullrich, Sebastian. The Lean 4 theorem prover and programming language. Automated Deduction – CADE 28, vol. 12699, pp. 625–635. 2021DOI
  4. Dietrich, Brenda L. A circuit set characterization of antimatroids. Journal of Combinatorial Theory, Series B, vol. 43, no. 3, pp. 314–321. 1987DOI
  5. Doignon, Jean-Paul; Falmagne, Jean-Claude. Knowledge Spaces. Springer. 1999
  6. Edelman, Paul H.; Jamison, Robert E. The theory of convex geometries. Geometriae Dedicata, vol. 19, no. 3, pp. 247–270. 1985DOI
  7. Falmagne, Jean-Claude; Doignon, Jean-Paul. Learning Spaces: Interdisciplinary Applied Mathematics. Springer. 2011
  8. Gabora, Liane; Steel, Mike. Autocatalytic networks in cognition and the origin of culture. Journal of Theoretical Biology, vol. 431, pp. 87–95. 2017DOI
  9. Gilmer, Justin. A constant lower bound for the union-closed sets conjecture. 2022. arXiv:2211.09055
  10. Hordijk, Wim; Smith, Joshua I.; Steel, Mike. Algorithms for detecting and analysing autocatalytic sets. Algorithms for Molecular Biology, vol. 10, pp. 15. 2015DOI
Show all 24 referencesShow fewer references
  1. Hordijk, Wim; Steel, Mike. Detecting autocatalytic, self-sustaining sets in chemical reaction systems. Journal of Theoretical Biology, vol. 227, no. 4, pp. 451–461. 2004DOI
  2. Hordijk, Wim; Steel, Mike. Autocatalytic networks at the basis of life's origin and organization. Life, vol. 8, no. 4, pp. 62. 2018DOI
  3. Kauffman, Stuart A. Autocatalytic sets of proteins. Journal of Theoretical Biology, vol. 119, no. 1, pp. 1–24. 1986DOI
  4. Kauffman, Stuart A. The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press. 1993
  5. Korte, Bernhard; Lovász, László. Shelling structures, convexity and a happy end. Graph Theory and Combinatorics, pp. 219–232. 1984
  6. Korte, Bernhard; Lovász, László; Schrader, Rainer. Greedoids. Springer, vol. 4. 1991
  7. Loutchko, Dimitri. An algebraic characterization of self-generating chemical reaction networks using semigroup models. Journal of Mathematical Biology, vol. 86, pp. 76. 2023DOI
  8. Steel, Mike. Interior operators and their relationship to autocatalytic networks. Acta Biotheoretica, vol. 71, no. 4, pp. 21. 2023DOI
  9. Steel, Mike; Hordijk, Wim; Xavier, Joana C. Autocatalytic networks in biology: structural theory and algorithms. Journal of the Royal Society Interface, vol. 16, no. 151, pp. 20180808. 2019DOI
  10. Steel, Mike; Xavier, Joana C.; Huson, Daniel H. The structure of autocatalytic networks, with application to early biochemistry. Journal of the Royal Society Interface, vol. 17, no. 171, pp. 20200488. 2020DOI
  11. The mathlib Community. The Lean mathematical library. Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs (CPP 2020), pp. 367–381. 2020DOI
  12. Wild, Marcel. The joy of implications, aka pure Horn formulas: Mainly a survey. Theoretical Computer Science, vol. 658, pp. 264–292. 2017DOI
  13. Xavier, Joana C.; Hordijk, Wim; Kauffman, Stuart; Steel, Mike; Martin, William F. Autocatalytic chemical networks at the origin of metabolism. Proceedings of the Royal Society B, vol. 287, no. 1922, pp. 20192377. 2020DOI
  14. Yoshikawa, Hiyori; Hirai, Hiroshi; Makino, Kazuhisa. A representation of antimatroids by Horn rules and its application to educational systems. Journal of Mathematical Psychology, vol. 77, pp. 82–93. 2017DOI

Version history

  1. v1Submitted by Michael MislanInitial depositCurrentOct 18, 2026