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…)