I am trying to prove the following claim. I did not find the claim in a book, but I believe it to be true.

Claim: Consider a finite set $P\neq \emptyset$ and subsets $S_1, S_2, S_3 \subset P$, each of size $s$. Suppose $s > \frac{2}{3} |P|$. Prove that $S_1 \cap S_2 \cap S_3 \neq \emptyset$.

Here is my proof.

Proof: Consider the elements of $S_1$ and $S_2$. There must be at minimum $\left\lfloor \frac{2|P|}{3} \right\rfloor + 1$ elements in each set. Therefore $$\begin{align*} |P - S_1| &= |P| - s \\ &\le |P| - \left\lfloor \frac{2|P|}{3} \right\rfloor - 1 \\ &= \left\lceil \frac{|P|}{3} \right\rceil - 1 \end{align*}$$ Thus $S_1$ and $S_2$ can have at most $\left\lceil \frac{|P|}{3} \right\rceil - 1$ distinct elements. The other elements must belong to their intersection. $$\begin{align*} |S_1 \cap S_2| &\ge \left\lfloor \frac{2|P|}{3} \right\rfloor + 1 - \left(\left\lceil \frac{|P|}{3} \right\rceil - 1\right)\\ &\ge \left\lfloor \frac{2|P|}{3} \right\rfloor - \left\lfloor \frac{|P|}{3} \right\rfloor + 1\\ &= \left\lfloor \frac{|P| + 1}{3} \right\rfloor + 1 \end{align*}$$

Thus, $$\begin{align*} |S_1 \cap S_2 \cap S_3| &= |S_1 \cap S_2| + |S_3| - |(S_1 \cap S_2) \cup S_3| \\ &\ge \left\lfloor \frac{|P| + 1}{3} \right\rfloor + 1 + \left\lfloor \frac{2|P|}{3} \right\rfloor + 1 - |P|\\ &>0 \end{align*}$$

I am looking for verification, criticism, and for alternative proofs.


Here is how I would prove it.

Count the total membership count, that is, the total number of times it happens that $p\in S_i$, for any point $p\in P$ and any of the sets $S_i$. Since each set $S_i$ is more than 2/3 of the points in $P$, this total membership count is strictly more than $3\cdot \frac 23|P|$. Thus, the total membership count is strictly more than $2|P|$.

But if no point $p$ is in all three sets, then every point is in at most two $S_i$, and so the total membership count would be at most $2|P|$, a contradiction.

This way of arguing shows the stronger result: you only need one of the sets to have strictly more than 2/3 of the points, if the other two sets have at least 2/3 of the points.

The argument generalizes to $k$ sets, provided that each of them has fraction $\frac{k-1}k$ of the total, with at least one having strictly more than this. In the case of two sets, this is the simple assertion that if $A$ has at least half the points and $B$ has more than half, then $A\cap B$ is not empty.


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.