Intersecting families

Question

Suppose A, B, C are 3 subsets of the set {1,...,n} Where each pair has nonempty intersect. Is there any intersecting family F from {1,...,n} subsets where F cardinality is equal to 2^(n-1) and F contains A, B and C?

Answer 1

HINT: If $A\cap B\cap C\ne\varnothing$, it’s pretty easy to find such an $F$. If not, there is a $3$-element set $\{a,b,c\}\subseteq[n]$ such that $a\in B\cap C$, $b\in A\cap C$, and $c\in A\cap B$. Let $F$ be the family of all subsets of $[n]$ that contain at least two of the points $a,b$, and $c$.

• Show that $F$ is an intersecting family.
• Use an inclusion-exclusion argument to show that $|F|=2^{n-1}$.

If you get completely stuck, I’ve added a further hint in the spoiler-protected block below; mouse over to see it.

How many subsets of $X$ contain both $a$ and $b$? Both $a$ and $c$? Both $b$ and $c$? If you add these three numbers together, how often have you counted each of the subsets of $X$ that contains all three of $a,b$, and $c$?