Special case: unavoidable \(3\)-stars

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 Erdös 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

\(\displaystyle 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.

Conjecture [2]

\[ f(n,3) \leq c^n \] for some absolute constant \(c\).

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

\(\displaystyle 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. Erdös 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 Erdös, 229-235, Springer-Verlag, Berlin, 1996.

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