Obligatory triple systems: atoms, spectra and decompositions
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 -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.
Provenance statement
Tools used
- OpenAI
- ChatGPTVersion GPT-5.6 Pro, GPT-6 Pro
- OpenAI
- Codex
- Lean
- LeanVersion Lean 4.32.0 with Mathlib
- Harmonic
- Aristotle
References
- Paul Erd ő s. On some problems in combinatorial set theory. Publikacije Instituta Matematičkog (Beograd) (N.S.) , 57(71): 0 61--65, 1995.
- Thomas F. Bloom. Erd ő s problem 593. https://www.erdosproblems.com/593, 2026. Accessed 11 July 2026.link
- 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
- 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
- Reinhard Diestel. Graph Theory , fifth edition. Graduate Texts in Mathematics, volume 173. Springer, Berlin, 2017. 10.1007/978-3-662-53622-3.DOI
- 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
- 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
- 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.
- 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
- 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
- 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
- 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
- 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
- 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
- Robert Tarjan. Depth-first search and linear graph algorithms. SIAM J. Comput. , 1 0 (2): 0 146--160, 1972. 10.1137/0201010.DOI
- 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
- 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
- George Gr ä tzer. Lattice Theory: Foundation . Birkh ä user, Basel, 2011. 10.1007/978-3-0348-0018-1.DOI
- 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
- 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
- Jeremy Avigad and John Harrison. Formally verified mathematics. Commun. ACM , 57 0 (4): 0 66--75, 2014. 10.1145/2591012.DOI
- 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
- 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
- G. Rossi. Weighted paths between partitions. arXiv:1509.01852v1 , 2015. https://arxiv.org/abs/1509.01852v1.arXiv
Version history
- 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