Probabilistische Methode
# 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 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.

