Skip to content

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

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.

Back to catalogue · Compendium introduction