Let ${A_i, 1 \leq i \leq n}$ be a collection of events in a probability space ${\Omega}$. There are two situations under which we can conclude that

$\displaystyle \bigcup A_i \neq \Omega.$

1. ${\sum \mathbb{P}(A_i) < 1}$.
2. The ${A_i}$ are independent of each other. In this case, the ${\overline{A_i} }$ are independent and ${\mathbb{P} ( \bigcap \overline{A_i}) = \prod \mathbb{P}(\overline{A_i}) >0}$.

There are a number of probabilistic arguments in combinatorics which can be made from the first situation alone. One of the original examples is the problem of bounding below the Ramsey numbers ${R(k, k)}$. By definition, ${R(k, k)}$ is large enough such that any 2-coloring of the edges on a complete graph ${K_{R(k, k)}}$ contains a monochromatic ${k}$-clique ${K_k}$.

In order to show that ${R(k, k)}$ must be larger than some value ${n}$, one chooses a random 2-coloring (with both colors equally likely and the coloring of each edge independent) on the edges of a ${K_n}$. For each ${k}$-subset ${A \subset [n]}$, let ${E_A}$ be the event that ${A}$ is monochromatic under this 2-coloring, so that

$\displaystyle \mathbb{P}(E_A) = 2^{1-\binom{k}{2}}.$

If ${\bigcup_{A: |A| = k} E_A }$ is a proper subset of the probability space, then there is a 2-coloring of ${K_n}$ with no monochromatic ${k}$-clique. In particular, if

$\displaystyle \sum_{A: |A| = k} \mathbb{P}(E_A) = \binom{n}{k} 2^{1-\binom{k}{2}} < 1,$

then we can conclude that there is a 2-coloring of ${K_n}$ without a monochromatic ${K_k}$, so that ${n < R(k, k)}$. One concludes the following lower bound:

Theorem 1 (Erdös) If ${\binom{n}{k} 2^{1-\binom{k}{2}} < 1}$, then ${R(k, k) > n}$.

In such arguments, the individual “bad” events (say, the ${E_A}$) had small probability, and to show that they did not together exhaust the entire probability space, one used the relatively crude bound ${\mathbb{P}( \bigcup A_i) \leq \sum \mathbb{P}(A_i)}$: that is, we used the first of the above two conditions at the beginning of this post. In practice, the events ${A_i}$ are not independent, but a large proportion of them are, and that might suggest the use of a “hybrid” of the two strategies. (more…)