Lesson 6

Theorem (Erdős, 1963). Let \(\mathcal{F}\subseteq 2^{U}\) be a family of subsets of the finite set \(U\), each of size \(n\). If \(|\mathcal{F}| < 2^{n-1}\), then there exists a coloring \(c \colon U \to \{0,1\}\) such that each set in \(\mathcal{F}\) is not monochromatic (i.e. for any \(F \in \mathcal{F}\) there exist \(u,v \in F\), such that \(c(u) \neq c(v)\)).

Proof. Color each element of \(U\) randomly in one of two colors. For the set \(F \in \mathcal{F}\), denote the event “\(F\) is monochromatic” by \(A_{F}\). Clearly, \(\Pr[A_{F}]=2^{1-n}\). Thus, by the union bound, \[\Pr\left[ \bigcup_{F \in \mathcal{F}}A_{F}\right] \le \sum_{F \in \mathcal{F}}\Pr[A_{F}]=|\mathcal{F}|\cdot 2^{1-n}<2^{n-1}2^{1-n}=1 \ .\] Thus, a random coloring satisfies the required property with positive probability, implying that such a coloring exists.◼