Obligatory triple systems: atoms, spectra and decompositions

A mix of human-written and AI-generated textHuman understanding: all partsmath.CO — Combinatoricsmath.LO — Logic

Contributed by Samuil Petkov ↗

Version 1 / Nov 18, 2026 / CC BY 4.0

Abstract

Erdős Problem 593 asks which finite triple systems embed in every triple system of uncountable chromatic number. Such finite systems are called obligatory. We describe their structure and the ways of decomposing them while keeping their original hyperedges. Every obligatory system without isolated points has canonical pieces, called atoms: single triples and expansions of finite 22-connected bipartite graphs, obtained by adding one new private point to each graph edge. A forest records how the atoms meet and reconstructs the system. We determine exactly which numbers of vertices, hyperedges and components can occur, and which atom counts occur in a connected system, including the parity restriction when the vertex–hyperedge incidence graph has just one independent cycle. For a fixed system, we consider decompositions into connected pieces that meet in at most one point and whose shared-point incidences form a forest. Each such decomposition is specified by independently partitioning the atoms through each shared point. These choices, ordered by merging blocks, form a product of partition lattices. An exact piece-count formula identifies the single local mergers. Li gave the first public classification. The appendix includes our self-contained proof, developed independently in parallel with Li's work.

Author comments: The first public classification of obligatory triple systems is due to E. Li, arXiv:2606.24882 (https://arxiv.org/abs/2606.24882); the classification proof in the appendix was developed independently in parallel. The principal statements are matched to a Lean 4 development (Lean 4.32.0, pinned Mathlib) in the public repository https://github.com/SamPetkov/Erdos593 , including the self-contained file Erdos593SelfContained.lean.

Provenance statement

OpenAI GPT-5.6 Pro, GPT-6 Pro and Codex, and Harmonic's Aristotle, were used in proof development, checking, editorial revision and the Lean formalization. Anthropic Claude (Claude Code) was used only to prepare this Hexagon deposit. The author takes responsibility for the arguments, attribution, citations and final text.

Tools used

OpenAI
ChatGPTVersion GPT-5.6 Pro, GPT-6 Pro
OpenAI
Codex
Lean
LeanVersion Lean 4.32.0 with Mathlib
Harmonic
Aristotle

References

  1. Paul Erd ő s. On some problems in combinatorial set theory. Publikacije Instituta Matematičkog (Beograd) (N.S.) , 57(71): 0 61--65, 1995.
  2. Thomas F. Bloom. Erd ő s problem 593. https://www.erdosproblems.com/593, 2026. Accessed 11 July 2026.link
  3. Eric Li. A resolution of Erd ő s Problems 593 and 1177 : Obligatory triple systems and exact spectra. arXiv:2606.24882, submitted 23 June 2026. 10.48550/arXiv.2606.24882. URL https://arxiv.org/abs/2606.24882.arXivDOI
  4. Hassler Whitney. Non-separable and planar graphs. Trans. Amer. Math. Soc. , 34 0 (2): 0 339--362, 1932. 10.1090/S0002-9947-1932-1501641-7.DOI
  5. Reinhard Diestel. Graph Theory , fifth edition. Graduate Texts in Mathematics, volume 173. Springer, Berlin, 2017. 10.1007/978-3-662-53622-3.DOI
  6. Richard P. Stanley. Enumerative Combinatorics , volume 1, second edition. Cambridge Studies in Advanced Mathematics, volume 49. Cambridge University Press, Cambridge, 2012. 10.1017/CBO9781139058520.DOI
  7. Paul Erd ő s and Andr á s Hajnal. On chromatic number of graphs and set-systems. Acta Math. Acad. Sci. Hungar. , 17 0 (1--2): 0 61--99, 1966. 10.1007/BF02020444.DOI
  8. Paul Erd ő s, Fred Galvin, and Andr á s Hajnal. On set-systems having large chromatic number and not containing prescribed subsystems. In Infinite and Finite Sets (Keszthely, 1973) , volume 10 of Colloquia Mathematica Societatis J á nos Bolyai , pages 425--513. North-Holland, 1975.
  9. P é ter Komj á th. Some remarks on obligatory subsystems of uncountably chromatic triple systems. Combinatorica , 21 0 (2): 0 233--238, 2001. 10.1007/s004930100021.DOI
  10. Christian Reiher. Obligatory hypergraphs. arXiv:2403.11223, 2024. 10.1090/proc/17021. URL https://arxiv.org/abs/2403.11223.arXivDOI
Show all 24 referencesShow fewer references
  1. Nicolaas Govert de Bruijn and Paul Erd ő s. A colour problem for infinite graphs and a problem in the theory of relations. Nederl. Akad. Wetensch. Proc. Ser. A , 54 0 (5): 0 371--373, 1951. 10.1016/S1385-7258(51)50053-7.DOI
  2. Paul Erd ő s and Richard Rado. A partition calculus in set theory. Bull. Amer. Math. Soc. , 62 0 (5): 0 427--489, 1956. 10.1090/S0002-9904-1956-10036-0.DOI
  3. M. Amin Bahmanian and Mateja Šajna. Connection and separation in hypergraphs. Theory Appl. Graphs , 2 0 (2): 0 Article 5, 2015. 10.20429/tag.2015.020205. URL https://arxiv.org/abs/1504.04274.DOI
  4. R. Endre Tarjan. A note on finding the bridges of a graph. Inform. Process. Lett. , 2 0 (6): 0 160--161, 1974. 10.1016/0020-0190(74)90003-9.DOI
  5. Robert Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput. , 1 0 (2): 0 146--160, 1972. 10.1137/0201010.DOI
  6. Frank Simon, Peter Tittmann, and Martin Trinks. Counting connected set partitions of graphs. Electron. J. Combin. , 18 0 (1): 0 P14, 2011. 10.37236/501. URL https://arxiv.org/abs/1005.1726.DOI
  7. Richard P. Stanley. An introduction to hyperplane arrangements. In Ezra Miller, Victor Reiner, and Bernd Sturmfels, editors, Geometric Combinatorics , volume 13 of IAS/Park City Mathematics Series , pages 389--496. American Mathematical Society, Providence, RI, 2007. URL https://math.mit.edu/~rstan/arrangements/arr.html.link
  8. George Gr ä tzer. Lattice Theory: Foundation . Birkh ä user, Basel, 2011. 10.1007/978-3-0348-0018-1.DOI
  9. Leonardo de Moura and Sebastian Ullrich. The Lean 4 theorem prover and programming language. In André Platzer and Geoff Sutcliffe, editors, Automated Deduction---CADE 28 , volume 12699 of Lecture Notes in Computer Science , pages 625--635. Springer, Cham, 2021. 10.1007/978-3-030-79876-5_37.DOI
  10. The mathlib Community. The Lean mathematical library. In Proceedings of the 9th ACM SIGPLAN International Conference on Certified Programs and Proofs , pages 367--381. Association for Computing Machinery, New York, 2020. 10.1145/3372885.3373824.DOI
  11. Jeremy Avigad and John Harrison. Formally verified mathematics. Commun. ACM , 57 0 (4): 0 66--75, 2014. 10.1145/2591012.DOI
  12. Mario Carneiro. Lean4Lean: Verifying a typechecker for Lean, in Lean. arXiv:2403.14064v3, revised 14 September 2025. URL https://arxiv.org/abs/2403.14064v3.arXiv
  13. Tudor Achim, Alex Best, Kevin Der, Math ï s F é d é rico, Sergei Gukov, Daniel Halpern-Leistner, Kirsten Henningsgard, Yury Kudryashov, Alexander Meiburg, Martin Michelsen, Riley Patterson, Eric Rodriguez, Laura Scharff, Vikram Shanker, Vladimir Sicca, Hari Sowrirajan, Aidan Swope, Matyas Tamas, Vlad Tenev, Jonathan Thomm, Harold Williams, and Lawrence Wu. Aristotle : IMO -level automated theorem proving, 2025. URL https://arxiv.org/abs/2510.01346. arXiv:2510.01346.arXiv
  14. G. Rossi. Weighted paths between partitions. arXiv:1509.01852v1 , 2015. https://arxiv.org/abs/1509.01852v1.arXiv

Version history

  1. v1 · 34 pagesSubmitted by Samuil PetkovThe first public classification of obligatory triple systems is due to E. Li, arXiv:2606.24882 (https://arxiv.org/abs/2606.24882); the classification proof in the appendix was developed independently in parallel. The principal statements are matched to a Lean 4 development (Lean 4.32.0, pinned Mathlib) in the public repository https://github.com/SamPetkov/Erdos593 , including the self-contained file Erdos593SelfContained.lean.CurrentNov 17, 2026