\(r\)-sets with common union and intersection

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 conjecture of Erdös and Füredi} [2]

Suppose that \(A_1, \ldots, A_s\) are distinct \(r\)-sets of an \(n\)-set. If \(s = \binom n {r-1} +1\), then there are always four sets \(A_i, A_j, A_l, A_k\) satisfying \begin{equation*} A_i \cup A_j = A_l \cup A_k, A_i \cap A_j = A_l \cap A_k = \emptyset . \end{equation*}

Füredi [2] solved an earlier conjecture of Erdös by showing that \( s= 1+ \frac 7 2 \binom{n}{r-1}\) is already enough, and there are families with \( s=\binom{n-1}{r-1} + \lfloor (n-1)/r \rfloor\) members which have the property that all disjoint pairs have disjoint unions.

Erdös originally considered the case of \( r=3\) and he wrote [1],

It is perhaps of interest to investigate how many \( A\)'s are needed if \( \vert A_i\vert=r\), or if we require \( k\) pairs of \( A\)'s instead of only two. Our conjecture with \( \binom{n}{2}\) is pleasing because there are so few exact results for extremal results for \( r\)-tuples \( r \geq 3\).

Bibliography
1 P. Erdös. Problems and results on set systems and hypergraphs. Extremal problems for finite sets (Visegrád, 1991), Bolyai Soc. Math. Stud., 3, pp. 217-227, János Bolyai Math. Soc., Budapest, 1994.

2 Z. Füredi. Hypergraphs in which all disjoint pairs have distinct unions. Combinatorica 4 (1984), 161-168.