# Prove that for a family of $100n$ subsets of a $[n]$ such that each subset has size $m$, there exists two whose intersection is at least $m^2/10n$.

Let $A_1, \ldots, A_k$ be subsets of $\{1, \ldots, n\}$ such that $|A_i| = m$ for each $i = 1,\ldots,k$ and $k>100n$. Prove that there exists two distinct sets $A_i, A_j$ such that $|A_i\cap A_j| \geq \frac{m^2}{10n}.$

I found this problem in the book Introduction to Theoretical Computer Science by Boaz Barak.

Here's my attempt: Suppose for contradiction that every pair of subsets satisfies $|A_i\cap A_j| < \frac{m^2}{10n}$. Then $$\sum_{1\leq i < j \leq k}|A_i\cap A_j| < {k\choose 2}\frac{m^2}{10n}.$$ It's also known from the principle of inclusion-exclusion that $$\left|\bigcup_{i=1}^k A_i\right| \geq \sum_{i=1}^k|A_i| - \sum_{1\leq i < j \leq k}|A_i\cap A_j|.$$ Then $$n\geq \left|\bigcup_{i=1}^k A_i\right| \geq \sum_{i=1}^k|A_i| - \sum_{1\leq i < j \leq k}|A_i\cap A_j| \geq km - {k\choose 2}\frac{m^2}{10n}$$ $$n^2 + {k\choose 2}\frac{m^2}{10n}\geq km.$$ I'm not sure how to proceed from here since it's pretty clear that the left side is bigger than the right side for large $n, m, k$ since it has a higher degree. Thanks in advance for any help.

• Looks like a fun problem. Please show your attempts on proving it yourself so when we offer help we don't spend time explaining concepts you already have a firm grasp on. – Andrew Tawfeek May 28 '18 at 16:39
• Is it likely that my entire approach to the problem is just wrong? – Anon May 28 '18 at 18:43
• @Anonymous I suspect that your approach is not going to work and a more direct pigeonhole application is required, but since I don't have a solution you should treat my suspicion with due caution. – Joffan May 29 '18 at 12:49

Your approach doesn't seem to work because your lower bound for $\sum |A_i \cap A_j|$ is not sharp enough.
Let $a_i$ be number of sets $A_j$ that $i$ belongs to. Hence, we have $$\sum_{i=1}^n a_i= \sum_{i=1}^k|A_i|=mk \; \text{and} \; \sum_{i=1}^n \binom{a_i}{2} = \sum_{1 \le i<j \le k} |A_i \cap A_j|$$ We have the inequality $$\sum_{i=1}^n \binom{a_i}{2} = \frac 12 \left[ \sum_{i=1}^n a_i^2-mk\right] \ge \frac 12 \left[ \frac 1n \left(\sum_{i=1}^na_i\right)^2-mk\right]= \frac{mk}{2} \left( \frac{mk}{n}-1\right).$$ Therefore, $$\binom{k}{2}|A_i \cap A_j|_{\max} \ge \frac{mk}{2}\left(\frac{mk}{n}-1\right).$$ We find $$|A_i\cap A_j|_{\max} \ge \frac{m}{k-1}\left(\frac{mk}{n}-1\right)> \frac{m^2}{n}-\frac{m}{k-1} \ge \frac{m^2}{n}-\frac{m}{100n}.$$