---

Claim. Theorem 1 of the paper states $m(n)<n^22^{n+1}$ for the least number $m(n)$ of edges of an $n$-uniform hypergraph that is not 2-colorable, the function of Problem 901. The proof is non-constructive: $n$-element subsets of a ground set of $2n^2$ points are chosen one at a time, each choice cutting the number of 2-colorings that still split every chosen set by a factor $1-2^{-n}$, until no 2-coloring survives. A more careful count with a smaller ground set gives the refinement $m(n)<(1+\epsilon)e(\log2)\,n^22^{n-2}$ for large $n$. The paper also reviews Schmidt's lower bound $2^n(1+4/n)^{-1}<m(n)$ and deduces $\lim m(n)^{1/n}=2$, and Erdős guesses that the truth is of order $n2^n$. The source card records the theorem and the refinement.

Covers. The upper bound $m(n)\le n^22^{n+1}$, the site's $m(n)\ll n^22^n$; no better upper bound is on record. The order of $m(n)$ stays open: the best lower bound is Radhakrishnan and Srinivasan's [[problems/set_systems/E0901/claims/2000_01_01_radhakrishnan_srinivasan|$0.7\sqrt{n/\ln n}\,2^n$]].

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

Acceptance. P. Erdős, On a combinatorial problem. II, Acta Math. Acad. Sci. Hungar. 15 (1964), no. 3--4, 445--447, a refereed journal (refereed); the record dates the issue to September 1964 without a day, so the page is dated to the first day of that month. The curator of erdosproblems.com, Thomas Bloom, credits the upper 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.