Let be a collection of events in a probability space . There are two situations under which we can conclude that

- .
- The are independent of each other. In this case, the are independent and .

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 . By definition, is large enough such that any 2-coloring of the edges on a complete graph contains a monochromatic -clique .

In order to show that must be larger than some value , one chooses a *random* 2-coloring (with both colors equally likely and the coloring of each edge independent) on the edges of a . For each -subset , let be the event that is monochromatic under this 2-coloring, so that

If is a proper subset of the probability space, then there is a 2-coloring of with no monochromatic -clique. In particular, if

then we can conclude that there is a 2-coloring of without a monochromatic , so that . One concludes the following lower bound:

Theorem 1 (Erdös)If , then .

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