1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ HAve you tried INDUCTION on $n$? $\endgroup$ – Tito Eliatron Jun 10 '20 at 10:59
  • $\begingroup$ @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$ $\endgroup$ – Myro Jun 10 '20 at 11:11
  • $\begingroup$ 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$? $\endgroup$ – Myro Jun 10 '20 at 11:13
  • $\begingroup$ 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}\}$. $\endgroup$ – Tito Eliatron Jun 10 '20 at 11:18
  • 1
    $\begingroup$ This should answer your question: math.stackexchange.com/a/1750335. $\endgroup$ – Martin R Jun 10 '20 at 12:10
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.