My question is one from my graph & set theory class that I'm not sure how to solve. Any help would be greatly appreciated.
Let $\{(A_i, B_i) \mid 1 \leq i \leq h\}$ be a family of pairs of sets satisfying
- $A_i \cap B_i = \varnothing$ for $i = 1, \ldots, h$;
- $\left|A_i\right| + \left|B_i\right|=k$ for $i=1, \ldots , h$; and
- for $i\neq j$, at least one of $A_i \cap B_j$ or $A_j \cap B_i$ is nonempty.
Show that $h\leq 2^k$.
Is $h = 2^k$ always attainable?
I tried to use the following theorem: If $A_1, . . . , A_m$ and $B_1, . . . , B_m$ are two sequences of sets such that $A_i \cap B_j = \varnothing$ if and only if $i = j$, then $$ \sum_{i=1}^m{\binom{|A_i|+|B_i|}{|A_i|}}^{-1}\le 1. $$