Probabilistic method

The probabilistic method is a non-constructive proof procedure that was shaped by Paul Erdős and is mainly used in combinatorics . The method is based on the following simple principle: To show that there is an object with a certain property, it is sufficient to find a probability distribution so that the probability that a randomly chosen object has the desired property is positive.

example

The Ramsey number is the smallest number , so that in each complete graph with a monochromatic corners, the individual edges are each colored either red or blue - Clique exist, so corners so that all edges have the same color between them. While Ramsey gave an upper bound for , Erdős found a lower estimate using the probabilistic method. ${\displaystyle R(r,r)}$ ${\displaystyle n}$ ${\displaystyle n}$ ${\displaystyle r}$ ${\displaystyle r}$ ${\displaystyle R(r,r)}$

To do this, we consider a complete graph with vertices and color its edges all independently of one another with the probability red, otherwise blue. The probability that given corners of this graph are all connected by red edges is then . The probability that any selection of corners will form a monochromatic clique is then at most . If, therefore , the probability that a graph that is randomly colored according to this method does not have a monochromatic clique is positive. This inequality is especially true for , so that holds. ${\displaystyle n}$ ${\displaystyle {\tfrac {1}{2}}}$ ${\displaystyle r}$ ${\displaystyle 2^{-{r \choose 2}}}$ ${\displaystyle r}$ ${\displaystyle {n \choose r}\cdot 2\cdot 2^{-{r \choose 2}}}$ ${\displaystyle {n \choose r}2^{1-{r \choose 2}}<1}$ ${\displaystyle r}$ ${\displaystyle n\leq 2^{r/2}}$ ${\displaystyle 2^{r/2}\leq R(r,r)}$

literature

• Noga Alon , Joel H. Spencer : The Probabilistic Method. Wiley, 2011. ISBN 978-1-118-21044-4 .
• Martin Aigner , Günter M. Ziegler : The book of evidence . Springer, Berlin 2004, ISBN 3-540-40185-7 . Chapter 40: The Probabilistic Method.

Individual evidence

1. ↑ Weitz / HAW Hamburg: Paul Erdős and the probabilistic method on YouTube , March 12, 2020, accessed on March 22, 2020.