4
$\begingroup$

Suppose, given a ground set $S$, we have two subsets $A,B \subseteq S$.

If we know that $|A|, |B| > \frac{|S|}{2}$, then we know that $A \cap B \neq \emptyset$.

Can this be generalized to $k$ sets? Does it hold that when $|A_1|, \dotsc, |A_k| > \frac{|S|}{k}$ for subsets $A_i \subseteq S$, then $\bigcap_{i=1}^k A_i \neq \emptyset$? My guess is no, that it only hold that there are $i,j$ such that $A_i \cap A_j \neq \emptyset$.

But I would like to have a sufficient condition to conclude that the overall intersection is not empty. Do you know an easy one?

Thanks a lot!

$\endgroup$
4
$\begingroup$

Your guess is right. For instance, taking $k=3$ and $S=\{1,2,3\}$, you could take $A_1=\{1,2\}$, $A_2=\{1,3\}$ and $A_3=\{2,3\}$.

To find a condition on $S$ that works, it helps to think about the complements of the $A_i$. Write $B=S\setminus A_i$. Then $$\bigcap_{i=1}^k A_i=S\setminus \bigcup_{i=1}^k B_i.$$ The condition is now obvious: to be sure that $\bigcup_{i=1}^k B_i$ is not all of $S$ using a uniform condition on their sizes, you need to know that $|B_i|<|S|/k$ for all $i$. This means you need to know that $$|A_i|>\frac{k-1}{k}|S|$$ for all $i$. You can see that for $k=2$ this is the same as $|A_i|>|S|/k$, but for larger $k$ it is a much stronger condition.

$\endgroup$
  • $\begingroup$ Thanks a lot, this was really helpful and exactly what I was looking for! Great! $\endgroup$ – user136457 Apr 22 '16 at 4:27

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.