5
$\begingroup$

Let $A_1,A_2,\cdots,A_m$ be $m$ subsets of the set of size $n$ . Prove that $$\sum_{i=1}^{m} \sum_{j=1}^{m}|A_i|\cdot |A_i \cap A_j|\geq \frac{1}{mn}\left(\sum_{i=1}^{m}|A_i|\right)^3.$$

Someone know what this inequality background? The article studies such problems? Thank you.

Idea: it seem this inequality with The sum can be written in terms of indicator functions as solve it? How to it?

$\endgroup$
0

1 Answer 1

3
$\begingroup$

Hint. Let $\{1,2,\dots,n\}$ be the given set of size $n$ and let $X_k:=\{i:k\in A_i\}$ for $k=1,\dots,n$. Then show that $$\sum_{i=1}^{m} \sum_{j=1}^{m}|A_i|\cdot |A_i\cap A_j|=\sum_{i=1}^{m}\sum_{k\in A_i}|A_i||X_k|=\sum_{k=1}^{n}\sum_{i\in X_k}|A_i||X_k|.$$ Finally, the conclusion follows by Hölder's inequality with three functions, $$ \underbrace{\left(\sum_{i=1}^{m} \sum_{k\in A_i}\frac{1}{|A_i|}\right)}_{m}\cdot\underbrace{\left(\sum_{k=1}^{n}\sum_{i\in X_k}\frac{1}{|X_k|}\right)}_n\cdot\underbrace{\left(\sum_{i=1}^{m} \sum_{k\in A_i}|A_i||X_k|\right)}_{\sum_{i=1}^{m} \sum_{j=1}^{m}|A_i|\cdot |A_i\cap A_j|}\geq \underbrace{\left(\sum_{i=1}^{m} \sum_{k\in A_i}1\right)^3}_{\left(\sum_{i=1}^{m}|A_i|\right)^3}.$$

$\endgroup$
5
  • $\begingroup$ How did you come up with that last inequality? $\endgroup$ Jan 6, 2018 at 18:25
  • $\begingroup$ @martycohen Probably by looking at the exponent $3$ on the RHS. $\endgroup$
    – Robert Z
    Jan 6, 2018 at 18:53
  • $\begingroup$ I am not saying that $|A_{i}\cap A_{j}|=|X_{k}|$... Moreover $\sum_{i=1}^{m}\dfrac{1}{|A_{i}|}\sum_{k\in A_{i}}1=\sum_{i=1}^{m}\dfrac{|A_i|}{|A_{i}|}=m$. $\endgroup$
    – Robert Z
    Jan 7, 2018 at 16:26
  • $\begingroup$ @inequality I gave you a hint to think about... Now show your efforts and try to prove that equality on your own! $\endgroup$
    – Robert Z
    Jan 8, 2018 at 5:26
  • $\begingroup$ @inequality Thank you for your downvote!! $\endgroup$
    – Robert Z
    Jan 8, 2018 at 6:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .