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.

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

$$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. Erds, 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. Erds, On a combinatorial problem, Nordisk Mat. Tidskr. 11 (1963), 5-10, 40.

5

P. Erds, 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.