Weak \(\Delta\)-systems 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\).

A family \( {\mathcal A} = (A_1, \ldots, A_s)\) is called a weak \( \Delta\)-system if \( A_i \cap A_j\), for \( i \not = j\), are all of the same size. Erdös and Szemerédi [1] considered the problem on weak \( \Delta\)-systems which consist of subsets of a given \( n\)-set:

A problem on weak \(\Delta\)-systems of an \(n\)-set (proposed by Erdös and Szemerédi [1])

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

Erdös and Szemerédi [1] proved that

\(\displaystyle g^*(n,3) > n^{\log n/ 4 \log \log n}. \)

Recently, Rödl and Thoma [3] proved that \( g^*(n,r) \geq 2^{\frac 1 3 n^{1/5} \log^{4/5} (r-1)}\) for \( r \geq 3\). For the upper bound on \( g^*(n,r)\), Frankl and Rödl [2] proved that \( g^*(n,k) < (2-\epsilon)^n\), where \( \epsilon\) depends only on \( k\).

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

2 P. Frankl and V. Rödl, Forbidden intersections, Trans. Amer. Math. Soc. 300 (1987), 259-286.

3 V. Rödl and L. Thoma, On the size of set systems on \( [n]\) not containing weak \( (r,\Delta)\)-systems, preprint.