Family of Pairs of Subsets using Probabilistic Method

Question

Let $\{(A_i, B_i) | 1 \le i \le h\}$ be a family of pairs of sets such that $|A_i| + |B_i| = k$ for all $i$, $A_i \cap B_i = \emptyset$ and $(A_i \cap B_j) \cup (A_j \cap B_i) \ne \emptyset$ for $i \ne j$. Prove that $h \le 2^k$.

I think I am supposed to somehow incorporate $\sum_i \binom{n}{|A_i|}$ as that should get me to $2^k$. Can anyone point me in the right direction?

Answer 1

Define the set $S = \bigcup_{i = 1}^h (A_i \cup B_i)$ (in other words, the union of all the elements in all the $A_i$ and $B_i$). Suppose that for every element $s \in S$, we color $s$ either blue or red. Let $E_i$ denote the event where all the $A_i$ are blue and all the $B_i$ are red.

From here, we can realize that $E_i$ and $E_j$ are disjoint for all $i \neq j$. In other words, it's impossible that all the elements of $A_i$ were blue and $B_i$ were red, and simultaneously to have all the elements of $A_j$ blue and all the $B_j$ red for $i \neq j$. Why is this? Hint: this relies on the conditions given in the problem about the unions of $(A_i \cap B_j)$ and $(A_j \cap B_i)$.

Thus, the probability that one of the $E_i$ is satisfied is just the sum of $h$ identical probabilities, in other words $$\mathbb{P}(E_1 \cup E_2 \cup \cdots \cup E_h) = h \mathbb{P}(E_1) \leq 1$$ But it can be checked that $\mathbb{P}(E_1) = 1/2^k$, since we need to color every element in $A_i \cup B_i$ the color we want (blue for the elements of $A_i$, and red for the elements of $B_i$). Hence, it follows $h \leq 2^k$.

Answer 2

Let $X$ be the support of the family (i.e., $X = \bigcup_i A_i \cup B_i$) and consider a subset $V \subseteq X$ chosen u.a.r (each $x \in X$ is in $V$ with probability $1/2$ independently).

Denote by $E_i(V)$ the event where $V$ "splits" $A_i$ and $B_i$, meaning that for all $a \in A_i$ we have $a \in V$ and for all $b \in B_i$ we have $b \notin V$. Clearly, $\Pr_V[E_i(V) = 1] = 1/2^k$ as we need to make all "choices" in $A_i \cup B_i$ "correctly".

Now note that given a subset $V$, these events are disjoint: if $E_i(V) = 1$ and $E_j(V) = 1$ and we have some $x \in A_i \cap B_j$ (wlog), then $x \in V$ by $E_i$ and $x \notin V$ by $E_j$.

It follows that $\Pr_V[\exists ~ E_i(V)=1] = \sum_i \Pr_V[E_i(V) = 1] = \frac{h}{2^k} \leq 1$ where the first equality is due to disjointness.