Editing Property B (section)

=== Asymptotics of ''m''(''n'') ===
Erdős (1963) proved that for any collection of fewer than <math>2^{n-1}</math> sets of size ''n'', there exists a 2-coloring in which all set are bichromatic. The proof is simple: Consider a random coloring. The probability that an arbitrary set is monochromatic is <math>2^{-n+1}</math>. By a [[union bound]], the probability that there exist a monochromatic set is less than <math>2^{n-1}2^{-n+1} = 1</math>. Therefore, there exists a good coloring.

Erdős (1964) showed the existence of an ''n''-uniform hypergraph with <math>O(2^n \cdot n^2)</math> hyperedges which does not have property B (i.e., does not have a 2-coloring in which all hyperedges are bichromatic), establishing an upper bound. 

Schmidt (1963) proved that every collection of at most <math>n/(n+4)\cdot 2^n</math> sets of size ''n'' has property B. Erdős and Lovász conjectured that <math>m(n) = \theta(2^n \cdot n)</math>. Beck in 1978 improved the lower bound to <math>m(n) = \Omega(n^{1/3 - \epsilon}2^n)</math>, where <math>\epsilon</math> is an arbitrary small positive number. In 2000, Radhakrishnan and Srinivasan improved the lower bound to <math>m(n) = \Omega(2^n \cdot \sqrt{n / \log n})</math>. They used a clever probabilistic algorithm.