---

Claim. Theorem 1 of the paper gives a sufficient condition for a family of finite sets $A_i$ with $|A_i|=\alpha_i\ge2$ to have property B, that is, to admit a set meeting every $A_i$ and containing none; the proof counts, by inclusion and exclusion, the subsets of the ground set that split every $A_i$. For $n$-element sets the condition yields $m(n)>2^{n-1}$ and, for every $\epsilon>0$ and all large $n$, $m(n)>(1-\epsilon)2^n\log2$, where $m(n)$ is the least number of edges of an $n$-uniform hypergraph that is not 2-colorable, the function of Problem 901. The paper also records $m(2)=3$ and $m(3)=7$, the latter attained by the seven lines of the Fano plane, and says that $m(4)$ is unknown. The source card records the theorem and the lemma behind it.

Covers. The lower bound $m(n)>2^{n-1}$, the site's $m(n)\gg2^n$. The order of $m(n)$ stays open: the later lower bounds are Beck's [[problems/set_systems/E0901/claims/1977_01_01_beck|$c(\log n)2^n$]] and [[problems/set_systems/E0901/claims/1978_01_01_beck|$n^{1/3-o(1)}2^n$]], Radhakrishnan and Srinivasan's [[problems/set_systems/E0901/claims/2000_01_01_radhakrishnan_srinivasan|$0.7\sqrt{n/\ln n}\,2^n$]] and Pluhár's [[problems/set_systems/E0901/claims/2009_02_10_pluhar|$0.5268\,n^{1/4}2^n$]], 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; the proof is self-contained.

Acceptance. P. Erdős, On a combinatorial problem, Nordisk Mat. Tidskr. 11 (1963), 5--10, 40, a refereed journal (refereed); the link above is the copy in the Rényi Institute's Erdős archive. The curator of erdosproblems.com, Thomas Bloom, credits the lower 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.