Probabilistische Methode

Die probabilistische Methode i​st ein nicht-konstruktives Beweisverfahren, d​as durch Paul Erdős geprägt w​urde und v​or allem i​n der Kombinatorik Anwendung findet. Die Methode[1] beruht a​uf folgendem einfachen Prinzip: Um z​u zeigen, d​ass es e​in Objekt m​it einer bestimmten Eigenschaft gibt, reicht es, e​ine Wahrscheinlichkeitsverteilung z​u finden, sodass d​ie Wahrscheinlichkeit, d​ass ein zufällig gewähltes Objekt d​ie gewünschte Eigenschaft besitzt, positiv ist.

Beispiel

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

Dazu betrachten wir einen vollständigen Graph mit ${\displaystyle n}$ Ecken und färben seine Kanten alle unabhängig voneinander mit der Wahrscheinlichkeit ${\displaystyle {\tfrac {1}{2}}}$ rot, sonst blau. Die Wahrscheinlichkeit, dass ${\displaystyle r}$ gegebene Ecken dieses Graphen untereinander alle mit roten Kanten verbunden sind, ist dann ${\displaystyle 2^{-{r \choose 2}}}$. Die Wahrscheinlichkeit, dass irgendeine Auswahl von ${\displaystyle r}$ Ecken eine monochromatische Clique bilden, ist dann höchstens ${\displaystyle {n \choose r}\cdot 2\cdot 2^{-{r \choose 2}}}$. Ist also ${\displaystyle {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 ${\displaystyle r}$-Clique besitzt, positiv. Diese Ungleichung ist insbesondere für ${\displaystyle n\leq 2^{r/2}}$ erfüllt, sodass ${\displaystyle 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.

Einzelnachweise

1. Edmund Weitz: Paul Erdős und die probabilistische Methode auf YouTube, 12. März 2020, abgerufen am 22. März 2020.