Define the Ramsey number to be the minimum number of vertices required of the complete graph so that for any two-coloring (red, blue) of the edges of one of two things will happen:
- There is a red -clique; that is, a complete subgraph of vertices for which all edges are red.
- There is a blue -clique.
It is known that these numbers are always finite, but it is very difficult to compute them exactly.
Problem: Prove that the Ramsey number whenever satisfy
Solution: Color the edges of uniformly at random (that is, each edge has probability 1/2 of being colored red). For any complete subgraph , define by event the event that is monochromatic (its edges are either all red or all blue).
Now the probability that occurs (where is fixed ahead of time) is easy to compute:
Since there are possible subgraphs with vertices, The probability that for some the event occurs is at most
Whenever this quantity is strictly less than 1 (by assumption) then there is a positive probability that no event will occur. That is, there is a positive probability that a random coloring will have no monochromatic subgraph . So there must exist such a coloring, and the Ramsey number must be larger than .
Discussion: This proof (originally due to Erdős) is a classic example of the so-called probabilistic method. In particular, we create a probability space from the object we wish to study, and then we make claims about the probability of joint events.
While it seems quite simple in nature, the probabilistic method has been successfully applied to a wide variety of problems in mathematics. For instance, there is an elegant proof in complexity theory that which uses this same method. The probabilistic method has been applied to loads of problems in combinatorics, number theory, and graph theory, and it forms the foundation of the area of random graph theory (which is the setting in which one studies social networks). Perhaps unsurprisingly, there is also a proof of the fundamental theorem of algebra that uses the probabilistic method.