Erdős Problem #832
Editorial depth: Reviewed explanatory article — evidence qualified.
Snapshot classification: disproved (not automatically the live result).
Subject areas: 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
For ordinary graphs a large chromatic number forces many edges. Erdős asked for an analogous sharp threshold for uniform hypergraphs. Alon's counterexamples defeat the proposed general rule, but not the remaining three-uniform case at sufficiently large chromatic number.
For a fixed r>=3 and sufficiently large chromatic number k, the proposed edge-minimal r-uniform hypergraph is the complete r-graph on (r-1)(k-1)+1 vertices. The statement is false for all r>=4, but the large-k r=3 case remains OPEN. Chromatic number means vertex colors with no monochromatic hyperedge; the finite r=k=3 Fano exception does not settle r=3 for large k.
A small example
For r=k=3, the seven triples of the Fano plane have chromatic number 3 but only seven edges; the complete 3-graph on (r-1)(k-1)+1=5 vertices has 10 edges. Exhaustively enumerating 128 two-colorings finds zero valid Fano colorings. Explicit seven-edge witness does not disprove eventual large-k r=3 statement.
This finite calculation is not an asymptotic or all-parameter proof.
What is known
Maintained /latex/832 directly read 2026-10-14. Alon 1985, peer-reviewed publication, Hypergraphs with high chromatic number,, Graphs and Combinatorics 1985 disproves all r>=4, with for sufficiently large r and k at least Cr an upper construction at most (7/8)^r times proposed complete-graph edge count. Akolzin–Shabanov [AkSh16] bound minimum number of edges for chromatic number greater than k by constants times (r/log r)k^r and (r^3 log r)k^r, not the same threshold. Cherkashin–Petrov [ChPe20] prove fixed-r normalized limit exists. All full primary proof texts require independent review.
For r=3,k=3 the proposed complete hypergraph has ten edges: all three-subsets of five points. The seven Fano triples already require three colors and therefore refute this small-k instance. That does not settle the remaining r=3 question with k large. Alon's 1985 results disprove the general statement for r>=4. Follow-up results on chromatic number STRICTLY GREATER than k need indexing care.
GCL's current state
The authenticated source return has disposition STATUS_CONFLICT. This is an editorially reviewed explanatory article under protected batch EC-BULK-005-R5; its original STATUS_CONFLICT source remains preserved. Published results remain attributed to their authors; original source conflicts and independent full-proof-review limits are not silently cleared by publishing the manuscript.
What remains
Write exact Fano hyperedges, test all two-colorings, count seven versus ten, inspect Alon 1985 and the later theorem quantifiers, keep r3-large-k open and avoid claiming full resolution.
The original primary mathematical proofs, quantified status, finite definitions and deployed rendering must be independently checked before protected admission. Publication of the source draft is already verified. Exact-hash V2 editorial admission and full independent historical theorem proof replay remain distinct and not yet claimed.
Sources and claim boundaries
- Maintained Erdős problem #832, LaTeX/bibliography and authenticated issue source return, checked 14 October 2026.
- Pinned teorth/erdosproblems revision 536408716724a2402bdfa7c1d764bf83d64a8c89, data/problems.yaml. Original papers and unresolved proof obligations are identified in the source comment.
- Editorial review: R5 protected PR #2668. Source publication: MERGED. Deployed MathJax: VERIFIED. GCL theorem certification: NONE.
Catalogue and evidence provenance
- Pinned catalogue source: teorth/erdosproblems at
536408716724. - GCL issue: #2103 — protected issue/assignment identity; its labels and results are live, not reproduced automatically here.
- GCL triage: OUTSIDE_STRICT_OPEN_TRIAGE.
- Formal-statement coverage: No statement was confirmed in GCL's pinned formal-provider snapshot. Presence does not mean the statement or proof has been checked.
- External mathematical status: consult current problem page and its dated bibliography.