Skip to main content
3 of 3
edited tags
Andrés E. Caicedo
  • 32.5k
  • 5
  • 133
  • 240

Large Intersecting Subsets of a Set

I am sure the answer to this question is well known, but I am not able to figure it out.

Question: Let $U$ be a finite set. Let $F=(S_1,S_2,...,S_n)$ be such that:

(1) $S_i\subset U$

(2) $|S_i|=n$

(3) $|S_i\cap S_j|\leq n/2$

Then, what is the lowerbound on $|U$|? In other words, what is the smallest $U$ for which there exists an $F$ satisfying the above conditions.

Clearly, if $U$ has size $n^2$, it easy to construct such an $F$. You can also do this with just $n^2/2$ elements in $U$. Can you do this with just $O(n)$ elements? What about $O(n^{1+\epsilon})$ for a constant $\epsilon<1$?