Research notes on every problem, and a library of the papers behind them. Built from the open erdos repository.

Updated Oct 8

Problem 780

claims/: The 2 claim pages of Problem 780, one per claimant's result; the problem's standing derives from them.

Statement. Suppose $n\geq kr+(t-1)(k-1)$ and the edges of the complete $r$ -uniform hypergraph on $n$ vertices are $t$ -coloured. Prove that some colour class must contain $k$ pairwise disjoint edges.

Status. Proved.

Source. erdosproblems.com/780, accessed 2026-09-04. Cite as: T. F. Bloom, Erdős Problem #780, https://www.erdosproblems.com/780.

References.

[AFL86] Alon, N. and Frankl, P. and Lovász, L., The chromatic number of Kneser hypergraphs. Trans. Amer. Math. Soc. (1986), 359-370.
[Lo78] Lovász, L., Kneser's conjecture, chromatic number, and homotopy. J. Combin. Theory Ser. A (1978), 319-324.

Formalization. Statement in formal-conjectures, marked solved there; the theorem has a third-party Lean proof, linked from the claim page below, which this corpus has not built.

Current assessment

The statement is Erdős's 1973 conjecture on colorings of the complete $r$ -uniform hypergraph, equivalently a determination of the chromatic number of the Kneser hypergraph whose vertices are the $r$ -subsets of an $n$ -set and whose edges are $k$ pairwise disjoint ones. It is proved in full: the case $k=2$ is Kneser's conjecture, proved by Lovász [Lo78], and the general case is Theorem 1.1 of Alon, Frankl and Lovász [AFL86]. The accepted claim page Alon, Frankl and Lovász 1986 states the theorem, the sharpness of the bound $n\ge kr+(t-1)(k-1)$ , the topological proof and the acceptance evidence, a refereed journal paper credited by the site's curator. The case $k=2$ has its own accepted partial page, Lovász 1978, a refereed paper credited by the curator, on which the general proof rests.

Search scope. 2026-10-07: the site's problem page, its discussion thread and its proof-claims list. No other claim on the problem was found.

Linked library material

These entries are derived from explicit links on library pages. They are navigation only and do not by themselves record mathematical progress.

Linked from (7)

Lovász's proof of the Kneser conjecture Alon, Frankl and Lovász's theorem problems/graph_coloring/E0780/claims Graph Coloring graph_coloring/alon_1986_chromatic_number_kneser_hypergraphs Corollary 1.2 (p. 359): unequal targets k_1 ≥ … ≥ k_t ≥ 2 for the t classes Theorem 1.1 (p. 359): t classes of r-sets with n ≥ kr + (t−1)(k−1) force k disjoint sets in one class

Graph