Satz von Ramsey

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Dieser Artikel behandelt den Satz von Ramsey in der Kombinatorik. Über den entsprechenden ramseyschen Satz in der Mengenlehre gibt es einen eigenen Artikel; siehe hier. Eine Einführung in das zugehörige mathematische Gebiet gibt der Artikel Ramseytheorie.

Der Satz von Ramsey geht auf Frank Plumpton Ramsey und dessen Veröffentlichundg 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.

Neben der reinen Existenzfrage wird in der Diskreten Mathematik auch ein damit zusammenhängendes Quantifizierunsproblem 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. Dieses 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)[Bearbeiten]

Wir betrachten endliche vollständige Graphen K_n mit n Knoten (n \in \N) und Kantenfärbungen, bei denen jede Kante von K_n mit einer von zwei Farben, etwa rot und blau, gefärbt ist.[1] Gibt es hierin r Knoten, so dass alle zwischen diesen verlaufenden Kanten rot sind, so sagen wir, der Graph enthalte einen roten r-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ürliche Zahlen r,b gibt es stets eine (von r und b abhängige) natürliche Zahl R dergestalt, dass jeder vollständig Graph K_n mit n \geq R Knoten, dessen Kanten entweder rot oder blau gefärbt sind, mindestens einen roten r-Teilgraphen oder einen blauen b-Teilgraphen enthält.

Ramsey-Zahlen für vollständige Graphen[Bearbeiten]

Die kleinste natürliche Zahl, die als ein solches R bei gegebenen r,b gewählt werden kann, heißt die zu r und b gehörige Ramsey-Zahl und wird mit R(r,b) bezeichnet.

Charakteristisch für die Ramsey-Zahl R(r,b) ist die Eigenschaft, dass K_{R(r,b)-1} der größte vollständige Graph ist, welcher eine Rot-Blau-Kantenfärbung gestattet, zu der weder ein roter r-Teilgraph noch einen blauer b-Teilgraph in K_{R(r,b)-1} existiert.

Der Satz von Ramsey für vollständige Graphen lässt sich auf Kantenfärbungen mit mehr als zwei auf solche mit beliebig vielen Farben verallgemeinern. Entsprechend gibt es zu beliebigen Kantenfärbungen mit t Farben   (t \in \N)   und   Anzahlen q_1,\ldots, q_t die zugehörige Ramsey-Zahl R(q_1,\ldots, q_t).

Einfache Beispiele[Bearbeiten]

  • Allgemein gilt R(r,b)=R(b,r), wie man durch Vertauschen der Farben erkennt.
  • R(r, 1) = 1: Jeder Teilgraph mit nur einer Ecke ist automatisch einfarbig.
  • R(r, 2) = r: Entweder sind alle Kanten rot oder es gibt eine blaue Kante.

Zur Berechnung von R(3,3)[Bearbeiten]

Eine 2-Färbung des K5 ohne monochromatisches K3

Das nebenstehende Bild zeigt, dass es möglich ist, den K_5, 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: R(3,3)>5 bzw. R(3,3)\geq 6.

Betrachtet man umgekehrt einen auf beliebige Weise rot-blau gefärbten K_6 und hierin eine beliebige Ecke v, so tritt bei den fünf in v endenden Kanten eine der beiden Farben, oBdA. rot, mindestens dreimal auf (Schubfachprinzip). Ist eine der Kanten zwischen den drei entsprechenden Endpunkten rot, so haben wir ein rotes K_3. Andernfalls sind alle Kanten zwischen diesen drei Endpunkten blau, und wir haben ein blaues K_3. In jedem rot-blau-gefärbten K_6 findet man also ein rotes K_3 oder ein blaues K_3, d.h., es gilt: R(3,3)\leq 6.

Insgesamt erhält man also R(3,3)=6.

Weitere Identitäten, Ungleichungen und Werte zu den Ramsey-Zahlen für vollständige Graphen[Bearbeiten]

Im Allgemeinen gelten folgende Beziehungen:[2][3][4]

  • R(r,b) =  R(b,r)
  • R(r,1) =  R(1,r) = 1   für   r \geq 1
  • R(r,2) =  R(2,r) = r   für   r \geq 1
  • R(r_1,b_1) \leq  R(r_2,b_2)   für   r_1 \leq r_2, b_1 \leq b_2,
  • R(r,b)\leq R(r-1,b)+R(r,b-1)  für   r,b \geq 2
  • R(r,b)\leq R(r-1,b)+R(r,b-1) - 1   für   r,b \geq 3 \, , \, R(r-1,b)  \equiv R(r,b-1) \equiv 0  \pmod 2

Aus der vorletzten Ungleichung erhält man so die folgende abgeleitete Ungleichung:

  • R(r,b) \leq \binom{r+b-2}{r-1}   für   r,b \geq 1  .

Für den Fall r=3 lässt sich diese noch verschärfen:[5]

  • R(3,b) \leq \frac{1}{2} (b^2 + 3)   für   b \geq 3  .

Für den allgemeinen Fall t = 2, 3, \ldots   , bei dem beliebige Kantenfärbungen mit zwei, drei oder mehr Farben zugelassen sind, gilt:[6]

  • R(q_1,q_2, \ldots, q_t) \leq \bigl( R(q_1 - 1,q_2, \ldots, q_t) +  R(q_1,q_2 - 1,\ldots, q_t)  + \cdots +  R(q_1,q_2,\ldots, q_t - 1) \bigr) - t + 2   für   q_1,\ldots, q_t \geq 2  .


Eine grobe Eingrenzung dieser Ramsey-Zahlen geben die folgenden Ungleichungen, bei deren Herleitung wesentlich auf probabilistische Methoden zurückgegriffen wurde:[7]

  • 2^{r/2} < R(r, r) < 4^{r-1}   für   r \geq 3  .

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:[8][9][10]

  • R(3,3) = 6
  • R(3,4) = 9
  • R(3,5) = 14
  • R(3,6) = 18
  • R(3,7) = 23
  • R(3,8) = 28
  • R(3,9) = 36

sowie

  • R(4,4) = 18
  • R(4,5) = 25  .

Danach sind nur noch Abschätzungen geläufig wie etwa

  •  35 \leq R(4,6) \leq 41

oder

Ü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:

Veranschaulichung[Bearbeiten]

Zur Veranschaulichung der Bedeutung einer Ramsey-Zahl R(r,b) 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 entweder r (oder mehr) einander nicht kennen oder b (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 R(3,2) = 3 sehr leicht bestimmen. Hier ist also r = 3 und b = 2.

Haben wir dann drei beliebige Gäste, so können wir den vollständigen Graphen K_3 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 R(3,2) = 3 :

Für eine Party , bei der von den erschienen 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)[Bearbeiten]

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 \{ {rot}, {blau} \} \,. An die Stelle der 2-Menge \{ {rot}, {blau} \} \, lässt sich auch jede andere aus zwei Elementen bestehende Menge zur Markierung der Kanten wählen und insbesondere die 2-Menge \{1,2\} \subset \N  \,. An die Stelle der Rot-Blau-Kantenfärbung tritt dann die Markierung der Kanten mit den Zahlen 1 und 2 . Auf diese Weise wird klar, dass eine Rot-Blau-Kantenfärbung einer Klasseneinteilung der Kanten in zwei Klassen gleichkommt.

Diesen Ansatz ist in mehrfacher Hinsicht verallgemeinerungsfähig. Dabei werden statt zweier Klassen endlich viele Klassen in beliebiger endlicher Anzahl betrachtet (also t = 1, 2, 3, \ldots Stück) , statt der Kanten (welche nichts weiter sind als 2-elementige Teilmengen der Knotenmenge von Graphen) beliebige k-Teilmengen (mit k = 1, 2, 3, \ldots) von beliebigen endlichen Mengen X \, und statt der zwei Zahlen r,b \, beliebig vorgelegte natürliche Zahlen q_1, q_2, \ldots , q_t \, .

Dies führt zum allgemeinen Satz von Ramsey, der für den Fall der vollständigen (k-uniformen) Hypergraphen gilt:[14][15][16][17]

Zu jeder natürlichen Zahl   t und je     t +1   beliebig gegebenen natürliche Zahlen  k, q_1, q_2, \ldots , q_t mit k \leq \min(q_1, q_2, \ldots , q_t) gibt es stets eine von k, q_1, q_2, \ldots , q_t abhängende natürliche Zahl R mit folgender Eigenschaft:
Ist n \, eine natürliche Zahl mit n \geq R und X eine n-elementige Menge und liegt irgendeine Zerlegung
 {X \choose k} = {\mathcal K}_1 \dot{\cup} {\mathcal K}_2 \dot{\cup} \, \dots \dot{\cup} {\mathcal K}_t \,  
des Mengensystems aller k-Teilmengen von   X   in     t   Klassen vor,
so gibt es stets mindestens einen Index s \in \{1, 2, \ldots , t \} \, und eine Teilmenge   T \subseteq X \,   dergestalt, dass die Bedingungen :
|T| = q_s \,
und
{T \choose k} \subseteq {\mathcal K}_s  \,
erfüllt sind.

Höhere (klassische) Ramsey-Zahlen für uniforme Hypergraphen[Bearbeiten]

Die kleinste natürliche Zahl, die als Zahl   R   im allgemeinen Satz von Ramsey bei gegebenem    k   und gegebenen    q_1, q_2, \ldots , q_t   gewählt werden kann, heißt die zu    k\,   und    q_1, q_2, \ldots , q_t   gehörige Ramsey-Zahl oder ähnlich. Eine solche Zahl nennt man auch eine höhere (klassische) Ramsey-Zahl (englisch k-hypergraph Ramsey number oder auch classical hypergraph Ramsey number) .[18] Sie wird vielfach mit   R(q_1, q_2, \ldots , q_t ; k)   oder in ähnlicher Weise bezeichnet.[19]

Identitäten, Ungleichungen und Werte zu den höheren Ramsey-Zahlen[Bearbeiten]

Mit den im obigen Satz genannten Bezeichnungen gelten folgende Identitäten:[20][21][22][23]

  • R(q_1, q_2 ; 2) = R(q_1, q_2)   sowie   R(q_1,\ldots, q_t)= R(q_1,\ldots, q_t; 2)[24]
  • R(2, 2, \ldots , 2 ; 2)  = 2
  • R(q_1, q_2, \ldots , q_t; 1)  = q_1 + q_2 + \cdots + q_t - t + 1
  • R(q_1, k, \ldots , k; k)  = q_1   für k,q_1 \in \N \, , \,  q_1 \geq k

Weiter ist für den Fall   t=2   noch die folgende Ungleichung gegeben:[25]

  • R( q_1, q_2; k) \leq 1 + R \bigl( {R(q_1-1, q_2; k), R(q_1, q_2-1; k); k -1} \bigr)   für q_1, q_2 , k \in \N \, , \, 1 < k < \min(q_1, q_2)

Daneben gilt für den Fall   t = 2, 3, \ldots   und   k = 2   :

  • R(q_1,q_2, \ldots, q_t;2) \leq \bigl( R(q_1 - 1,q_2, \ldots, q_t;2) +  R(q_1,q_2 - 1,\ldots, q_t;2)  + \cdots +  R(q_1,q_2,\ldots, q_t - 1;2) \bigr) - t + 2   für   q_1,\ldots, q_t \geq 2  .

Für t=2   und   q_1=3 gibt es noch folgende Verschärfung:

  • R(3,q_2;2) \leq \frac{1}{2} ({q_2}^2 + 3)   für   q_2 \geq 3  .[26]

Exakte Werte für die höheren Ramsey-Zahlen sind, soweit man von den aufgeführten einfachen Beispielen und den obigen Werten der Ramsey-Zahlen für kleine Graphen absieht, weitgehend unbekannt. Eine Ausnahme bildet die Ramsey-Zahl für    t=2 , k=3  , q_1 = q_2 = 4   . Hier gilt:

  •  R(4, 4; 3) = 13   .

Die unendliche Version des Satzes von Ramsey[Bearbeiten]

Die unendliche Version des Satzes von Ramsey ist diejenige, welche im Wesentlichem dem ursprünglich von Frank Plumpton Ramsey in 1930 vorgelegten Theorem entspricht. Sie lautet:[27]

Zu beliebig gegebenen natürlichen Zahlen  k,t \, , zu einer beliebig gegebenen unendlichen Menge X und irgendeiner Zerlegung
 {X \choose k} = {\mathcal K}_1\dot{\cup}{\mathcal K}_2\dot{\cup} \, \dots \dot{\cup} {\mathcal K}_t \,  
des Mengensystems aller k-Teilmengen von X \,
gibt es stets mindestens einen Index s \in \{1, 2, \ldots , t \} \, und eine unendliche Teilmenge T \subseteq X \, mit
{T \choose k} \subseteq {\mathcal K}_s  \,   .

Es lässt sich zeigen, dass die unendliche Version des Satzes von Ramsey die endliche Version nach sich zieht.[28]

Folgerungen[Bearbeiten]

Dieser Satz von Ramsey hat bemerkenswerte Konsequenzen, etwa in der Geometrie und in der Zahlentheorie. Unter anderem ergibt sich aus ihm das berühmte Happy Ending theorem von Erdős und Szekeres aus dem Jahre 1935 und eine erweiterte Version des Satzes von Schur.[29][30][31]

Happy Ending theorem[Bearbeiten]

Zu jeder beliebig vorgegebenen natürlichen Zahl   m \geq 3   existiert stets eine allein von    m \,   abhängige natürliche Zahl   \kappa   mit der Eigenschaft, dass je    \kappa   oder mehr Punkte der euklidischen Ebene, welche sich in allgemeiner Lage befinden, stets ein konvexes Vieleck mit    m   Eckpunkten enthalten.

Nach Halder und Heise lässt sich dieser Satz sogar noch etwas schärfer fassen:[32]

Zu jeder beliebig vorgegebenen natürlichen Zahl   m \geq 3   existiert stets eine natürliche Zahl   \kappa   mit der Eigenschaft, dass je    \kappa   oder mehr Punkte der euklidischen Ebene zumindest    m   kollineare Punkte oder ein konvexes Vieleck mit    m   Eckpunkten enthalten.

Bezeichnet man die kleinste natürliche Zahl, welche zu vorgegebener natürlicher Zahl   m \geq 3   dem Happy Ending theorem (in der ersten etwas schwächeren Version) genügt, mit    \kappa (m)   , so hat man für   m = 3,4,5,6   folgenden exakten Wert:[33]

  • \kappa (m)= 2^{m-2} +1   .

Es sind also

  • \kappa (3) = 3
  • \kappa (4) = 5
  • \kappa (5) = 9
  • \kappa (6) = 17   .

Darüber hinaus sind man keine weiteren exakten Werte bekannt, sondern nur noch ein allgemeines Werteintervall :[34]

  • 2^{m-2} +1  \leq \kappa (m)  \leq \binom{2m-5}{m-2} + 2   für alle   m \geq 3 .

Satz von Schur (erweiterte Version)[Bearbeiten]

Zu je zwei beliebig vorgegebenen natürlichen Zahlen   m,t   mit   m \geq 2   existiert stets eine kleinste natürliche Zahl   S = S(m,t)   mit folgender Eigenschaft:
Ist   n   eine natürliche Zahl mit   n \geq S   und liegt für das Anfangsstück   A = \{ 1 ,2  \, \ldots , n \} \subset \N   irgendeine Zerlegung
 A = A_1 \dot{\cup} A2 \dot{\cup} \, \dots \dot{\cup} A_t \,
in     t   Klassen vor,
so enthält mindestens eine der Mengen A_s \, ( s \in \{1, 2, \ldots , t \} )   ein   m-Tupel   (a_1 , a_2  \, \dots , a_m)   von (nicht notwendig verschiedenen) Zahlen , welche die Gleichung:
a_1 + a_2  + \, \dots + a_{m-1} = a_m
erfüllen.

Zusatz[Bearbeiten]

Aus dem von Halder und Heise gelieferten Beweis geht hervor, dass die mit dem schurschen Satz definierte Schur-Zahl   S(m,t)   stets unterhalb der Ramsey-Zahl   R(q_1, q_2, \ldots , q_t; 2)   (q_1 = q_2 = \, \ldots = q_t= m)   liegt.[35]

Verallgemeinerung des Satzes von Ramsey für endliche einfache Graphen[Bearbeiten]

Der ramseysche Satzes behandelt im Fall der Graphen (s. Teil 1) die Frage, ob und wie sich hinreichend große vollständige Graphen K_n finden lassen, so dass sich in solche   K_n   bei jeder Kantenfärbung mindestens einer von   t   vorgegebenen vollständigen Graphen K_{q_i} als einfarbiger Teilgraph einbetten lässt.

Dieses Konzept ist dahingehend verallgemeinert worden, dass man nun von den   K_{q_i}   auf beliebige einfache Graphen   {\mathcal G}_i   endlicher Ordnung übergeht. Auf diesem Wege erhält man die folgende Verallgemeinerung des Satzes von Ramsey für Graphen:[36][37][38]

Zu jeder natürlichen Zahl    t \geq 2   und jeder beliebig vorgegebenen t-Familie   ({\mathcal G}_1, {\mathcal G}_2, \ldots , {\mathcal G}_t)   von endlichen einfachen Graphen existiert stets eine natürliche Zahl   r   mit folgender Eigenschaft:
Ist   n \in \N   und   n \geq r   und liegt irgendeine Kantenfärbung von   K_n   mit    t   Farben vor, so existiert in K_n ein einfarbiger Teilgraph, welcher das isomorphe Bild zumindest eines der Graphen   {\mathcal G}_1, {\mathcal G}_2, \ldots , {\mathcal G}_t enthält.

Verallgemeinerte Ramsey-Zahlen für endliche einfache Graphen[Bearbeiten]

Die kleinste natürliche Zahl, die als Zahl   r   in der Verallgemeinerung des Satzes von Ramsey für Graphen bei gegebenen {\mathcal G}_1, {\mathcal G}_2, \ldots , {\mathcal G}_t gewählt werden kann, heißt die zu {\mathcal G}_1, {\mathcal G}_2, \ldots , {\mathcal G}_t   gehörige (verallgemeinerte) Ramsey-Zahl (oder ähnlich) und wird mit   r({\mathcal G}_1, {\mathcal G}_2, \ldots , {\mathcal G}_t)   bezeichnet.[39]

Für sie gelten folgende allgemeine Beziehungen:[40][41]

Ebenso wie bei obigen Ramsey-Zahlen sind zu den verallgemeinerten Ramsey-Zahlen für einfache Graphen in nur einigen Fällen konkrete Ergebnisse bekannt. Dazu gehören die folgenden:[44]

Asymptotische Abschätzungen[Bearbeiten]

Obwohl die klassischen Ramsey-Zahlen wie auch die verallgemeinerten Ramsey-Zahlen für Graphen nur in wenigen Fällen exakt bestimmt sind, lassen sie sich gewisse asymptotische Abschätzungen angeben. Das folgende Resultat, welches insbesondere auf Arbeiten von Miklós Ajtai, János Komlós und Endre Szemerédi (1980) sowie Jeong Han Kim (1995) zurückgeht, wird häufig genannt:[48][49]

{ C_1 \cdot \frac {n^2 }{\ln (n)} } \leq R(3,n; 2) \leq { C_2 \cdot \frac {n^2 }{\ln (n)} }      ( n \in \N \,  ,  \, n \geq 2)   . [50]

Vermutungen[Bearbeiten]

Es gibt zu den klassischen Ramsey-Zahlen ebenso wie zu den verallgemeinerten Ramsey-Zahlen für Graphen eine Reihe von Vermutungen. Diese sind nicht selten mit Namen und Person von Paul Erdös verbunden. Dazu gehören die folgenden:

Vermutung von Erdős[Bearbeiten]

Paul Erdös äußerte im Jahre 1973 die folgende Vermutung, welche die Ramsey-Zahlen, verallgemeinerten Ramsey-Zahlen für Graphen und deren chromatische Zahlen in Verbindung bringt :[51]

  • Hat ein endlicher einfacher Graph   {\mathcal G}   die chromatische Zahl   \chi ({\mathcal G}) = n     (n \in \N)   , so gilt  r({\mathcal G},{\mathcal G}) \geq R(n,n)   . [52]

Vermutung von Bondy und Erdős[Bearbeiten]

John Adrian Bondy und Paul Erdös stellten im Jahre 1973 die folgende Vermutung von Bondy und Erdős zu den Ramsey-Zahlen für Kreisgraphen auf:[53]

  • Es gilt für Kreisgraphen   C_n   , sofern   n \geq 5   und ungerade ist, stets   r(C_n,C_n,C_n) = 4n - 3   .

Bislang gesichert ist, dass für derartige ungeraden Zahlen   n   immer die Ungleichung

Bestand hat.

Baum-Vermutung[Bearbeiten]

Stefan A. Burr und Paul Erdös äußerten in 1976 die sogenannte Baum-Vermutung (englisch Tree Conjecture):[55]

  • Für Baumgraphen   B_p   und   B_q   mit   p,q \geq 2   ist stets   r(B_p,B_q) \leq  p + q - 2   .

Erdős-Sós-Vermutung[Bearbeiten]

Verknüpft und dabei weiterreichend als die Baum-Vermutung - da sie diese impliziert - ist die Erdős-Sós-Vermutung, welche von Paul Erdős und Vera Turán Sós im Jahre 1963 aufgestellt wurde:[56][57]

  • In jedem endlichen einfachen Graphen   \mathcal G   mit   n   Knoten und   1+ \frac {n (p-2)} {2}   (oder mehr) Kanten   (n,p \in \N \,\, , p \geq 2 )   ist von jedem beliebigen Baumgraphen   B_p   mit   p   Knoten immer ein isomorphes Bild als Teilgraph enthalten.

Vermutung von McKay und Radziszowski[Bearbeiten]

Die Vermutung von McKay und Radziszowski aus dem Jahre 1997 besagt:[58]

  • r(5,5) = 43

Literatur[Bearbeiten]

Originalarbeiten[Bearbeiten]

Monographien[Bearbeiten]

Handbücher[Bearbeiten]

Siehe auch[Bearbeiten]

Weblinks[Bearbeiten]

Einzelnachweise und Fußnoten[Bearbeiten]

  1. Die Wahl der Farben ist unwesentlich.
  2.  Handbook of Discrete and Combinatorial Mathematics. S. 150 ff.
  3. 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.
  4. 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)  Erdős-Szekeres: In: Proc. London Math. Soc.. S. 463 ff. 2)  Graham-Rothschild-Spencer: S. 24 ff. 3)  Handbook of Graph Theory. S. 838 ff.
  5.  Volkmann: S. 359.
  6. Diese Ungleichung geht gemäß Lutz Volkmann auf eine Arbeit von E. J. Cockayne aus dem Jahr 1972 zurück. Vgl.  Volkmann: S. 363.
  7.  Erdős: In: Bull. Amer. Math. Soc.. S. 292 ff.
  8.  Graham-Rothschild-Spencer: S. 75.
  9.  Handbook of Discrete and Combinatorial Mathematics. S. 151, 592 ff. )
  10.  Handbook of Graph Theory. S. 840. )
  11. Die untere Schranke von R(5,5) ergibt sich daraus, dass ein vollständiger zweigefärbter Graph mit 42 Knoten gefunden wurde, welcher keinen vollständigen einfarbigen Untergraphen mit 5 Knoten enthält. Vgl.  Neunhäuserer: S. 31-32,182-183. Weitere aktuelle Abschätzungen (Stand November 2014) zu Kantenfärbungen mit zwei Farben sind im Artikel Ramsey's theorem des englischsprachigen Wikipedia nachzulesen.
  12.  Greenwood-Gleason: In: Canad. J. Math. S. 1 ff.
  13.  Bondy-Murty: S. 249.
  14.  Jacobs-Jungnickel: S. 105.
  15.  Halder-Heise: S. 141-142.
  16.  Harzheim: S. 299-301.
  17.  Handbook of Discrete and Combinatorial Mathematics. S. 150.
  18.  Graham-Rothschild-Spencer: S. 90.
  19. Es gibt einige Bezeichnungsvarianten. Insbesondere ist die Wahl des bezeichnenden Buchstabens nicht einheitlich und zugleich kann auch die Position des    k   im Verhältnis zu den   q_i   wechseln. Statt des Großbuchstabens    R   findet man des Öfteren auch den Kleinbuchstaben    r   vor, dies vor allem in der Graphentheorie. Hier etwa tritt die Zahl    k   auch als Index auf. In diesem Sinne gilt also (vgl. Handbook of Graph Theory):
    •  r(q_1, q_2) = {r_2}(q_1, q_2) = R(q_1, q_2) = R(q_1, q_2 ; 2)
    •  r(q_1, q_2, \ldots , q_t) = {r_2}(q_1, q_2, \ldots , q_t) = R(q_1, q_2, \ldots , q_t) = R(q_1, q_2, \ldots , q_t ; 2)
    • {r_k}(q_1, q_2, \ldots , q_t)   = R(q_1, q_2, \ldots , q_t ; k)   .
    Bei manchen Autoren - zumindest denen der älteren Literatur, etwa bei Halder-Heise - ist als Funktionsbezeichner sogar der griechische Kleinbuchstabe    \rho   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.
  20.  Handbook of Graph Theory. S. 853.
  21.  Handbook of Discrete and Combinatorial Mathematics. S. 150.
  22.  Jacobs-Jungnickel: S. 108.
  23.  McKay-Radziszowski: In: Proceedings of the Second Annual ACM-SIAM Symposium on Discrete Algorithms. 1991, S. 304 ff.
  24. Dies stellt die Verbindung zwischen allgemeinen Ramsey-Zahlen und Ramsey-Zahlen für Graphen her.
  25.  Halder-Heise: S. 138.
  26. Die letzten beiden Ungleichungen sind von oben übernommen.
  27.  Jacobs-Jungnickel: S. 109-110.
  28.  Jacobs-Jungnickel: S. 110.
  29.  Jacobs-Jungnickel: S. 108-109.
  30. Siehe auch im englischsprachigen WIKIPEDIA unter: Happy Ending problem!
  31.  Halder-Heise: S. 142-143.
  32.  Halder-Heise: S. 140-141.
  33.  Handbook of Discrete and Combinatorial Mathematics. S. 832.
  34.  Tóth-Valtr: In: Discrete Comput. Geom.. 19, S. 457 ff.
  35.  Halder-Heise: S. 143.
  36.  Volkmann: S. 362 ff.
  37.  Handbook of Discrete and Combinatorial Mathematics. S. 592 ff.
  38.  Handbook of Graph Theory. S. 838 ff.
  39. Diese Bezeichnung mit dem Kleinbuchstaben r statt mit dem Großbuchstaben R entspricht der üblichen Konvention der Graphentheorie (s. frühere Fußnote) und wird daher an dieser Stelle benutzt.
  40.  Handbook of Graph Theory. S. 842 ff.
  41.  Volkmann: S. 362 ff.
  42. Diese Gleichung stellt die Verbindung zu den klassischen Ramsey-Zahlen für vollständige Graphen her und belegt zugleich, dass es sich bei den verallgemeinerten Ramsey-Zahlen für endliche einfache Graphen in der Tat um einer Verallgemeinerung handelt.
  43. Dabei bezeichnet man mit   n ({\mathcal G})   für eine Graphen   {\mathcal G}   seine Ordnung, also die Anzahl seiner Knoten.
  44. a.a.O.
  45. C_n   ist der Kreisgraph mit   n   Knoten und   n   Kanten.
  46.  Chvátal: In: J. Graph Theory. 1, 1977, S. 93.
  47.  Burr-Roberts: In: Utilitas Math. 4, 1973, S. 217 ff.
  48.  Jukna: S. 67.
  49.  Handbook of Graph Theory. S. 841 ff.
  50. Weitere Abschätzungen dieser Art finden sich im Artikel des englischsprachigen Wikipedia. Siehe hier!
  51.  Bondy-Murty: Graph Theory with Applications. S. 250.
  52. Ob diese Vermutung von Erdős immer offen ist, kann derzeit (Stand Dezember 2014) nicht mit letzter Sicherheit gesagt werden. In ihrer erweiterten Monographie Graph Theory von 2008 haben Bondy und Murty diese Vermutung jedenfalls nicht mehr in die Liste der Unsolved Problems (S. 583 ff) aufgenommen.
  53.  Handbook of Graph Theory. S. 843.
  54. S. a.a.O. !
  55.  Handbook of Graph Theory. S. 842.
  56.  Bollobás: S. 135.
  57.  Handbook of Graph Theory. S. 843.
  58.  Neunhäuserer: S. 182-183.