# Showing ${1\over n}\sum|S_i|=O(\sqrt n)$ for $S_i\subset$, $|S_i\cap S_i|\le 1$ for $i\ne j$

Show ${1\over n}\sum|S_i|=O(\sqrt n)$ where $S_i\subset [n]$, $|S_i\cap S_i|\le 1$ for $i\ne j$. A previous question required showing $|E|\le {1\over 2}(\sqrt{t-1}n^{3\over 2}+n)$, for an $n$-vertex graph $G$. What I tried to do is placing $S_1,…,S_n$ in a row, and below it setting $1,…,n$ likewise. While I didn’t mind the fact that as a graph, $S_i$ cannot be connected to $S_j$ as it will have no meaning here, I did pay attention to the restrictions I am given: I can’t have a $K_{2,2}$ graph (also not a $K_{2,t\ge 2}$, but $t=2$ is tighter.). Is what I am doing admissible? If so, I am arriving at: $|E|\le {1\over 2}(\sqrt 2n^{3\over 2}+2n)$. Acknowledge(or at least assuming) that the number of edges is simply the sum of $|S_i|$’s, I get ${1\over n}\sum|S_i|\le \sqrt2n^{1\over 2}+2$ which seems $O(\sqrt n)$. Is it graph theory acceptable arguing? I would really appreciate your insights.

#### Solutions Collecting From Web of "Showing ${1\over n}\sum|S_i|=O(\sqrt n)$ for $S_i\subset$, $|S_i\cap S_i|\le 1$ for $i\ne j$"

If you assume to have $k$ almost-disjoint (that means $|S_i\cap S_j|\leq 1$ for any $i\neq j$) subsets of $\{1,2,\ldots,n\}$, any element $m\in\{1,2,\ldots, n\}$ can be labeled according to the subsets $S_i$ to which it belongs. Assume that $m$ belongs to $c(m)$ different subsets: then $\sum |S_i| = \sum_{m=1}^{n} c(m)$, but we must have
$$\sum_{m=1}^{n}\binom{c(m)}{2}\leq \binom{k}{2}\leq\binom{n}{2}$$
so, by the Cauchy-Schwarz inequality, it follows that:
$$\left(-n+\sum_{m=1}^n c(m)\right)^2 \leq n^3$$
and:
$$\frac{1}{n}\sum |S_i| \leq \sqrt{n}+1.$$