Minimum number of edges for a \(n\)-graph to not have Property B (that is: to not be \(2\)-colorable)

A hypergraph \( H\) consists of a vertex set \( V\) together with a family \( E\) of subsets of \( V\), which are called the edges of \( H\). A \( r\)-uniform hypergraph, or \( r\)-graph, for short, is a hypergraph whose edge set consists of \( r\)-subsets of \( V\). A graph is just a special case of an \( r\)-graph with \( r=2\).

A family \( \mathcal{F}\) of sets is said to have property \( B \) if there is a subset \( S\) of vertices such that every set in \( \mathcal{F}\) contains an element in \( S\) and an element not in \( S\).

Property \( B \) is named after Felix Bernstein who first introduced this property in 1908 [3]. A hypergraph with Property \( B \) has chromatic number two.

A problem on Property B (proposed by Erdös [4], 1963)

What is the minimum number \(f(n)\) of subsets in a family \(\mathcal{F}\) of \(n\)-sets not having property \(B\)?

The best upper bound known for \( f(n)\) is due to Erdös [4] [5] and the following lower bound was given by Beck [2]:

\(\displaystyle n^{1/3-\epsilon} 2^n \leq f(n) < (1+ \epsilon) \frac{e \log 2}{4} n^2 2^n \)

for \( n \geq n_0\) and \( n_0\) depends only on \( \epsilon\). This problem was extensively considered in [1], [6].

Bibliography
1 N. Alon, J. H. Spencer and P. Erdös, The Probabilistic Method, Wiley and Sons, New York, 1992. (Link To sample sections.)

2 J. Beck, On \( 3\)-chromatic hypergraphs, Discrete Math. 24 (1978), 127-137.

3 F. Bernstein, Zur Theorie der trigonometrische Reihen, Leipz. Ber. 60 (1908), 325-328.

4 P. Erdös, On a combinatorial problem, Nordisk Mat. Tidskr. 11 (1963), 5-10, 40.

5 P. Erdös, On a combinatorial problem, II, Acta Math. Acad. Sci. Hungar. 15 (1964), 445-447.

6 T. R. Jensen and B. Toft, Graph Coloring Problems, John Wiley and Sons, New York, 1995.