Unavoidable 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 [1] 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. Erdös and Rado [1] showed that

\(\displaystyle (t-1)^r \leq f(r,t) \leq r!(t-1)^r. \)

The lower bound is derived by considering \( r\)-partite complete \( r\)-graphs with each part consisting of \( t-1\) vertices. The upper bound can be proved by induction on \( r\) using the observation that the maximum number of mutually disjoint \( r\)-edges is \( t-1\).

A problem on unavoidable stars $1000 (proposed by Erdös and Rado [1] in 1960)

For given integers \(r\) and for any \(t \geq 3\), decide if \[ f(r,t) \leq c_t^r \] where \(c_t\) depends only on \(t\) (and is independent of \(r\)).

In Erdös' problem papers, he often liked to mention the case of \( t=3\) (e.g., see [2]). See also this problem.


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

2 P. Erdös and R. Rado, Intersection theorems for systems of sets, II, J. London Math. Soc. 44 (1969), 467-479.