Satz von Ramsey

Satz von Ramsey

Der Satz von Ramsey (nach Frank Plumpton Ramsey) beantwortet die Frage, ob in einem Graphen zwingend gewisse Unterstrukturen auftreten. Genauer werden gefärbte vollständige Graphen auf das Auftreten monochromatischer Teilgraphen hin betrachtet, und es stellt sich heraus, dass solche für hinreichend große Graphen tatsächlich auftreten müssen. Eine praktische Anwendung ist das Spiel Sim.

Erheblich schwieriger als die reine Existenzaussage gestaltet sich die genaue Quantifizierung, was hierbei als „hinreichend groß“ zu betrachten ist, d.h. die genaue Berechnung oder wenigstens Abschätzung der Ramsey-Zahlen.

Inhaltsverzeichnis

Aussage des Satzes

Wir betrachten einen vollständigen Graphen mit n Ecken, dessen Kanten mit zwei Farben, etwa rot und blau, gefärbt wurden. Gibt es hierin r Ecken, so dass alle Kanten zwischen diesen rot sind, so sagen wir, der Graph enthalte einen roten r-Teilgraphen, entsprechend für blaue Teilgraphen. Mit diesen Bezeichnungen behauptet der Satz von Ramsey:

Seien r,b natürliche Zahlen. Jeder hinreichend große vollständige Graph, dessen Kanten rot oder blau gefärbt wurden, enthält einen roten r-Teilgraphen oder einen blauen b-Teilgraphen. „Hinreichend groß“ bedeutet hierbei n\geq N für eine von r und b abhängige Zahl N. Die kleinstmögliche Zahl, die für N gewählt werden kann, heißt Ramsey-Zahl und wird mit R(r,b) bezeichnet. Umgekehrt ist es also möglich, den vollständigen Graphen mit R(r,b) − 1 Ecken so zu färben, dass man weder einen roten r-Teilgraphen noch einen blauen b-Teilgraphen erzeugt.

Der Satz gilt auch in verallgemeinerter Form für mehr als zwei Farben. Entsprechend gibt es auch zu Färbungen mit c Farben gehörige Ramsey-Zahlen R(n_1,\ldots, n_c).

Beispiele

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

Berechnung von R(3,3)

Eine 2-Färbung des K5 ohne monochromatisches K3

Das nebenstehende Bild zeigt, dass es möglich ist, den K5, 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 K6 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 K3. Andernfalls sind alle Kanten zwischen diesen drei Endpunkten blau, und wir haben ein blaues K3. In jedem rot-blau-gefärbten K6 findet man also ein rotes K3 oder ein blaues K3, d.h., es gilt: R(3,3)\leq 6.

Insgesamt ergibt sich also der exakte Wert R(3,3) = 6.

Die hier gemachten Überlegungen zeigen bereits wesentliche Gedanken für einen Beweis des Satzes sowie eine einfache rekursive Abschätzung für Ramsey-Zahlen, die jedoch für eine exakte Bestimmung der Ramsey-Zahlen nicht ausreicht:

R(r,b)\leq R(r-1,b)+R(r,b-1).

Veranschaulichung

Die Ramsey-Zahl R(r,b) beantwortet die Frage, wie viele Personen man z.B. zu einer Party einladen muss, damit sich r Gäste untereinander nicht kennen oder b Gäste sich kennen. „Kennen“ ist in diesem Beispiel eine symmetrische Relation, d.h., wenn Person A Person B kennt, so kennt B auch A.

Betrachten wir beispielsweise R(3,2) = 3. Mit r = 3 und b = 2 folgt R(3,2) = 3 = N (siehe oben).

Haben wir also N = 3 Gäste, so können wir nun den vollständigen Graphen K3 zeichnen und das Färben beginnen. Man muss jede Kante entweder rot oder blau färben (rot: Gäste kennen sich nicht, blau: Gäste kennen sich) und erreicht folgende mögliche Färbungen:

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

  • Es kennen sich alle drei.
  • Niemand kennt jemand anderes.
  • Eine Person kennt zwei Personen, die einander vorher nicht kannten.
  • Zwei Personen kennen sich, aber die dritte Person nicht.

Diese Beschreibung dient lediglich zur Veranschaulichung. Die Analogie zu den Gästen behandelt nicht Probleme, die seltsame „Kennen-sich(-nicht)“-Beziehungen haben (alle kennen sich nicht, zwei kennen sich, aber wer ist der 3.) Ebenso wird nicht berücksichtigt, dass evtl. Person A Person B kennt, aber Person B Person A nicht kennt. Außerdem werden keine transitiven Beziehungen dargestellt.

Literatur

  • F. P. Ramsey: On a problem of formal logic. In: Proc. London Math. Soc. series 2, Bd. 30 (1930), S. 264–286

Weblinks


Wikimedia Foundation.

Игры ⚽ Нужно сделать НИР?

Schlagen Sie auch in anderen Wörterbüchern nach:

  • Satz von Ramsey (Mengenlehre) — Der Satz von Ramsey ist ein von F. P. Ramsey im Jahre 1929 bewiesener Satz aus dem mathematischen Gebiet der Mengenlehre. Er verallgemeinert die einfache Tatsache, dass bei einer Zerlegung einer unendlichen Menge in endlich viele Teilmengen… …   Deutsch Wikipedia

  • Satz von Schur — Der Satz von Schur liefert in der diskreten Mathematik Aussagen, wie groß eine Zahlenmenge [1,s(r)] sein muss, damit für jede beliebige r Färbung dieser stets eine einfarbige Lösung existiert. Dieser Satz war ursprünglich ein Hilfssatz in einer… …   Deutsch Wikipedia

  • Satz von Erdös-Rado — Der Satz von Erdös Rado, benannt nach Paul Erdős und Richard Rado, ist ein mathematischer Satz aus dem Gebiet der Mengenlehre. Er trifft eine Aussage darüber, wie groß eine Menge sein muss, um eine gewisse Zerlegungseigenschaft zu haben. Die… …   Deutsch Wikipedia

  • Satz von Van der Waerden — Der Satz von Van der Waerden (nach Bartel Leendert van der Waerden) ist ein berühmter Satz aus der Kombinatorik, genauer aus der Ramseytheorie. Er besagt, dass für alle natürlichen Zahlen r und l eine natürliche Zahl N(r,l) existiert, so dass… …   Deutsch Wikipedia

  • Ramsey — ist der Name folgender Orte: Ramsey (England), Großbritannien Ramsey (Isle of Man), Großbritannien Ramsay (Illinois), USA Ramsey (Minnesota), USA Ramsey (New Jersey), USA Ramsey County, unterschiedliche Gebiete Ramsey ist der Familienname… …   Deutsch Wikipedia

  • Ramsey-Theorie — Die Ramseytheorie (nach Frank Plumpton Ramsey) ist ein Zweig der Kombinatorik innerhalb der Diskreten Mathematik. Sie behandelt die Frage, wie viele Elemente aus einer mit einer gewissen Struktur versehenen Menge ausgewählt werden müssen, damit… …   Deutsch Wikipedia

  • Frank P. Ramsey — Frank Plumpton Ramsey (* 22. Februar 1903 in Cambridge; † 19. Januar 1930) war ein britischer Mathematiker und Logiker. Inhaltsverzeichnis 1 Leben und Wirken 2 Werke (Auswahl) 3 Literatur …   Deutsch Wikipedia

  • Frank Plumpton Ramsey — (* 22. Februar 1903 in Cambridge; † 19. Januar 1930) war ein britischer Mathematiker und Logiker. Inhaltsverzeichnis 1 Leben und Wirken 2 Werke (Auswahl) 3 Literatur …   Deutsch Wikipedia

  • Liste von Physikern — Die Liste von Physikern ist alphabetisch sortiert und enthält nur Forscher, die wesentliche Beiträge zum Fachgebiet geleistet haben. Die Liste soll neben den Lebensdaten das Fachgebiet des Forschers nennen und wenige Stichworte zu den Aspekten… …   Deutsch Wikipedia

  • Liste von Titel- und Erkennungsmelodien aus Funk und Fernsehen — Die Liste von Titel und Erkennungsmelodien aus Funk und Fernsehen beinhaltet Titelmelodien, die bei Fernseh und Rundfunksendungen verwendet werden bzw. wurden. Diese werden auch oft als „Unterleger“ verwendet. Inhaltsverzeichnis 1… …   Deutsch Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”