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$.

By considering the lines of a finite geometry, the following upper bound can be easily obtained:

$$f(n) \leq n^2-n+1.$$

Erds and Lovász [2] proved that

$$\frac 8 3 n -3 \leq f(n) \leq c n^{3/2} \log n.$$

Kahn [3] showed that $f(n) = O(n)$. For the lower bound for $f(n)$, Dow et al [1] proved that $f(n) > 3n$ for $n \geq 4$.

Bibliography

1

S. J. Dow, D. A. Drake, Z. Füredi and J. A. Larson. A lower bound for the cardinality of a maximal family of mutually intersecting sets of equal size. Proceedings of the sixteenth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congr. Numer. 48 (1985), 47-48.

2

P. Erds and L. Lovász, Problems and results on 3-chromatic hypergraphs and some related questions, Infinite and finite sets (Colloq., Keszthely, 1973; dedicated to P. Erds on his 60th birthday), Vol. I; Colloq. Math. Soc. János Bolyai, Vol. 10, 609-627, North-Holland, Amsterdam, 1975.

3

J. Kahn, On a problem of Erds and Lovász: random lines in a projective plane, Combinatorica 12 (1992), 417-423.