---

Claim. There is a function $g(n)\to0$ such that every $n$-uniform hypergraph with at most $n^{1/3-g(n)}2^n$ edges is 2-colorable; hence $m(n)>n^{1/3-o(1)}2^n$ for the function $m(n)$ of Problem 901. This is the form in which Radhakrishnan and Srinivasan state the theorem (Random Structures Algorithms 16 (2000), 4--32, Section 1), and the publisher's abstract gives the hypothesis as a bound of order $n^{1/3}2^n$ on the number of edges; Erdős's surveys of 1979 and 1982 report the result as $m(n)>cn^{1/3}2^n$. The proof recolors a random 2-coloring, and Spencer later gave a shorter probabilistic proof of the same bound. The paper also treats hypergraphs that are not uniform: it shows that a hypergraph whose edges all have at least $k$ points is 2-colorable when $\sum_e2^{-|e|}$ is at most a function of $k$ of order $\log^*k$, answering a question of Erdős.

Covers. The lower bound $m(n)>n^{1/3-o(1)}2^n$, which improved Beck's own [[problems/set_systems/E0901/claims/1977_01_01_beck|$c(\log n)2^n$]]. The order of $m(n)$ stays open: Radhakrishnan and Srinivasan's [[problems/set_systems/E0901/claims/2000_01_01_radhakrishnan_srinivasan|$0.7\sqrt{n/\ln n}\,2^n$]] supersedes 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 3-chromatic hypergraphs, Discrete Math. 24 (1978), no. 2, 127--137, 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 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.