Prove that at least one of the subsets is at most size $\sqrt{n}+1$

Question

Let $X$ be an $n$-element set, and let $S_1, ..., S_n$ be subsets of $X$ such that $\mid S_i \cap S_j \mid \leq 1$ whenever $1 \leq i < j \leq n$. Prove that at least one of the sets $S_i$ has size at most $\sqrt{n}+1$

I was thinking of taking an approach by contradiction by assuming for every $S_i$ we have $\mid S_i \mid \geq \sqrt{n}+1$.

I know $\mid S_i \cap S_j \mid = \mid S_i \mid + \mid S_j \mid - \mid S_i \cup S_j \mid$. But I have no further idea about how to go about proving the claim.

Answer 1

Let $X:=\{1,2,\dots,n\}$ and let's assume that the element $i\in X$ is in $d_i$ subsets of the list $S_1,\dots,S_n$. Then, by the assumption $\mid S_i \cap S_j \mid \leq 1$ whenever $1 \leq i < j \leq n$, it follows that $$\frac{1}{n}\binom{n}{2}\geq \frac{1}{n}\sum_{i=1}^n \binom{d_i}{2}\geq \binom{\frac{N}{n}}{2}.$$ where $$N=\sum_{i=1}^nd_i=\sum_{i=1}^n |S_i|.$$ Assume by contradiction that $|S_i|> \sqrt{n}+1$ for all $i$. Then $N>n(\sqrt{n}+1)$ and, by the above inequality, we have $$\frac{n-1}{2}=\frac{1}{n}\binom{n}{2}\geq \binom{\frac{N}{n}}{2}> \frac{1}{2}\left(\frac{N}{n}-1\right)^2>\frac{n}{2}$$ which is a contradiction.

Answer 2

Let $Y$ be a random variable uniformly distributed on $X$, and let $N$ be the number of subsets $S_i$ that $Y$ is in. (Using indicator functions, $N=\sum 1_{S_i}$).

Let $f=x^2-x$, a convex function.

Then we know via Jensen's inequality that $$\mathbb E[f(N)]\ge f(\mathbb E[N]).$$

The left hand side of this is just $$\frac1n\left(\sum_{i=1}^n\sum_{j=1}^n|S_i\cap S_j|-\sum_{i=1}^n|S_i|\right).$$ Cancelling the $S_i\cap S_i$ terms with the $S_i$ gives us a trivial upper bound of $\frac1nn(n-1)=n-1$.

On the other hand, if we let $S=\sum_{i=1}^n|S_i|$, then the RHS is equal to $S(S-1)$.

Therefore we know that $n-1\ge S(S-1)$ so $$\frac12+\sqrt{n-1+\frac14}\ge S$$

But the total number of elements across all sets is $Sn$ and there are $n$ sets, so one set has at most $S$ things in it. Thus it remains to show that $$\sqrt{n}+1\ge\sqrt{n-\frac34}+\frac12$$ which is trivial as every term on the left is greater than the corresponding term on the right.

An interesting thing to note is that equality (the minimum size of a set being $\sqrt{n-\frac34}+\frac12$, not your one) is actually attainable, if you make the elements points in a finite projective plane, and sets correspond to lines containing the points they are in. Thus this shows that this bound is in fact tight :)