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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Andrew Tawfeek May 28 '18 at 16:39
  • $\begingroup$ Is it likely that my entire approach to the problem is just wrong? $\endgroup$ – Anon May 28 '18 at 18:43
  • $\begingroup$ @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. $\endgroup$ – 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}.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.