Erdős #593 — characterize obligatory finite 3-uniform hypergraphs

Statement

Characterize those finite 3-uniform hypergraphs which appear (as a non-induced sub-hypergraph) in every 3-uniform hypergraph of chromatic number $>\aleph_0$. (Such hypergraphs are called "obligatory".)

Facts

- Prize \$500; status on erdosproblems.com is OPEN as of the 2026-07-02 fetch — "this is open, and cannot be resolved with a finite computation" (site-owner belief; erdosproblems.com/593). This has not yet been updated to reflect a June 2026 preprint claiming full resolution (see Literature state). - Falsifiable: no — a full characterization over all finite 3-uniform hypergraphs, not a single yes/no with a finite witness; needs a genuine proof. - Origin: Erdős, "On some problems in combinatorial set theory", Publ. Inst. Math. (Beograd) (1995) [Er95d]. Remark on erdosproblems.com/593 notes: "Similar problems were investigated by Erdős, Galvin, and Hajnal [EGH75]" (Erdős–Galvin–Hajnal, "On set-systems having large chromatic number and not containing prescribed subsystems", Colloq. Math. Soc. János Bolyai 10, 1975, pp. 425–513 — https://www.erdosproblems.com/bibs/EGH75) and "Erdős claims that for graphs the problem is completely solved: a graph of chromatic number $\geq\aleph_1$ must contain all finite bipartite graphs but need not contain any fixed odd cycle" — this graph-level statement is the Erdős–Hajnal theorem (Acta Math. Acad. Sci. Hungar. 17 (1966), 61–99, doi:10.1007/BF02020444). - Graph-level ("uniformity 2") companion results, both PROVED (directly linked as "See also" from the erdosproblems.com neighborhood, both fetched 2026-07-02): - erdos/594: does every graph $G$ with $\chi(G)\geq\aleph_1$ contain all sufficiently large odd cycles? Proved yes by Erdős, Hajnal, Shelah [EHS74] (Erdős–Hajnal had earlier proved it for $\chi\geq\aleph_2$). - erdos/737: must there be a single edge $e$ through which $G$ contains cycles of every sufficiently large length? Proved yes by Thomassen [Th83]. - Companion set-theoretic problem erdos/1177 (Bloom, https://www.erdosproblems.com/1177, fetched 2026-07-02, still OPEN on the site): three avoidance-spectrum questions for finite forbidden triple systems $G$ — (1) if $F_G(\aleph_1)\neq\emptyset$ is there a witness of size $\leq 2^{2^{\aleph_0}}$; (2) can two forbidden systems' avoidance classes at $\aleph_1$ be simultaneously non-empty yet disjoint; (3) does non-emptiness at one uncountable $\kappa$ imply it at every uncountable $\lambda$. The June 2026 preprint below claims to resolve #593 and all three parts of #1177 together. - Prior partial progress in the literature (all confirmed real via OpenAlex/DOI cross-check, cited by the resolution preprint): - Erdős, Hajnal, Rothschild, "On chromatic number of graphs and set-systems" (Cambridge Summer School in Math. Logic 1971, LNM 337, 1973, pp. 531–538): Theorem 2 gives, for 3-uniform systems, an uncountably-chromatic *linear* system (no two edges sharing 2 vertices) — i.e. any obligatory finite triple system must itself be linear. - Hajnal & Komjáth, "Obligatory subsystems of triple systems", Acta Math. Hungar. 119 (2007/2008), 1–13, doi:10.1007/s10474-007-6231-2 (confirmed on OpenAlex). - Komjáth, "Some remarks on obligatory subsystems of uncountably chromatic triple systems", Combinatorica 21 (2001), 233–238, doi:10.1007/s004930100021 (confirmed on OpenAlex): proved a finite triple system is obligatory iff each of its 2-connected components is, and that every obligatory triple system is tripartite. - Komjáth, "An uncountably chromatic triple system", Acta Math. Hungar. 121 (2008), 79–92: consistency (not ZFC) construction of an uncountably-chromatic triple system avoiding double intersections and circuits of length 3 and 5. - Reiher, "Obligatory hypergraphs", arXiv:2403.11223 (2024) / Proc. Amer. Math. Soc., to appear, doi:10.1090/proc/17021 (DOI confirmed to resolve to PAMS): extends Erdős–Hajnal's graph result to hypergraphs; proves every uniform private-vertex expansion of $K_{n,n}$ is obligatory — the key "positive atom" reused by the 2026 resolution. - Wang, Duan, Gerbner, Hama Karim, arXiv:2604.21551 (2026, title confirmed via direct fetch): finite-host analogue — weak chromatic numbers of finite $F$-free uniform hypergraphs are bounded iff $F$ has no Berge cycle (a *different* boundedness question, not the uncountable-jump question of #593).

Literature state

Resolved in the literature — but only by a very recent (23 June 2026), single-author, not-yet-refereed preprint that erdosproblems.com has not yet incorporated (site still shows OPEN as of this 2026-07-02 fetch, only 9 days after posting).

Eric Li (Trinity College, Cambridge), "A Resolution of Erdős Problems 593 and 1177: Obligatory Triple Systems and Exact Spectra", arXiv:2606.24882v1 [math.CO], 23 Jun 2026 (https://arxiv.org/abs/2606.24882, full text read via arxiv.org/html/2606.24882). Indexed by Semantic Scholar (corpusId 289623448) with no venue yet, consistent with "brand-new, unrefereed". All of its cited prior results ([EHR73], Erdős–Hajnal 1966, Hajnal–Komjáth 2007, Komjáth 2001/2008, Reiher 2024/PAMS, Wang–Duan–Gerbner–Hama Karim 2026) check out as real, correctly-attributed papers.

Claimed results (Theorem 1.1, restated exactly from the paper): - Let $J^+$ be the triple system from a finite graph $J$ by adding one private vertex to each edge. Let $\mathfrak B$ be the smallest class of finite triple systems containing $J^+$ for every finite bipartite $J$ and every finite edgeless system, closed under finite disjoint unions and one-point amalgamations. Claim: for a finite triple system $F$, TFAE: (i) $F$ occurs in every uncountably-chromatic triple system; (ii) $F\in\mathfrak B$; (iii) after removing isolated vertices, $F$ is linear, every hyperedge-node of its Levi graph has an incident bridge, and every Berge cycle of $F$ is even. - Theorem 1.2 (exact linear calibration): for every uncountable cardinal $\kappa$ there is a *linear* triple system $L_\kappa$ with $\chi(L_\kappa)=\kappa$ exactly (not just $\geq$), and if $\kappa=\mu^+$ then $|V(L_\kappa)|\leq 2^{2^\mu}$ — a ZFC (not just consistency) construction, strictly stronger than Komjáth's 2008 consistency result. - These combine (Corollary 1.3) into an exact-spectrum dichotomy: $\mathrm{Spec}(F)$ is either empty ($F\in\mathfrak B$, obligatory) or *all* uncountable cardinals ($F\notin\mathfrak B$) — an all-or-nothing result, no finite triple system is "obligatory at $\aleph_1$ only" or has a gap in its spectrum. This is claimed to answer all three parts of erdos/1177: yes, no, yes (with explicit witnesses for part (2): two triples sharing a pair, vs. the "loose 7-cycle"). - Proof architecture (per §1.1 "logical dependence"): Part I (finite combinatorics) proves #593 via a new "complete-rank one-apex sequence lift" and an "exact bridge-trace theorem", building on Erdős–Hajnal–Rothschild's linearity obstruction and Reiher's $K_{n,n}$-expansion positive result, and does not use any cardinal-arithmetic machinery. Part II (transfinite construction) proves the exact calibration theorem via a "transfinite reservoir recursion" using an Erdős–Galvin–Hajnal simultaneous-edge-labelling property (their Corollary 9.7, EGH75) plus Reiher's separate "Graphs of large girth" preprint (arXiv:2403.13571) for exact high-odd-girth graphs, then combines both parts for #1177. - I did not independently verify the ~60-page proof; the paper is self-consistent, cites real theorems with correct page/theorem numbers in an explicit "external theorem interface" appendix (a strong good-practice signal), and its central classification (linear + Levi-graph-bridge-covering + even-Berge-cycle) is a natural generalization of exactly the prior partial results (linearity from EHR73, tripartite-2-connected reduction from Komjáth 2001, $K_{n,n}^+$-positive-atom from Reiher 2024/PAMS) — i.e. it is not an outlier claim from nowhere, it closes a well-documented 50-year gap (EHR73 → Komjáth 2001/2008 → Reiher 2024 → Li 2026) using those exact prior results as stated interfaces. This raises plausibility but is not a substitute for peer review. - No AI/formal-proof-assistant involvement found for #593 specifically (unlike e.g. erdos/592's Isabelle/HOL work); no formalization of Li's proof exists yet.

Attack surface

- Mode: literature-resolution (primary — track whether arXiv:2606.24882 gets a v2/errata, a referee report, or independent confirmation/refutation) + verification (the highest-value next step is not new derivation but *checking* Li's proof, since if correct the $500 problem is already solved and only needs the community/site to catch up). - Concrete first experiment: (1) monitor arXiv:2606.24882 for revisions and citations (e.g. via curl -sS "https://api.semanticscholar.org/graph/v1/paper/arXiv:2606.24882/citations" periodically); (2) re-fetch erdosproblems.com/593 and /1177 periodically to see if T.F. Bloom updates the status (the site explicitly invites this via its comment system); (3) as a sanity check, hand-verify Theorem 1.1's easy direction on small cases — e.g. confirm $J^+$ for $J=K_{1,1}$ (a single edge, i.e. two triples sharing one vertex, "private-vertex expansion of an edge") is *not* obligatory by the linearity requirement, and that the "two triples sharing a pair" example cited for Erdős Problem #1177 part (2) is indeed non-linear hence non-obligatory by the Erdős–Hajnal–Rothschild obstruction — both are checkable by hand from stated definitions without needing the full paper. - Oracle: mechanical verification of the *characterization*'s finite side (is a given finite $F$ linear / Levi-bridge-covered / even-Berge-cycle?) is a trivial polynomial-time check on $F$'s structure — a good target for a small script that enumerates small triple systems and cross-checks membership in $\mathfrak B$ against condition (iii), as an independent sanity test of the equivalence (ii)$\iff$(iii) claimed in Theorem 1.1 (this is checkable without needing the hard uncountable-chromatic direction). The uncountable-chromatic direction itself has no finite oracle — it is genuine set-theoretic proof territory. - Feasibility: the *hard* mathematics (if Li's proof is correct) is already done by someone else; our realistic contribution is (a) literature-tracking to confirm/refute, (b) independently mechanically checking the finite combinatorial characterization (iii) against the class $\mathfrak B$ on small hypergraphs as a partial correctness signal, (c) if a flaw surfaces, this reverts to a genuine open "famous-and-hard" 50-year problem with real prior partial machinery (Reiher 2024/PAMS $K_{n,n}^+$ positive result + Komjáth 2001 tripartite/2-connected reduction) as the actual attack surface.

Related

- erdos/1177 — companion set-theoretic problem (avoidance-spectrum questions), claimed resolved in the *same* June 2026 preprint (arXiv:2606.24882) via the same "exact linear calibration" construction. - erdos/594 — graph-level ($2$-uniform) analogue: does $\chi(G)\geq\aleph_1$ force all sufficiently large odd cycles? Proved (Erdős–Hajnal–Shelah [EHS74]); the finite-configuration template that Erdős conjectured (and #593 asks to generalize to 3-uniform). - erdos/737 — sharper graph-level result: a single edge through which all sufficiently large cycles pass. Proved by Thomassen [Th83]. - concept/uncountable-chromatic-number — the core object: hypergraphs/graphs with $\chi>\aleph_0$, and what finite structure they must contain (Erdős–Hajnal 1966 theorem is the founding result of this whole area). - concept/obligatory-subgraph — the technical term (used throughout Komjáth's and Reiher's papers) for a finite structure forced into every uncountably-chromatic host; #593 asks for the exact class of obligatory finite 3-uniform hypergraphs. - concept/levi-graph — the bipartite incidence graph (vertices vs. hyperedges) used in Li's intrinsic characterization (condition (iii): every hyperedge-node has an incident bridge). - concept/berge-cycle — the hypergraph generalization of a graph cycle; Li's characterization requires every Berge cycle of an obligatory (isolated-vertex-free) triple system to be even, echoing the odd-cycle-freeness in the graph case (Erdős's claim on #593's page, and erdos/594). - concept/private-vertex-expansion — the $J\mapsto J^+$ construction (attach a fresh private vertex to every edge of a graph $J$ to make a triple system) that generates the positive/obligatory examples in Reiher's PAMS theorem and Li's class $\mathfrak B$. - concept/one-point-amalgamation — the gluing operation (plus disjoint union) that Li's class $\mathfrak B$ is closed under; proved closed via a graph-colouring compactness argument. - concept/set-mapping-partition-relation — the Erdős–Hajnal–Rothschild / Erdős–Galvin–Hajnal machinery ($R(\alpha,\beta,\gamma,k,i)$ partition properties, the $\mathrm{GS}_n(\rho)$ simultaneous-labelling property) underlying both the linearity obstruction and the exact-cardinal calibration construction. - concept/transfinite-recursion-construction — the "reservoir recursion" Li uses to build, in ZFC, a linear triple system of exact chromatic number $\kappa$ for every uncountable $\kappa$, strengthening Komjáth's earlier consistency-only construction.