Upper bound on cumulative power of system of limitedly intersecting subsets?

Question

We have a set $S$ of power $n$ and $k < n$ subsets $S_1, \ldots, S_k \subseteq S$ such that $|S_i \cap S_j| \le 1$ when $i \ne j$. Is there any nontrivial upper bound on total power of sets $S_1, \ldots, S_k$? In particular, is it true that $$\sum_{i=1}^k |S_i| = O(n)$$

Answer 1

Say an element $i$ is in $d_i$ sets. Then we have $$\sum ^k |S_i| = \sum ^n d_i =:m$$

Beacuse of $|S_i\cap S_j|\leq 1$ we have (with use of Cauchy inequality):

$$ {k\choose 2} = \sum ^n {d_i\choose 2} \geq {{1\over n}m^2-m\over 2}$$

so from here we get

$$ m\leq n\cdot {1+\sqrt{1+{8\over n}\cdot {k\choose 2}}\over 2} =O(n\sqrt{n})$$

Answer 2

The Bonferroni inequalities (basically a truncated version of the inclusion–exclusion principle) can be brought to bear: $$ \left|\bigcup_{i=1}^kS_i\right| \ge \sum_{i=1}^k |S_i| - \sum_{i<j}\left|S_i\cap S_j\right| \ge \sum_{i=1}^k|S_i| - \frac{k(k-1)}{2}, $$ hence $$ \sum_{i=1}^k|S_i| \le \left|\bigcup_{i=1}^kS_i\right| + \frac{k(k-1)}{2} \le n + \frac{n(n-1)}{2}, $$ which is enough to bound your sum with $ O(n^2) $. I'm not sure you can do any better, although I wouldn't be surprised if your stricter bound were to be found to hold.