Unavoidable stars of an n-set

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.

A problem on unavoidable stars of an \(n\)-set (proposed by Erdös and Szemerédi [3])

Determine the least integer \(m\), denoted by \(f^*(n,k)\), such that for any family \(\mathcal{A}\) of subsets of an \(n\)-set with \(|{\mathcal{A}}| > f^*(n,k)\), \(\mathcal{A}\) must contain a \(k\)-star.

Erdös and Szemerédi [3] showed that

\(\displaystyle f^*(n,3) < 2^{(1-1/(10\sqrt{n}))n} \)

and they observed that the probabilistic methods imply that

\(\displaystyle f^*(n,r) > (1+c_r)^n \)

where \( c_r > 0\) for \( r > 3\) and \( c_r \rightarrow 1\) as \( r \rightarrow\infty.\) They stated [3], " It is easy to see that

\(\displaystyle \lim_{n \rightarrow \infty} (f^*(n,r))^{1/r} \rightarrow c_r+1 \)

exists but we cannot even prove \( c_3 < 1\)".

Recently, Deuber, Erdös, Gunderson, Kostochka and Meyer [1] proved that for a fixed \( c\),

\(\displaystyle f^*(n,r) > 2^{ n ( 1 - \log\log r / 2r - c/r) } \)

for every \( r \ge 3 \) and infinitely many \( n\) and, in particular,

\(\displaystyle f^*(n,3) > 1.551^{n-2} \)

for infinitely many \( n\). For the upper bound, they showed that

\(\displaystyle f^*(n,r) < 2^{n-\frac{\sqrt{n \log \log n}}{\log \log \log n} }. \)

Bibliography
1 W. A. Deuber, P. Erdös, D. S. Gunderson, A. V. Kostochka, A. G. Meyer, Intersection Statements for Systems of Sets, J. Comb. Theory, Ser A 79 (1997), 118-132.

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

3 P. Erdös and E. Szemerédi, Combinatorial properties of systems of sets, J. Comb. Theory Ser. A 24 (1978), 308-313.