Problem 832

Let $r\geq 3$ and $k$ be sufficiently large in terms of $r$ . Is it true that every $r$ -uniform hypergraph with chromatic number $k$ has at least

\binom{(r-1)(k-1)+1}{r}

edges, with equality only for the complete graph on $(r-1)(k-1)+1$ vertices?

Source: erdosproblems.com/832

Graph theory
Hypergraphs
Chromatic number

Wiki page

Status

SolvedDisproved

An accepted solution exists. The statement is false.

Disproved. The site labels the problem DISPROVED, credits the disproof to Alon [Al85] and says that the case $r=3$ is open; the claim page Alon 1985 records the result and its acceptance evidence.

Problem 832

Status

Proof claims

Discussion