Ramseytheorie - LinkFang.de





Ramseytheorie


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 diese Struktur in der Teilmenge wiedergefunden werden kann und eine bestimmte Eigenschaft erfüllt ist. Berühmte Sätze der Ramseytheorie haben dabei alle diese Eigenschaft gemeinsam.

Beispiele

Als einfaches Beispiel gilt das Schubfachprinzip. Dieses besagt, dass beim Verteilen von [math]k+1[/math] Objekten auf [math]k[/math] Schubfächer wenigstens eines der Schubfächer mindestens zwei Objekte enthält.

In einem weiteren Beispiel treffen 6 Personen aufeinander. Je zwei sind entweder miteinander befreundet oder nicht befreundet. Dann gibt es (stets!) eine Gruppe von dreien, die jeweils miteinander befreundet bzw. nicht befreundet sind.

Formulierung der Lösung als Graphenproblem

Sei [math]\mathcal{G}=(V,E)[/math] ein Graph mit [math]n=6[/math] Knoten (für die Personen) und roten Kanten für Freunde bzw. grauen Kanten für Nicht-Freunde. Wir betrachten eine Person [math]A[/math]. Diese hat stets mindestens drei Freunde oder Nicht-Freunde (Abb. 1). Würden nun zwei der drei gleichartigen Endknoten (im Bild rot verbunden) mit einer weiteren roten Kante verknüpft, so haben wir bereits eine Gruppe von Dreien, die alle miteinander befreundet (oder auch nicht) sind. Würden hingegen alle drei Endknoten mit drei grauen Kanten verbunden, so hätten wir auch wieder eine Gruppe von Dreien, die alle unbefreundet (befreundet) sind.

In diesem Beispiel werden Paare aus einer sechselementigen Menge in zwei disjunkte Klassen eingeordnet (Freunde und nicht Freunde). Egal, wie die Zuordnung aussieht, existiert eine homogene Dreiergruppe.

Ein anderes Beispiel ist Sim.

Berühmte Sätze der Ramseytheorie

  • Das Schubfachprinzip macht Aussagen über die Anzahl der in Schubfächern befindlichen Objekte und gilt als Ausgangspunkt der Ramseytheorie.
  • Der klassische Satz von Ramsey untersucht, wie groß ein Graph sein muss, damit für eine Färbung stets eine Clique in entsprechender Farbe und Größe existiert. Unendliche Versionen dieses Satzes spielen in der abstrakten Mengenlehre eine Rolle, siehe Satz von Ramsey (Mengenlehre).
  • Der Satz von Van der Waerden untersucht die minimale Größe einer Menge [math]\{1, \cdots, n\}[/math], so dass unter einer Färbung dieser Menge stets eine einfarbige arithmetische Folge bestimmter Länge zu finden ist.
  • Das Färben von Ebenen, genauer gesagt, das Färben der Ebene [math]x+y=z[/math] ist unter dem Satz von Schur bekannt geworden.

Literatur

  • Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer: Ramsey Theory. 2. Auflage. Wiley, New York, NY, 1990, ISBN 0-471-50046-1
  • Bruce M. Landman, Aaron Robertson: Ramsey Theory on the Integers. 1. Auflage. AMS, Rhode Island, 2004, ISBN 0-8218-3199-2
  • Richard Rado: Studien zur Kombinatorik. Dissertation, Berlin 1933

Kategorien: Teilgebiet der Mathematik | Graphentheorie | Ramseytheorie

Quelle: Wikipedia - http://de.wikipedia.org/wiki/Ramseytheorie (Vollständige Liste der Autoren des Textes [Versionsgeschichte])    Lizenz: CC-by-sa-3.0

Änderungen: Alle Bilder mit den meisten Bildunterschriften wurden entfernt. Ebenso alle zu nicht-existierenden Artikeln/Kategorien gehenden internen Wikipedia-Links (Bsp. Portal-Links, Redlinks, Bearbeiten-Links). Entfernung von Navigationsframes, Geo & Normdaten, Mediadateien, gesprochene Versionen, z.T. ID&Class-Namen, Style von Div-Containern, Metadaten, Vorlagen, wie lesenwerte Artikel. Ansonsten sind keine Inhaltsänderungen vorgenommen worden. Weiterhin kann es durch die maschinelle Bearbeitung des Inhalts zu Fehlern gerade in der Darstellung kommen. Darum würden wir jeden Besucher unserer Seite darum bitten uns diese Fehler über den Support mittels einer Nachricht mit Link zu melden. Vielen Dank!

Stand der Informationen: August 201& - Wichtiger Hinweis: Da die Inhalte maschinell von Wikipedia übernommen wurden, ist eine manuelle Überprüfung nicht möglich. Somit garantiert LinkFang.de nicht die Richtigkeit und Aktualität der übernommenen Inhalte. Sollten die Informationen mittlerweile fehlerhaft sein, bitten wir Sie darum uns per Support oder E-Mail zu kontaktieren. Wir werden uns dann innerhalb von spätestens 10 Tagen um Ihr Anliegen kümmern. Auch ohne Anliegen erfolgt mindestens alle drei Monate ein Update der gesamten Inhalte.