Erdős Problem #593 — Characterize those finite 3-uniform hypergraphs which appear in every 3-uniform hypergraph of chromatic number $>\aleph_0$.

The problem asks which finite triple systems are unavoidable in every triple system whose chromatic number is uncountable.

Known results

• Hajnal and Komjáth showed that the loose cycle $C_n^{(3)}$ is linearly obligatory for $n\notin\{2,3,5\}$; the source gives no year.

June 2026 classification

The paper states that, after isolated vertices are removed, $F$ is obligatory exactly when it is linear, every hyperedge-node of its Levi graph is incident with a bridge, and every Berge cycle has even length. Equivalently, these systems are generated from private-vertex expansions of finite bipartite graphs by finite disjoint unions and one-point amalgamations. It also gives counterexamples at every uncountable cardinal when any condition fails. In particular, $C_7^{(3)}$ is linearly obligatory but not obligatory. The paper reports formal verification in Lean $4$.

Current status (as of June 2026): The classification is supplied by an arXiv preprint and reported as formally verified; no remaining case of Problem #593 is identified.