---

Claim. Corollary 1 of the paper states $m(n)>\frac{\sqrt2}{2}\,\pi^{-1/4}e^{-1/(12n)}\,n^{1/4}2^n$, that is, $m(n)>0.5268\,n^{1/4}2^n$ for $n\ge3$, for the function $m(n)$ of Problem 901. The proof takes the vertices in a uniformly random order, colors every vertex blue and recolors a vertex red when it is the first vertex of some edge in that order; no edge ends all blue, and Claim 1 bounds the expected number of all-red edges by $2\sqrt\pi\,e^{1/(6n)}n^{-1/2}2^{-2n}|E|(|E|-1)$, which is below $1$ for $|E|$ at the stated size. The same method gives $m_k(n)>c_2k^{-1}n^{(k-1)/(2k)}2^n$ for $k$-colorability and, with the Lovász Local Lemma, reproves that $n$-uniform $n$-regular hypergraphs are 2-colorable for $n\ge8$. The source card records the results.

Covers. The lower bound $m(n)>0.5268\,n^{1/4}2^n$ for $n\ge3$, which reproves $m(n)/2^n\to\infty$ by a shorter argument than Beck's. It is weaker than Radhakrishnan and Srinivasan's [[problems/set_systems/E0901/claims/2000_01_01_radhakrishnan_srinivasan|$0.7\sqrt{n/\ln n}\,2^n$]], so it changes no bound; the order of $m(n)$ stays open, with Erdős's [[problems/set_systems/E0901/claims/1964_09_01_erdos|$n^22^{n+1}$]] as the upper bound.

Depends on. No page of this wiki; the proof is self-contained.

Acceptance. A. Pluhár, Greedy colorings of uniform hypergraphs, Random Structures Algorithms 35 (2009), no. 2, 216--221, a refereed journal (refereed), published online on 10 February 2009, the page's date, and in print in September 2009. The curator of erdosproblems.com, Thomas Bloom, credits the short proof 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.