P103.4.1.2018.3.2 Let $A_1$, $A_2$, $\cdots$, $A_m$ be $m$ subsets of a 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.$$

Solution


Let the set of size $n$ be $\{1,2,\ldots,n\}$, and construct a bipartite graph $G$ between vertex sets $\{v_1,v_2,\ldots,v_m\}$ and $\{w_1,w_2,\ldots,w_n\}$ where $v_i$ is connected to $w_j$ iff $i\in A_j$. Let $N$ be the number of tuples $(p,q,r,s)$ such that $v_p$ is connected to $w_q$, $w_q$ is connected to $v_r$, and $v_r$ is connected to $w_s$, i.e. the number of walks of length 3 in $G$. Suppose that there are $e$ edges in $G$, and note that $\sum_{i=1}^m|A_i|=e$.

First, note that the LHS is equal to $N$. Indeed, given $q$ and $s$, there are $|A_q|$ choices for $p$ and $|A_q\cap A_s|$ choices for $r$. Summing over all pairs $(q,s)$ gives the result.

Now, summing over all pairs $(q,r)$ instead, we have that $N=\sum_{v_i-w_j}\deg v_i\cdot\deg w_j$. Now, note that by Holder's inequality we have that
\[\left(\sum_{v_i-w_j}\frac1{\deg v_i}\right)\left(\sum_{v_i-w_j}\frac1{\deg w_j}\right)\left(\sum_{v_i-w_j}\deg v_i\cdot\deg w_j\right)\ge\left(\sum_{v_i-w_j}1\right)^3\]
\[\left(\sum_{v_i}1\right)\left(\sum_{w_j}1\right)N\ge e^3\]
\[N\ge\frac{e^3}{mn}\]

 

 

 

as desired.