Erdős Problem #593
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: open (not automatically the live result).
Subject areas: set theory, graph theory, hypergraphs, chromatic number.
Read this status correctly
The status above is reproduced from GCL's immutable external-catalogue snapshot. It is not a new claim of current mathematical resolution, a source-semantic review, an independent proof check, or GCL certification. A published proof and a GCL replay are separate events.
The question in plain language
A triple system is a hypergraph whose edges contain exactly three vertices. It is properly coloured if no edge is monochromatic. A finite triple system \(F\) is obligatory if every (possibly enormous) triple system requiring more than countably many colours contains a copy of \(F\). Erdős #593 asks for a characterization of the obligatory finite triple systems.
A major trap: being two-colourable is a necessary but not sufficient condition for being obligatory. A frozen historical formal statement mistakenly presented the equivalence as the conjecture; the later upstream provider corrected this.
A small example
Take four vertices \(\{0,1,2,3\}\) with two triples \(\{0,1,2\}\) and \(\{0,1,3\}\). Colour 0 and 1 red, 2 and 3 blue. Neither edge is monochromatic, so the system is two-colourable. Yet the two triples share two vertices, so the system is not linear (a linear triple system allows distinct edges to share at most one vertex).
As the GCL source audit explains, classical partition theory constructs a linear triple system with uncountable chromatic number; this four-point non-linear system cannot embed in it. Thus it is not obligatory. The finite colour check is elementary; the high-chromatic host rests on a separately cited infinite combinatorial theorem.
What is known
Erdős and Hajnal studied compulsory subhypergraphs under large chromatic-cardinal conditions. Two-colourability alone does not classify them. A subsequent claimed general classification has been discussed in external work, but a GCL protected adjudication accepted only particular elementary reductions and left the global kernel/proof assessment outstanding. Such work cannot be silently promoted to GCL-certified resolution.
GCL's current state
The authenticated source audit reconciles the frozen statement, primary literature and bounded elementary checks. These observations are not a new GCL mathematical certification.
What remains
The open source-record obligation is the exact finite-family characterization under the correct subhypergraph embedding and chromatic-cardinal quantifiers, with rigorous reconciliation of any purported resolution. The counterexample above refutes an erroneous candidate classification; it does not provide the desired full classification.
Sources and claim boundaries
- Erdős Problems #593: public mathematical question.
- Erdős–Hajnal (1967), On decomposition of graphs, Acta Mathematica Academiae Scientiarum Hungaricae 18, 359–377: original relevant context.
- GCL source audit: corrects a false frozen formal biconditional and records the bounded counterexample and unadjudicated global claim.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #1864 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: FIRST_RECONNAISSANCE_TRANCHE.
- Formal-statement coverage: A provider statement was included in the pinned snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.