Probabilistische Methode

aus Wikipedia, der freien Enzyklopädie

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

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

Literatur

Einzelnachweise

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