:This-Artikel stellt eine Einführung zur Verfügung. Für einen ausführlicheren und technischen Artikel, sieh den Lehrsatz von Ramsey.

Theorie von Ramsey, genannt nach dem britischen Mathematiker und Philosophen Frank P. Ramsey, ist ein Zweig der Mathematik, die die Bedingungen studiert, unter denen Ordnung erscheinen muss. Probleme in der Theorie von Ramsey stellen normalerweise eine Frage der Form: "Wie viele Elemente von einer Struktur dort sein müssen zu versichern, dass ein besonderes Eigentum halten wird?"

Beispiele

Ein typisches Ergebnis in der Theorie von Ramsey fängt mit einer mathematischen Struktur das an

wird dann entzweigeschnitten. Wie groß muss die ursprüngliche Struktur sein, um sicherzustellen, dass mindestens ein der Stücke ein gegebenes interessantes Eigentum haben?

Denken Sie zum Beispiel einen ganzen Graphen des Auftrags n; d. h. es gibt n Scheitelpunkte, und jeder Scheitelpunkt wird mit jedem anderen Scheitelpunkt durch einen Rand verbunden. Ein ganzer Graph des Auftrags 3 wird ein Dreieck genannt. Färben Sie jetzt jeden Rand rot oder Blau. Wie groß n muss sein, um sicherzustellen, dass es entweder ein blaues Dreieck oder ein rotes Dreieck gibt? Es stellt sich heraus, dass die Antwort 6 ist. Sieh den Artikel über den Lehrsatz von Ramsey für einen strengen Beweis.

Eine andere Weise, dieses Ergebnis auszudrücken, ist wie folgt: An jeder Partei mit mindestens sechs Menschen gibt es drei Menschen, die alle jeder gegenseitige Bekanntschaften sind (jeder weiß die anderen zwei), oder gegenseitige Fremde (jeder weiß keinen der anderen zwei). Sieh Lehrsatz auf Freunden und Fremden.

Das ist auch ein spezieller Fall des Lehrsatzes von Ramsey, der sagt, dass für jede gegebene ganze Zahl c, irgendwelche gegebenen ganzen Zahlen n..., n, es eine Zahl, R (n..., n), solch dass gibt, wenn die Ränder eines ganzen Graphen des Auftrags R (n..., n) mit c verschiedenen Farben gefärbt werden, dann für einige ich zwischen 1 und c muss es einen ganzen Subgraphen des Auftrags n enthalten, dessen Ränder die ganze Farbe i sind. Der spezielle Fall hat oben c = 2 und n = n = 3.

Ergebnisse

Zwei Schlüssellehrsätze der Theorie von Ramsey sind:

• Der Lehrsatz von Van der Waerden: Für irgendwelchen gegeben c und n gibt es eine Nummer V, solch dass, wenn V Konsekutivzahlen mit c verschiedenen Farben gefärbt werden, dann muss es einen arithmetischen Fortschritt der Länge n enthalten, dessen Elemente Farbe alle gleich sind.
• Hales-Jewett Lehrsatz: Für irgendwelchen gegeben n und c gibt es eine solche Nummer H, dass, wenn die Zellen eines H-dimensional n×n×n×...×n Würfel mit C-Farben gefärbt wird, es eine Reihe, Säule, usw. der Länge n geben muss alle sind dessen Zellen dieselbe Farbe. D. h. wenn Sie auf einem Ausschuss mit genug vielen Dimensionen spielen, dann kann Mehrfachabspiellaufwerk n hintereinander tic-tac-toe nicht in einer Attraktion enden, egal wie großer n ist, und egal wie viele Menschen spielen. Hales-Jewett Lehrsatz bezieht den Lehrsatz von Van der Waerden ein.

Ein dem Lehrsatz von van der Waerden ähnlicher Lehrsatz ist der Lehrsatz von Schur: Für irgendwelchen gegeben c gibt es eine solche Nummer N dass, wenn die Nummern 1, 2..., N mit c verschiedenen Farben gefärbt werden, dann muss es ein Paar von ganzen Zahlen x, y geben

solch, dass x, y, und x+y Farbe alle gleich sind. Viele Generalisationen dieses Lehrsatzes, bestehen einschließlich des Lehrsatzes von Rado, Rado-Folkman-Sanders Lehrsatz, der Lehrsatz von Hindman und der Lehrsatz von Milliken-Taylor. Eine klassische Verweisung für diese und viele andere Ergebnisse in der Theorie von Ramsey ist Graham und al.

Läuft auf Theorie von Ramsey hinaus normalerweise haben zwei primäre Eigenschaften. Erstens sind sie nichtkonstruktiv: Sie können zeigen, dass eine Struktur besteht, aber sie geben keinen Prozess, um diese Struktur (anders zu finden, als Suche der rohen Gewalt). Zum Beispiel ist der Ablegefach-Grundsatz dieser Form. Zweitens, während Theorie-Ergebnisse von Ramsey wirklich sagen, dass genug große Gegenstände eine gegebene Struktur notwendigerweise enthalten müssen, häufig verlangt der Beweis dieser Ergebnisse diese Gegenstände - Grenzen enorm groß zu sein, die exponential wachsen, oder gerade als schnell als die Funktion von Ackermann ziemlich üblich sind. In vielen Fällen sind diese Grenzen Kunsterzeugnisse des Beweises, und es ist nicht bekannt, ob sie wesentlich verbessert werden können. In anderen Fällen ist es bekannt, dass irgendwelcher gebunden hat, muss außerordentlich groß, manchmal noch größer sein als jede primitive rekursive Funktion; sieh den Lehrsatz des Paris-Harrington für ein Beispiel. Die Zahl von Graham, eine der größten im ernsten mathematischen Beweis jemals verwendeten Zahlen, ist ein oberer, der für ein mit der Theorie von Ramsey verbundenes Problem gebunden ist.

Lehrsätze in der Theorie von Ramsey sind allgemein einer der zwei Typen. Viele Lehrsätze, die nach dem Lehrsatz von Ramsey selbst modelliert werden, behaupten, dass in jeder Teilung eines großen strukturierten Gegenstands eine der Klassen notwendigerweise einen großen strukturierten Subgegenstand enthält, aber geben Sie keine Information, über die klassifizieren, ist das. Gelegentlich besteht der Grund hinter solchen Ramsey-Typ-Ergebnissen darin, dass die größte Teilungsklasse immer den gewünschten Unterbau enthält. Die Ergebnisse dieser Art werden entweder Dichte-Ergebnisse oder Turán-Typ-Ergebnis nach dem Lehrsatz von Turán genannt. Bemerkenswerte Beispiele schließen den Lehrsatz von Szemerédi ein, der solch eine Stärkung des Lehrsatzes von van der Waerden und die Dichte-Version des Hales-Jewett Lehrsatzes ist.

Siehe auch

• Bartel Leendert van der Waerden
• Combinatorics
• Der Lehrsatz von Goodstein
• Theorie von Ergodic Ramsey
• Graph-Theorie von Extremal

Zeichen