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

Let us call a family ${\mathcal S } = (S_1, S_2, \ldots, S_r)$ of $r$-graphs $S_i$, a $t$-star with center $A$, if for all $i <j$, $S_i \cap S_j = A$ (possibly empty). Stars were introduced by Erds and Rado [2] in 1960 under the name strong delta systems, where they proved that every large $r$-graph contains a $t$-star. Let $f(r,t)$ denote the maximum number of $r$-sets one can have without containing a $t$-star. Here, we consider the case that $t=3$. It is known [2] that

$$2^n < f(n,3) \leq 2^n n! .$$

Abbott and Hanson [1] proved $f(n,3) > 10^{n/2}$. Spencer [4] showed $f(n,3) < (1+\epsilon)^n n!$ for any $\epsilon >0$ if $n$ is large enough.

The current best bound is due to Kostochka [3]:

$$f(n,3) < n! \left( \Frac{c \log \log n}{\log n } \right)^n .$$

Bibliography

1

H. L. Abbott and D. Hanson, On finite $\Delta$-systems, Discrete Math. 8 (1974), 1-12.

2

P. Erds and R. Rado, Intersection theorems for systems of sets, J. London Math. Soc. 35 (1960), 85-90.

3

A. V. Kostochka, A bound of the cardinality of families not containing $\Delta$-systems, The Mathematics of Paul Erds (R. L. Graham and J. Nešetil, eds.), 229-235, Springer-Verlag, Berlin, 1996.

4

J. Spencer, Intersection theorems for systems of sets, Canad. Math. Bull. 20 (1977), 249-254. No link found.