HEXAGONbeta

Equivalence of the RAF abundance conjecture and Frankl's union-closed sets conjecture

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

Contributed by Michael Mislan ↗

Version 1 / Oct 20, 2026 / CC BY 4.0

Abstract

In a catalytic reaction system with finitely many reactions, a RAF is a nonempty set of reactions whose reactants are produced from the food set by iterated closure under the selected reactions and whose reactions are each catalysed by a molecule of that closure. Steel (arXiv:2305.16714v4, Section 4) asked whether some reaction always lies in at least half of the RAFs. Call a reaction food-ready if all its reactants are food, and abundant if it lies in at least half of the sets in the family formed by the RAFs and the empty set. If some RAF U consists entirely of food-ready reactions, then some reaction of U is abundant, with no condition on the other reactions. If every reaction of the system, except at most two, is food-ready and the system has a RAF, then some reaction is abundant. Finally, the statement that every catalytic reaction system with finitely many reactions and a RAF has an abundant reaction is equivalent to Frankl's union-closed sets conjecture in the form: every finite union-closed family containing the empty set and a nonempty set has an element lying in at least half of its members.

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. Alweiss, Ryan; Huang, Brice; Sellke, Mark. Improved lower bound for Frankl's union-closed sets conjecture. 2022. arXiv:2211.11731arXiv
  2. Bruhn, Henning; Schaudt, Oliver. The journey of the union-closed sets conjecture. Graphs and Combinatorics, vol. 31, no. 6, pp. 2043–2074. 2015DOI
  3. Cambie, Stijn. Better bounds for the union-closed sets conjecture using the entropy approach. 2022. arXiv:2212.12500arXiv
  4. Chase, Zachary; Lovett, Shachar. Approximate union closed conjecture. 2022. arXiv:2211.11689arXiv
  5. de Moura, Leonardo; Ullrich, Sebastian. The Lean 4 theorem prover and programming language. Automated Deduction – CADE 28, vol. 12699, pp. 625–635. 2021DOI
  6. Dilworth, Robert P. Lattices with unique irreducible decompositions. Annals of Mathematics, vol. 41, no. 4, pp. 771–777. 1940DOI
  7. Frankl, Peter. Extremal set systems. Handbook of Combinatorics, vol. 2, pp. 1293–1329. 1995
  8. Gilmer, Justin. A constant lower bound for the union-closed sets conjecture. 2022. arXiv:2211.09055arXiv
  9. 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
  10. Hordijk, Wim; Steel, Mike. Chasing the tail: the emergence of autocatalytic networks. BioSystems, vol. 152, pp. 1–10. 2017DOI
Show all 23 referencesShow fewer references
  1. Kauffman, Stuart A. Autocatalytic sets of proteins. Journal of Theoretical Biology, vol. 119, no. 1, pp. 1–24. 1986DOI
  2. Kauffman, Stuart A. The Origins of Order: Self-Organization and Selection in Evolution. Oxford University Press. 1993
  3. Korte, Bernhard; Lovász, László; Schrader, Rainer. Greedoids. Springer, vol. 4. 1991
  4. Lozin, Vadim; Zamaraev, Viktor. Union-closed sets and Horn Boolean functions. Journal of Combinatorial Theory, Series A, vol. 202, pp. 105818. 2024DOI
  5. Mossel, Elchanan; Steel, Mike. Random biochemical networks: the probability of self-sustaining autocatalysis. Journal of Theoretical Biology, vol. 233, no. 3, pp. 327–336. 2005DOI
  6. Poonen, Bjorn. Union-closed families. Journal of Combinatorial Theory, Series A, vol. 59, no. 2, pp. 253–268. 1992DOI
  7. Reimer, David. An average set size theorem. Combinatorics, Probability and Computing, vol. 12, no. 1, pp. 89–93. 2003DOI
  8. Sarvate, Dinesh G.; Renaud, Jean-Claude. On the union-closed sets conjecture. Ars Combinatoria, vol. 27, pp. 149–154. 1989
  9. Sawin, Will. An improved lower bound for the union-closed set conjecture. 2022. arXiv:2211.11504arXiv
  10. Steel, Mike. Interior operators and their relationship to autocatalytic networks. Acta Biotheoretica, vol. 71, no. 4, pp. 21. 2023. arXiv:2305.16714arXivDOI
  11. 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
  12. 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
  13. Wójcik, Piotr. Union-closed families of sets. Discrete Mathematics, vol. 199, no. 1–3, pp. 173–182. 1999DOI

Version history

  1. v1Submitted by Michael MislanInitial depositCurrentOct 18, 2026