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

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.

• HAve you tried INDUCTION on $n$? – Tito Eliatron Jun 10 '20 at 10:59
• @TitoEliatron I have not! So let's see, for $n=1$ the claim clearly holds for a single element set with $1$ subset. Now assume for an $n$-element set with subsets $S_1, ..., S_n$ there is a $k$ with $1 \leq k \leq n$ with $\mid S_k \mid \leq \sqrt{n}+1$ – Myro Jun 10 '20 at 11:11
• For the inductive step we consider the set $X$ but with an extra element $x_{n+1}$ and subset $S_{n+1}$ satisfying the intersection condition. We seek to prove there is now also a $k$ such that $\mid S_k \mid \leq \sqrt{n+1}+1$ But does this induction make sense? How do I know I can build a set $S_{n+1}$ to meet the criteria by adding a new element to $X$? – Myro Jun 10 '20 at 11:13
• I think the extra element can only be part of, at most, two subsets.... (say $X_{n}$ and $X_{n+1}$). So yopu can apply Induction Hypothesis to $X_1,X_2,...X_{n-1},\tilde{X_n}$ where $\tilde{X_n}=X_n\setminus\{x_{n+1}\}$. – Tito Eliatron Jun 10 '20 at 11:18
• This should answer your question: math.stackexchange.com/a/1750335. – Martin R Jun 10 '20 at 12:10

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.

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 :)