Der Satz von Ramsey geht auf Frank Plumpton Ramsey und dessen Veröffentlichung aus dem Jahr 1930 zurück. Er zählt zu den klassischen Theoremen der Kombinatorik und stellt eine Verallgemeinerung des dirichletschen Schubfachprinzips dar. Der Satz behandelt die Frage, ob und unter welchen Bedingungen bei Kantenfärbungen von vollständigen Graphen und Hypergraphen mit zwei (oder mehr) Farben einfarbige Teilgraphen auftreten. Es ergibt sich, dass solche Teilgraphen für hinreichend große vollständige Graphen und Hypergraphen stets auftreten müssen. Das derartige Fragestellungen behandelnde Teilgebiet der Kombinatorik wird Ramseytheorie genannt.
Neben der reinen Existenzfrage wird in der Diskreten Mathematik auch ein damit zusammenhängendes Quantifizierungsproblem untersucht. Es handelt sich hier um die Frage, ab welcher Größe ein vollständiger Graph bzw. Hypergraph im genannten Sinne als „hinreichend groß“ zu betrachten ist, und weiter darum, wie die in diesem Sinne zu bestimmenden Ramsey-Zahlen zu berechnen oder wenigstens abzuschätzen sind. Diese Quantifizierungsfrage zu klären oder gar zu lösen, hat sich als außerordentlich schwierig herausgestellt.
Mit dem Satz von Ramsey lassen sich Existenzsätze der Diskreten Mathematik ableiten und insbesondere kombinatorische Probleme der Geometrie und Zahlentheorie lösen. Eine praktische Anwendung findet er auch beim Spiel Sim.
Aussage des Satzes (Version für vollständige Graphen) Wir betrachten endliche vollständige Graphen mit Knoten und Kantenfärbungen, bei denen jede Kante von mit einer von zwei Farben, etwa rot und blau, gefärbt ist.Die Wahl der Farben ist unwesentlich. Gibt es hierin Knoten, so dass alle zwischen diesen verlaufenden Kanten rot sind, so sagen wir, der Graph enthalte einen roten -Teilgraphen. Eine entsprechende Sprechweise gelte für blaue Teilgraphen.
Mit dieser Sprechweise lässt sich der Satz von Ramsey (in der Version für Graphen) angeben wie folgt:
Zu je zwei natürlichen Zahlen gibt es stets eine (von und abhängige) natürliche Zahl dergestalt, dass jeder vollständige Graph mit Knoten, dessen Kanten entweder rot oder blau gefärbt sind, mindestens einen roten -Teilgraphen oder einen blauen -Teilgraphen enthält.
Ramsey-Zahlen für vollständige Graphen Die kleinste natürliche Zahl, die als ein solches bei gegebenen gewählt werden kann, heißt die zu und gehörige Ramsey-Zahl und wird mit bezeichnet.
Charakteristisch für die Ramsey-Zahl ist die Eigenschaft, dass der größte vollständige Graph ist, welcher eine Rot-Blau-Kantenfärbung gestattet, zu der weder ein roter -Teilgraph noch ein blauer -Teilgraph in existiert.
Der Satz von Ramsey für vollständige Graphen lässt sich von Kantenfärbungen mit zwei auf solche mit beliebig vielen Farben verallgemeinern. Entsprechend gibt es zu beliebigen Kantenfärbungen mit Farben und Anzahlen die zugehörige Ramsey-Zahl .
Einfache Beispiele Allgemein gilt , wie man durch Vertauschen der Farben erkennt. : Jeder Teilgraph mit nur einer Ecke ist automatisch einfarbig. : Entweder sind alle Kanten rot oder es gibt eine blaue Kante.
Zur Berechnung von R(3,3) gerahmt|Eine 2-Färbung des K5 ohne monochromatisches K3 Das nebenstehende Bild zeigt, dass es möglich ist, den , also den vollständigen Graphen mit fünf Ecken, so mit zwei Farben rot und blau zu färben, dass weder ein rotes noch ein blaues Dreieck auftritt. Folglich gilt gewiss: bzw. .
Betrachtet man umgekehrt einen auf beliebige Weise rot-blau gefärbten und hierin eine beliebige Ecke , so tritt bei den fünf in endenden Kanten eine der beiden Farben, o. B. d. A. Rot, mindestens dreimal auf (Schubfachprinzip). Ist eine der Kanten zwischen den drei entsprechenden Endpunkten rot, so haben wir einen roten . Andernfalls sind alle Kanten zwischen diesen drei Endpunkten blau, und wir haben einen blauen . In jedem rot-blau-gefärbten findet man also einen roten oder einen blauen , d. h., es gilt: .
Insgesamt erhält man also .
Weitere Identitäten, Ungleichungen und Werte zu den Ramsey-Zahlen für vollständige Graphen Im Allgemeinen gelten folgende Beziehungen:Die oben gemachten Überlegungen zur Bestimmung von R(3,3) deuten bereits einige der wesentlichen Ideen an, die zu der genannten rekursiven Abschätzung der Ramsey-Zahlen und dann auch zu einem Beweis des Satzes führen. Diese Abschätzung ist jedoch für eine exakte Bestimmung der Ramsey-Zahlen bei weitem nicht ausreichend.Die Ungleichungen gehen zurück auf die klassische Arbeit von Paul Erdős und George Szekeres aus dem Jahre 1935, mit welchem die beiden Autoren als erste den Satz von Ramsey mit Fragestellungen der Graphentheorie und Geometrie verknüpften. (Vgl. 1) 2) Graham-Rothschild-Spencer: S. 24 ff. 3)
für für für für für
Aus der vorletzten Ungleichung erhält man so die folgende abgeleitete Ungleichung: für .
Für den Fall lässt sich diese noch verschärfen:Volkmann: S. 359. für .
Für den allgemeinen Fall , bei dem beliebige Kantenfärbungen mit zwei, drei oder mehr Farben zugelassen sind, gilt:Diese Ungleichung geht gemäß Lutz Volkmann auf eine Arbeit von E. J. Cockayne aus dem Jahr 1972 zurück. Vgl. Volkmann: S. 363.
für .
Eine grobe Eingrenzung dieser Ramsey-Zahlen geben die folgenden Ungleichungen, bei deren Herleitung wesentlich auf probabilistische Methoden zurückgegriffen wurde: für .
Die exakten Werte für diese Ramsey-Zahlen zu Kantenfärbungen mit zwei Farben sind – von den einfachen Beispielen abgesehen – bislang allein für kleinere Graphen bekannt. Es sind:Graham-Rothschild-Spencer: S. 75. , (Greenwood und Gleason (1955)) , (Greenwood und Gleason (1955)) , (Greenwood und Gleason (1955)) , (Graver und Yackel (1968)) , (Kalbfleisch (1966)) , (McKay und Min (1992)) , (Grinstead und Roberts (1982))
sowie , (Greenwood und Gleason (1955)) , (McKay und Radziszowski (1995))
Danach sind nur noch Schranken bekannt wie etwa
oder .Die untere Schranke von ergibt sich daraus, dass ein vollständiger zweigefärbter Graph mit Knoten gefunden wurde, welcher keinen vollständigen einfarbigen Untergraphen mit Knoten enthält. Vgl. Neunhäuserer: S. 31–32, 182–183. Weitere aktuelle Abschätzungen zu Kantenfärbungen mit zwei Farben sind im Artikel Ramsey's theorem des englischsprachigen Wikipedia nachzulesen.
Über die Ramsey-Zahlen zu Kantenfärbungen mit drei oder mehr Farben ist exaktes Zahlenmaterial nur in sehr geringer Menge vorhanden. Hier kennt man nicht viel mehr als
und dann noch eine obere und untere Schranke zu Kantenfärbungen mit vier Farben: .Bondy-Murty: S. 249.
Veranschaulichung Zur Veranschaulichung der Bedeutung einer Ramsey-Zahl ist es hilfreich, diese in Zusammenhang zu bringen mit der Beantwortung der folgenden Frage: Wie viele Gäste müssen zu einer Party zumindest erscheinen, wenn gewährleistet sein soll, dass von ihnen (oder mehr) einander nicht kennen oder (oder mehr) einander kennen.
Setzt man hierbei die Relation des Einander-Kennens, verstanden im Sinne eines zweiseitigen Miteinander-Bekanntseins, gleich mit einer irreflexiven, symmetrischen (aber nicht notwendig transitiven) Relation, so gelangt man zu einem Graphen mit roten und blauen Kanten, indem man in dem Falle, dass sich irgendwelche zwei Gäste nicht kennen, eine rote Kante, jedoch im gegenteiligen Fall, wenn sie sich kennen, eine blaue Kante zeichnet.
Damit lässt sich etwa die Ramsey-Zahl sehr leicht bestimmen. Hier ist also und .
Haben wir dann drei beliebige Gäste, so können wir den vollständigen Graphen zeichnen und folgende mögliche Kantenfärbungen erzielen: Alle Kanten werden rot gefärbt. Alle Kanten werden blau gefärbt. Zwei Kanten werden blau gefärbt und eine rot. Zwei Kanten werden rot gefärbt und eine blau.
Für die drei Gäste bedeutet dies: Keiner der Gäste kennt einen anderen. Alle drei Gäste kennen sich untereinander. Ein Gast kennt die beiden anderen Gäste, die einander jedoch nicht kennen. Zwei Gäste kennen sich, sind aber nicht mit dem dritten Gast bekannt.
Insgesamt heißt dies für die Bestimmung von : Für eine Party, bei der von den erschienenen Gästen entweder mindestens drei einander nicht kennen oder mindestens zwei einander kennen, genügt es, wenn drei oder mehr Gäste erscheinen.
Der allgemeine Satz von Ramsey (endliche Version für uniforme Hypergraphen) In der Version des Satzes von Ramsey für Graphen waren die zwei Farben Rot und Blau vorgegeben. Eine Rot-Blau-Kantenfärbung eines Graphen ist dabei ihrer mathematischen Bedeutung nach eine Abbildung von der Menge der Kanten des Graphen in die Menge . An die Stelle der -Menge lässt sich auch jede andere aus zwei Elementen bestehende Menge zur Markierung der Kanten wählen und insbesondere die -Menge . An die Stelle der Rot-Blau-Kantenfärbung tritt dann die Markierung der Kanten mit den Zahlen und . Auf diese Weise wird klar, dass eine Rot-Blau-Kantenfärbung einer Klasseneinteilung der Kanten in zwei Klassen gleichkommt.
Dieser Ansatz ist in mehrfacher Hinsicht verallgemeinerungsfähig. Dabei werden statt zweier Klassen endlich viele Klassen in beliebiger endlicher Anzahl betrachtet (also Stück), statt der Kanten (welche nichts weiter sind als -elementige Teilmengen der Knotenmenge von Graphen) beliebige -Teilmengen (mit ) von beliebigen endlichen Mengen und statt der zwei Zahlen beliebig vorgelegte natürliche Zahlen .
Dies führt zum allgemeinen Satz von Ramsey, der für den Fall der vollständigen (k-uniformen) Hypergraphen gilt:Jacobs-Jungnickel: S. 105.Halder-Heise: S. 141–142.Harzheim: S. 299–301.
Zu jeder natürlichen Zahl und je beliebig gegebenen natürliche Zahlen mit gibt es stets eine von abhängende natürliche Zahl mit folgender Eigenschaft: Ist eine natürliche Zahl mit und eine -elementige Menge und liegt irgendeine Zerlegung
des Mengensystems aller -Teilmengen von in Klassen vor, so gibt es stets mindestens einen Index und eine Teilmenge dergestalt, dass die Bedingungen:
und
erfüllt sind.
Höhere (klassische) Ramsey-Zahlen für uniforme Hypergraphen Die kleinste natürliche Zahl, die als Zahl im allgemeinen Satz von Ramsey bei gegebenem und gegebenen gewählt werden kann, heißt die zu und gehörige Ramsey-Zahl oder ähnlich. Eine solche Zahl nennt man auch eine höhere (klassische) Ramsey-Zahl ( oder auch classical hypergraph Ramsey number).Graham-Rothschild-Spencer: S. 90. Sie wird vielfach mit oder in ähnlicher Weise bezeichnet.Es gibt einige Bezeichnungsvarianten. Insbesondere ist die Wahl des bezeichnenden Buchstabens nicht einheitlich und zugleich kann auch die Position des im Verhältnis zu den wechseln. Statt des Großbuchstabens findet man des Öfteren auch den Kleinbuchstaben vor, dies vor allem in der Graphentheorie. Hier etwa tritt die Zahl auch als Index auf. In diesem Sinne gilt also (vgl. Handbook of Graph Theory):
.
Bei manchen Autoren – zumindest denen der älteren Literatur, etwa bei Halder-Heise – ist als Funktionsbezeichner sogar der griechische Kleinbuchstabe zu finden und es kommen noch weitere Bezeichnungsvarianten vor. Die hiesige Bezeichnung folgt im Wesentlichen der allgemeinen (nicht allein auf die Graphentheorie ausgerichteten) Bezeichnung bei Jacobs-Jungnickel bzw. der des Handbook of Discrete and Combinatorial Mathematics.
Identitäten, Ungleichungen und Werte zu den höheren Ramsey-Zahlen Mit den im obigen Satz genannten Bezeichnungen gelten folgende Identitäten:Jacobs-Jungnickel: S. 108. sowie Dies stellt die Verbindung zwischen allgemeinen Ramsey-Zahlen und Ramsey-Zahlen für Graphen her.
für
Weiter ist für den Fall noch die folgende Ungleichung gegeben:Halder-Heise: S. 138. für
Daneben gilt für den Fall und : für .
Für und gibt es noch folgende Verschärfung: für .Die letzten beiden Ungleichungen sind von oben übernommen.