Probabilistische Methode

Die probabilistische Methode ist ein nicht-konstruktives Beweisverfahren, das durch Paul Erdős geprägt wurde und vor allem in der Kombinatorik Anwendung findet. Die Methode^[1] beruht auf folgendem einfachen Prinzip: Um zu zeigen, dass es ein Objekt mit einer bestimmten Eigenschaft gibt, reicht es, eine Wahrscheinlichkeitsverteilung zu finden, sodass die Wahrscheinlichkeit, dass ein zufällig gewähltes Objekt die gewünschte Eigenschaft besitzt, positiv ist.

Beispiel

Die Ramsey-Zahl $R(r,r)$ ist die kleinste Zahl $n$ , sodass in jedem vollständigen Graphen mit $n$ Ecken, dessen einzelne Kanten jeweils entweder rot oder blau gefärbt sind, eine monochromatische $r$ -Clique existiert, also $r$ Ecken, sodass alle Kanten zwischen ihnen die gleiche Farbe haben. Während Ramsey eine obere Schranke für $R(r,r)$ angab, fand Erdős mit der probabilistischen Methode eine untere Abschätzung.

Dazu betrachten wir einen vollständigen Graph mit $n$ Ecken und färben seine Kanten alle unabhängig voneinander mit der Wahrscheinlichkeit ${\tfrac {1}{2}}$ rot, sonst blau. Die Wahrscheinlichkeit, dass $r$ gegebene Ecken dieses Graphen untereinander alle mit roten Kanten verbunden sind, ist dann $2^{-{r \choose 2}}$ . Die Wahrscheinlichkeit, dass irgendeine Auswahl von $r$ Ecken eine monochromatische Clique bilden, ist dann höchstens ${n \choose r}\cdot 2\cdot 2^{-{r \choose 2}}$ . Ist also ${n \choose r}2^{1-{r \choose 2}}<1$ , so ist die Wahrscheinlichkeit, dass ein nach diesem Verfahren zufällig gefärbter Graph keine monochromatische $r$ -Clique besitzt, positiv. Diese Ungleichung ist insbesondere für $n\leq 2^{r/2}$ erfüllt, sodass $2^{r/2}\leq R(r,r)$ gilt.

Literatur

Noga Alon, Joel H. Spencer: The Probabilistic Method. Wiley, 2011. ISBN 978-1-118-21044-4.
Martin Aigner, Günter M. Ziegler: Das Buch der Beweise. Springer, Berlin 2004, ISBN 3-540-40185-7. Kapitel 40: Die probabilistische Methode.