---

Claim. For some absolute constant $c>0$, every $n$-uniform hypergraph with fewer than $c(\log n)2^n$ edges is 2-colorable, so $m(n)>c(\log n)2^n$ for the function $m(n)$ of Problem 901; in particular $m(n)/2^n\to\infty$, the conjecture of Erdős and Lovász in their 1975 paper, on the card for that paper. The bound is stated in this form by Pluhár (Random Structures Algorithms 35 (2009), 216--221, Section 1), who credits the paper with the first solution of the conjecture, and by the site's commentary. The method is Beck's recoloring of a random 2-coloring, the starting point of every later lower bound.

Covers. The lower bound $m(n)>c(\log n)2^n$ and with it the conjecture $m(n)/2^n\to\infty$. The order of $m(n)$ stays open: Beck's own [[problems/set_systems/E0901/claims/1978_01_01_beck|$n^{1/3-o(1)}2^n$]] and Radhakrishnan and Srinivasan's [[problems/set_systems/E0901/claims/2000_01_01_radhakrishnan_srinivasan|$0.7\sqrt{n/\ln n}\,2^n$]] supersede the bound, and the upper bound is Erdős's [[problems/set_systems/E0901/claims/1964_09_01_erdos|$n^22^{n+1}$]].

Depends on. No page of this wiki.

Acceptance. J. Beck, On a combinatorial problem of P. Erdős and L. Lovász, Discrete Math. 17 (1977), no. 2, 127--131, a refereed journal (refereed); the record gives only the year, so the page is dated to its first day. The curator of erdosproblems.com, Thomas Bloom, credits the bound and the proof of the conjecture to this paper in the problem's commentary, but the site labels the problem OPEN, so that credit is not acceptance of this partial claim.