Stellen Sie sich vor, Sie richten eine kleine Party mit sechs Gästen aus. Ihnen ist nicht ganz klar, wer sich untereinander kennt und wer nicht. Wie sich herausstellt, gibt es zwangsläufig mindestens drei Personen, die sich untereinander völlig fremd sind – oder die bereits miteinander befreundet sind (wir gehen nicht davon aus, dass Ihre Freunde sich nicht leiden können). Es wird also stets mindestens ein Dreier-Grüppchen geben, das sich kennt, oder eins, in dem alle einander komplett unbekannt sind.

Das mag zunächst vielleicht nicht allzu überraschend klingen, doch je länger man über das Problem nachdenkt, desto faszinierender wird es. Sechs Personen haben untereinander 15 Verbindungen (wie steht Person A zu Person B? Wie steht A zu C? Kennt B Person C?). Diese Verbindungen können einen von zwei Werten haben: Freunde oder Fremde. Das heißt, bei bloß sechs Gästen gibt es bereits 2¹⁵ (= 32 768) verschiedene Möglichkeiten, wie die Personen zueinander stehen können. Und nun behauptet die Mathematik, dass es in jeder möglichen Konstellation stets ein Trio gibt, das sich untereinander kennt oder vollkommen unbekannt ist. Jeden einzelnen Fall durchzugehen und nach einem Trio zu suchen, erscheint ziemlich aufwändig.

Tatsächlich fällt diese Aufgabe in den Bereich der so genannten Ramseytheorie, benannt nach dem britischen Mathematiker Frank Ramsey (1903–1930), der bereits im jungen Alter von 26 Jahren starb. In seiner kurzen Lebenszeit gelang es ihm allerdings, einen Zweig der Mathematik zu entwickeln, in dem es darum geht, eine gewisse Ordnung im Chaos zu identifizieren. Ziel ist es, in unübersichtlichen Anordnungen wiederkehrende Muster zu erkennen. So auch für den Fall der Party; dort lautet die Fragestellung aus mathematischer Sicht: Wie viele Gäste muss man mindestens einladen, damit stets ein Trio auftritt, das sich kennt oder einander vollkommen fremd ist?

Auch in der Mathematik hilft Netzwerken bei einer Party

Lösen lässt sich das Ganze mit Graphen, das sind Netzwerke aus Punkten (auch Knoten genannt) und Kanten. Jede Person symbolisiert dabei einen Knoten; die sechs Gäste kann man beispielsweise in einem Kreis anordnen. Nun verbindet man jeden Punkt miteinander. Dadurch entstehen die 15 Kanten, die bereits erwähnt wurden. Je nachdem, ob zwei Personen sich kennen oder nicht, färbt man diese rot (sie kennen sich) oder blau (sie sind sich fremd). Nun die Behauptung: Völlig egal, wie man die Kanten koloriert, es wird stets ein einfarbiges Dreieck enthalten. Sie können das ja mal versuchen, Sie werden sehen, ein solches Dreieck taucht immer auf.

Natürlich hat aber niemand Lust, die 32 768 Möglichkeiten durchzuspielen. Und außerdem beantwortet es auch nicht die Ramsey-Frage, ob sechs Personen die kleinste Anzahl an Gästen ist, bei der zwangsweise ein solches Dreieck entsteht. Daher arbeitet man sich mit der Anzahl geladener Personen langsam hoch. Findet man für eine gewisse Zahl eine Färbung im entsprechenden Graphen, bei der kein gleichfarbiges Dreieck auftaucht, dann hat man einen Gegenbeweis gefunden. Wenn man beispielsweise bloß drei Gäste einlädt, könnten sich zwei der Personen zuvor bereits begegnet sein. In diesem Fall gibt es also kein Trio, das sich kennt oder sich fremd ist.

Im Fall von vier Personen findet man auch schnell Fälle, in denen sich einige kennen und andere nicht, ohne dass eine Dreier-Gruppe einander unbekannt oder miteinander befreundet ist.

Und selbst bei fünf Gästen gibt es zumindest eine Konfiguration ohne gleichfarbiges Dreieck:

Kann man ein gleichgesinntes Trio bei sechs Personen vermeiden?

Doch wie ist das mit sechs Personen? Man muss nun versuchen, die Kanten eines Graphen einzufärben, ohne dass ein unifarbenes Dreieck entsteht. Um das zu bewerkstelligen, kann man sich zunächst eine einzelne Person A herauspicken und untersuchen, wie ihre Beziehung zu den übrigen Gästen aussehen kann. Es gibt insgesamt sechs verschiedene Möglichkeiten, mit wie vielen der Geladenen sie befreundet sein kann und wie viele ihr fremd sein können:

Die Person A ist also immer mit mindestens drei Personen befreundet – oder ihr sind mindestens drei Personen unbekannt. Im Graph macht sich das dadurch bemerkbar, dass von der Person stets mindestens drei gleichfarbige Kanten ausgehen. Für ein konkretes Beispiel kann man annehmen, ein bestimmter Punkt A habe drei rote Kanten (sprich: Person A kennt drei andere Gäste). Nun kann man versuchen, die restlichen Verbindungen so zu färben, dass auf jeden Fall ein rotes Dreieck umgangen wird. Denn wir suchen hier nach einer Konstellation unter den 32 768 möglichen Färbungen, bei denen kein gleichfarbiges Dreieck entsteht.

Daher muss man sicherstellen, dass jeweils zwei Personen, die A kennt, sich untereinander nicht kennen (also blaue Verbindungen haben). Wenn man all diese Kanten blau markiert, entsteht aber ein blaues Dreieck! Das heißt, es gibt keine Möglichkeit, ein einfarbiges Dreieck in einem Graphen mit sechs Punkten zu umgehen, wenn alle Knoten miteinander verbunden sein müssen. Und damit findet man ein solches Dreieck auch in jedem größeren Graphen, bei dem alle Punkte miteinander verbunden sind. Das heißt: Sobald Sie mehr als fünf Gäste einladen, gibt es auf jeden Fall immer ein Dreiergespann, das sich untereinander kennt oder völlig fremd ist.

Ramsey-Zahlen: Der allgemeine Fall

Natürlich geben sich Mathematiker mit diesem Einzelergebnis nicht zufrieden. Stattdessen versuchen sie, das Problem zu verallgemeinern: Wie viele Knoten R braucht man mindestens, um stets eine rote m- oder blaue n-Clique zu finden? Eine n-Clique bezeichnet eine Gruppe von n Punkten, die alle miteinander verbunden sind. Die sich daraus ergebende Zahl R(m,n) heißt Ramsey-Zahl. Erstaunlicherweise sind nur sehr wenige Ramsey-Zahlen bekannt. So haben wir bewiesen, dass R(3,3) = 6 ist. Es konnte auch gezeigt werden, dass R(4,4) = 18. Das heißt, wenn Sie eine Party mit 18 Gästen schmeißen, findet man immer eine Vierergruppe, die sich alle untereinander kennen oder fremd sind.

Seit Jahrzehnten ist hingegen unklar, wie groß R(5,5) ist. Was ist die kleinste Anzahl an Gästen, die man einladen muss, damit immer ein Fünfergespann von völlig Fremden oder Bekannten entsteht? Immerhin konnten Fachleute das Ergebnis eingrenzen; man weiß inzwischen, dass 43 ≤ R(5,5) ≤ 49. Nun könnte man einfach einen Computer einsetzen, der alle möglichen Färbungen für Graphen mit 43 Knoten durchgeht und prüft, ob es einen gibt, der keine gleichfarbige Fünfergruppe enthält. Aber tatsächlich übersteigt diese Aufgabe jede verfügbare Rechenleistung!

Ein Graph mit 43 Knoten, die alle miteinander verbunden sind, besitzt 903 Kanten. Diese können entweder blau (unbekannt) oder rot (Freunde) sein – das ergibt 2⁹⁰³ Möglichkeiten, was gerundet etwa 10²⁷² entspricht. Also eine 1 mit 272 Nullen. Das ist unvorstellbar groß. Um zu verstehen, wie groß, kann man folgende Überlegung anstellen: Aktuell geht man davon aus, dass unser Universum etwa 10⁸² Atome umfasst. Angenommen, jedes davon sei eine Rechenmaschine, die pro Sekunde so viele Berechnungen durchführen kann, wie der derzeit leistungsfähigste Supercomputer: eine Trillion (10¹⁸) Rechenschritte pro Sekunde. Nehmen wir vereinfacht an, jedes Atom könnte in einer Sekunde eine Trillion Graphen nach einer Fünfergruppe durchsuchen – und die Teilchen hätten direkt nach dem Urknall (13,8 Milliarden Jahre in der Vergangenheit) damit begonnen. Dann hätten sie bislang: 13,8 · 10⁹ · 365,25 · 24 · 3600 ≈ 4,35 · 10¹⁷ Sekunden Zeit dafür gehabt. Das heißt, alle Atome im Universum hätten bis heute etwa 4,35 · 10¹¹⁷ Graphen geprüft. Das ist allerdings nur ein winziger Bruchteil derer, die noch übrig sind.

Daher suchen Mathematikerinnen und Mathematiker nach einer clevereren Lösung für das Problem. Bislang haben sie jedoch keine gefunden.

Was ist euer Lieblingsmathetheorem? Schreibt es gerne in die Kommentare – und vielleicht ist es schon bald das Thema dieser Kolumne!