For $n$ sets with intersection of size at most $1$ sets we have $\frac{1}{n}\sum\limits_{i=1}^{n}|S_i|=O(\sqrt n)$ Suppose $S_1,\dots, S_n\subseteq[n]$ are such that $|S_i\cap S_j|\leq 1$ for all $1\leq i\lt j\leq n$. Show that in this case
$$\frac{1}{n}\sum\limits_{i=1}^{n}|S_i|=O(\sqrt n).$$
 A: Let's consider the following bipartite graph $G = ((S_{[n]}, [n]), E)$, where vertices of the first part are sets $(S_i)$, vertices of the second part are numbers and there is an edge between set $S_i$ and number $j$ iff $j \in S_i$. It is easy to see that $G$ is bipartite $C_4$-free graph and $|E| = \sum_{i = 1}^n |S_i|$.
Therefore let's count the maximum number of edges in $G$. Let's count the number $x$ of subgraphs $P_3$ where middle vertex is a set, that is the number of pairs of numbers that belong to the same set. On one hand it is exactly $x = \sum_{i = 1}^n \binom{|S_i|}{2}$. On the other hand $x \le \binom{n}{2}$ because each pair can belong to at most one set. So we have
$$\begin{align}
\sum_{i = 1}^n \binom{|S_i|}{2} &\le \binom{n}{2},\\
\sum_{i = 1}^n |S_i|^2 - \sum_{i = 1}^n |S_i| &\le n^2 - n,\\
\sum_{i = 1}^n |S_i|^2 &\le n^2 - n + \sum_{i = 1}^n |S_i|.\\
\end{align}$$
Remember that
$$ \frac{\sum_{i = 1}^m a_i}{m} \le \sqrt{\frac{\sum_{i = 1}^m a_i^2}{m}}$$
or
$$ \left(\sum_{i = 1}^m a_i\right)^2 \le m\sum_{i = 1}^m a_i^2$$
by Cauchy inequality for any real numbers $a_i$. Then
$$\left(\sum_{i = 1}^n |S_i|\right)^2 \le n\sum_{i = 1}^n |S_i|^2 \le n^3 - n^2 + n\sum_{i = 1}^n |S_i|,\\
|E|^2 \le n^3 - n^2 + n|E|,\\
|E|^2 - n|E| - n^3 + n^2 \le 0,\\
\left(|E| - \frac{n + n\sqrt{4n - 3}}2\right)\left(|E| - \frac{n - n\sqrt{4n - 3}}2\right) \le 0,\\
\frac{n - n\sqrt{4n - 3}}2 \le |E| \le \frac{n + n\sqrt{4n - 3}}2 = O(n\sqrt n).$$
Thus $\frac1n\sum |S_i| = \frac{|E|}n = O(\sqrt n)$.
