If every object in a collection of objects fails to have a certain property, then the probability that a random object chosen from the collection has that property is zero. Similarly, showing that the probability is less than 1 can be used to prove the existence of an object that does not satisfy the prescribed properties. Another way to use the probabilistic method is by calculating the expected value of some random variable. If it can be shown that the random variable can take on a value less than the expected value, this proves that the random variable can also take on some value greater than the expected value. Common tools used in the probabilistic method include Markov's inequality, the Chernoff bound, and the Lovász local lemma.
Two examples due to Erdős
Although others before him proved theorems via the probabilistic method, many of the most well known proofs using this method are due to Erdős. The first example below describes one such result from 1947 that gives a proof of a lower bound for the Ramsey number.
First example
Suppose we have a complete graph on vertices. We wish to show that it is possible to color the edges of the graph in two colors so that there is no complete subgraph on vertices which is monochromatic. To do so, we color the graph randomly. Color each edge independently with probability of being red and of being blue. We calculate the expected number of monochromatic subgraphs on vertices as follows: For any set of vertices from our graph, define the variable to be if every edge amongst the vertices is the same color, and otherwise. Note that the number of monochromatic -subgraphs is the sum of over all possible subsets. For any individual set, the expected value of is simply the probability that all of the edges in are the same color: . This holds true for any of the possible subsets we could have chosen, i.e. ranges from to. So we have that the sum of over all is The sum of expectations is the expectation of the sum, so the expectation of the sum is Consider what happens if this value is less than. Since the expected number of monochromatic -subgraphs is strictly less than, it must be that a specific random coloring satisfies that the number of monochromatic -subgraphs is strictly less than. The number of monochromatic -subgraphs in this random coloring is a non-negative integer, hence it must be . It follows that if , there must exist a coloring in which there are no monochromatic -subgraphs. By definition of the Ramsey number, this implies that must be bigger than. In particular, must grow at least exponentially with. A peculiarity of this argument is that it is entirely nonconstructive. Even though it proves that almost every coloring of the complete graph on vertices contains no monochromatic -subgraph, it gives no explicit example of such a coloring. The problem of finding such a coloring has been open for more than 50 years. ----
Second example
A 1959 paper of Erdős addressed the following problem in graph theory: given positive integers and, does there exist a graph containing only cycles of length at least, such that the chromatic number of is at least ? It can be shown that such a graph exists for any and, and the proof is reasonably simple. Let be very large and consider a random graph on vertices, where every edge in exists with probability. We show that with positive probability, a graph satisfies the following two properties: Proof. Let be the number cycles of length less than. Number of cycles of length in the complete graph on vertices is and each of them is present in with probability. Hence by Markov's inequality we have Proof. Let be the size of the largest independent set in. Clearly, we have when For sufficiently large, the probability that a graph from the distribution has both properties is positive, as the events for these properties cannot be disjoint. Here comes the trick: since has these two properties, we can remove at most vertices from to obtain a new graph on vertices that contains only cycles of length at least. We can see that this new graph has no independent set of size. can only be partitioned into at least independent sets, and, hence, has chromatic number at least. This result gives a hint as to why the computation of the chromatic number of a graph is so difficult: even when there are no local reasons for a graph to require many colors the chromatic number can still be arbitrarily large.
