Probabilistic method

The probabilistic method is a non- constructive proof method that has been coined by Paul Erdős and finds application mainly in combinatorics. The method is based on the following simple principle: In order to show that there is an object with a given property, it suffices to find a probability distribution, so that the probability that a randomly selected object has the desired characteristic, is positive.

Example

The Ramsey number is the smallest number such that every complete graph with vertices whose edges are colored either red or blue all, a monochromatic clique exists, so that all edges have the same color corners between them. While Ramsey stated an upper bound for, Erdős found with the probabilistic method, a lower estimate.

For this we consider a complete graph with vertices and color its edges all independently with probability red, otherwise blue. The probability of given edges of this graph are all connected to each other with red edges, then. The likelihood that any selection of vertices form a clique is monochromatic, then a maximum. Is so, then the probability that a randomly dyed according to this method does not monochromatic graph clique positive. This inequality is satisfied in particular for so applies.