Satz von Ramsey

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

Eine 2-Färbung des K₅ ohne monochromatisches K₃

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

Betrachtet man umgekehrt einen auf beliebige Weise rot-blau gefärbten ${\displaystyle K_{6}}$ und hierin eine beliebige Ecke ${\displaystyle v}$, so tritt bei den fünf in ${\displaystyle 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 ${\displaystyle K_{3}}$. Andernfalls sind alle Kanten zwischen diesen drei Endpunkten blau, und wir haben ein blaues ${\displaystyle K_{3}}$. In jedem rot-blau-gefärbten ${\displaystyle K_{6}}$ findet man also ein rotes ${\displaystyle K_{3}}$ oder ein blaues ${\displaystyle K_{3}}$, d. h., es gilt: ${\displaystyle R(3,3)\leq 6}$.

Insgesamt erhält man also ${\displaystyle R(3,3)=6}$.

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

• ${\displaystyle R(r,b)=R(b,r)}$
• ${\displaystyle R(r,1)=R(1,r)=1}$   für   ${\displaystyle r\geq 1}$
• ${\displaystyle R(r,2)=R(2,r)=r}$   für   ${\displaystyle r\geq 2}$
• ${\displaystyle R(r_{1},b_{1})\leq R(r_{2},b_{2})}$   für   ${\displaystyle r_{1}\leq r_{2},b_{1}\leq b_{2},}$
• ${\displaystyle R(r,b)\leq R(r-1,b)+R(r,b-1)}$  für   ${\displaystyle r,b\geq 2}$
• ${\displaystyle R(r,b)\leq R(r-1,b)+R(r,b-1)-1}$   für   ${\displaystyle 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:

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

Für den Fall ${\displaystyle r=3}$ lässt sich diese noch verschärfen:[5]

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

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

• ${\displaystyle 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   ${\displaystyle 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]

• ${\displaystyle 2^{r/2}<R(r,r)<4^{r-1}}$   für   ${\displaystyle 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]

• ${\displaystyle R(3,3)=6}$
• ${\displaystyle R(3,4)=9}$
• ${\displaystyle R(3,5)=14}$
• ${\displaystyle R(3,6)=18}$
• ${\displaystyle R(3,7)=23}$
• ${\displaystyle R(3,8)=28}$
• ${\displaystyle R(3,9)=36}$

sowie

• ${\displaystyle R(4,4)=18}$
• ${\displaystyle R(4,5)=25}$  .

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

• ${\displaystyle 35\leq R(4,6)\leq 41}$

oder

• ${\displaystyle 43\leq R(5,5)\leq 48}$  .[11]

Ü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

• ${\displaystyle R(3,3,3)=17}$[12]

und dann noch eine obere und untere Schranke zu Kantenfärbungen mit vier Farben:

• ${\displaystyle 51\leq R(3,3,3,3)\leq 65}$  .[13]

Die kleinste natürliche Zahl, die als Zahl   ${\displaystyle R}$   im allgemeinen Satz von Ramsey bei gegebenem   ${\displaystyle k}$   und gegebenen   ${\displaystyle q_{1},q_{2},\ldots ,q_{t}}$   gewählt werden kann, heißt die zu   ${\displaystyle k\,}$   und   ${\displaystyle 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   ${\displaystyle R(q_{1},q_{2},\ldots ,q_{t};k)}$   oder in ähnlicher Weise bezeichnet.[19]

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

• ${\displaystyle R(q_{1},q_{2};2)=R(q_{1},q_{2})}$   sowie   ${\displaystyle R(q_{1},\ldots ,q_{t})=R(q_{1},\ldots ,q_{t};2)}$[23]
• ${\displaystyle R(2,2,\ldots ,2;2)=2}$
• ${\displaystyle R(q_{1},q_{2},\ldots ,q_{t};1)=q_{1}+q_{2}+\cdots +q_{t}-t+1}$
• ${\displaystyle R(q_{1},k,\ldots ,k;k)=q_{1}}$   für ${\displaystyle k,q_{1}\in \mathbb {N} \,,\,q_{1}\geq k}$

Weiter ist für den Fall   ${\displaystyle t=2}$   noch die folgende Ungleichung gegeben:[24]

• ${\displaystyle 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 ${\displaystyle q_{1},q_{2},k\in \mathbb {N} \,,\,1<k<\min(q_{1},q_{2})}$

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

• ${\displaystyle 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   ${\displaystyle q_{1},\ldots ,q_{t}\geq 2}$  .

Für ${\displaystyle t=2}$   und   ${\displaystyle q_{1}=3}$ gibt es noch folgende Verschärfung:

• ${\displaystyle R(3,q_{2};2)\leq {\frac {1}{2}}({q_{2}}^{2}+3)}$   für   ${\displaystyle q_{2}\geq 3}$  .[25]

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   ${\displaystyle t=2,k=3,q_{1}=q_{2}=4}$   . Hier gilt:

• ${\displaystyle R(4,4;3)=13}$   .

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

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

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

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

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

Es sind also

• ${\displaystyle \kappa (3)=3}$
• ${\displaystyle \kappa (4)=5}$
• ${\displaystyle \kappa (5)=9}$
• ${\displaystyle \kappa (6)=17}$   .

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

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

Zu je zwei beliebig vorgegebenen natürlichen Zahlen   ${\displaystyle m,t}$   mit   ${\displaystyle m\geq 2}$   existiert stets eine kleinste natürliche Zahl   ${\displaystyle S=S(m,t)}$   mit folgender Eigenschaft:

Ist   ${\displaystyle n}$   eine natürliche Zahl mit   ${\displaystyle n\geq S}$   und liegt für das Anfangsstück   ${\displaystyle A=\{1,2\,\ldots ,n\}\subset \mathbb {N} }$   irgendeine Zerlegung

${\displaystyle A=A_{1}{\dot {\cup }}A_{2}{\dot {\cup }}\,\dots {\dot {\cup }}A_{t}\,}$

in   ${\displaystyle t}$   Klassen vor,

so enthält mindestens eine der Mengen ${\displaystyle A_{s}\,(s\in \{1,2,\ldots ,t\})}$   ein   ${\displaystyle m}$-Tupel   ${\displaystyle (a_{1},a_{2}\,\dots ,a_{m})}$   von (nicht notwendig verschiedenen) Zahlen, welche die Gleichung:

${\displaystyle a_{1}+a_{2}+\,\dots +a_{m-1}=a_{m}}$

erfüllen.

Aus dem von Halder und Heise gelieferten Beweis geht hervor, dass die mit dem schurschen Satz definierte Schur-Zahl   ${\displaystyle S(m,t)}$   stets unterhalb der Ramsey-Zahl   ${\displaystyle R(q_{1},q_{2},\ldots ,q_{t};2)}$   ${\displaystyle (q_{1}=q_{2}=\,\ldots =q_{t}=m)}$   liegt.[34]

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

Für sie gelten folgende allgemeine Beziehungen:[39][35]

• ${\displaystyle r(K_{q_{1}},K_{q_{2}},\ldots ,K_{q_{t}})=R(q_{1},q_{2},\ldots ,q_{t})=R(q_{1},q_{2},\ldots ,q_{t};2)}$[40]
• ${\displaystyle r({\mathcal {G}}_{1},{\mathcal {G}}_{2},\ldots ,{\mathcal {G}}_{t})\leq R(q_{1},q_{2},\ldots ,q_{t};2)}$   , wenn   ${\displaystyle n({\mathcal {G}}_{i})=q_{i}}$   ${\displaystyle (i=1,2,\ldots ,t)}$[41]
• ${\displaystyle r({\mathcal {G}}_{\sigma (1)},{\mathcal {G}}_{\sigma (2)},\ldots ,{\mathcal {G}}_{\sigma (t)})=r({\mathcal {G}}_{1},{\mathcal {G}}_{2},\ldots ,{\mathcal {G}}_{t})}$   für jede Permutation   ${\displaystyle \sigma \colon \{1,2,\ldots ,t\}\rightarrow \{1,2,\ldots ,t\}}$

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:

• ${\displaystyle r(C_{3},C_{3})=6}$[42]
• ${\displaystyle r(C_{4},C_{4})=6}$
• ${\displaystyle r(C_{5},C_{5},C_{5})=17}$
• ${\displaystyle r(C_{7},C_{7},C_{7})=25}$
• ${\displaystyle r(B_{q_{1}},K_{q_{2}})=1+(q_{1}-1)(q_{2}-1)}$   für   ${\displaystyle q_{1},q_{2}\in \mathbb {N} }$   ,   ${\displaystyle q_{1}\geq 2}$   und Baumgraphen   ${\displaystyle B_{q_{1}}}$   mit   ${\displaystyle n(B_{q_{1}})=q_{1}}$[43]
• ${\displaystyle r(K_{1,q_{1}},K_{1,q_{2}},\ldots ,K_{1,q_{t}})=\alpha -t+q_{1}+q_{2}+\cdots +q_{t}}$   für   ${\displaystyle t\geq 2}$   Sterngraphen   ${\displaystyle K_{1,q_{i}}}$   ${\displaystyle (i=1,2,\ldots ,t)}$   , wobei   ${\displaystyle \alpha =1}$   ist, sofern unter den natürlichen Zahlen   ${\displaystyle q_{1},q_{2},\ldots ,q_{t}}$   zwei oder mehr gerade Zahlen vorkommen und deren Anzahl ihrerseits eine gerade Zahl ist, und   ${\displaystyle \alpha =2}$   sonst[44]

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

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

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:[50]

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

Bislang gesichert ist, dass für derartige ungeraden Zahlen   ${\displaystyle n}$   immer die Ungleichung

• ${\displaystyle r(C_{n},C_{n},C_{n})\geq 4n-3}$

Bestand hat.

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

• Für Baumgraphen   ${\displaystyle B_{p}}$   und   ${\displaystyle B_{q}}$   mit   ${\displaystyle p,q\geq 2}$   ist stets   ${\displaystyle r(B_{p},B_{q})\leq p+q-2}$   .

Verknüpft mit der 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:[52][50]

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

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

• ${\displaystyle r(5,5)=43}$