Ramsey-Theorie

Günter Schachner, 86 25 051

13. 12. 1997

``Of three ordinary people, two must have the same sex.''
D. J. KLEITMAN

Einführung

Ein klassisches Beispiel der Ramsey-Theorie ist das sogenannte ,,Partyproblem``: Wieviele Gäste muß man auf eine Party einladen, sodaß es auf jeden Fall drei Personen gibt, die alle einander entweder kennen oder nicht kennen. Dabei wird vorausgesetzt, daß ,,einander kennen`` eine symmetrische Beziehung ist, d.h. wenn eine Person eine andere kennt, so ist dies auch in umgekehrter Richtung der Fall. Man kann zeigen, daß sechs Personen zur Lösung dieses Problems ausreichen.

Wir können dieses Problem als graphentheoretisches Problem interpretieren: Gegeben sei ein vollständiger Graph der Größe k, dessen Kanten blau oder rot gefärbt sind. Wie groß ist k zu wählen, damit es immer einen einfärbigen vollständigen Teilgraph der Größe 3 gibt?

Der Satz von Ramsey

Der Ursprung der Ramsey-Theorie ist diffus. F. P. Ramsey interessierte sich in seiner Arbeit von 1930 für Entscheidungsprobleme in logischen Systemen. Dabei erkannte er den heute nach ihm benannten Satz auch als eigenständig wichtig, war aber in erster Linie an dessen Anwendung für besagte Entscheidungsprobleme interessiert.

Beim sogenannten Satz von Ramsey betrachtet man eine Verallgemeinerung des obigen ,,Partyproblems``. Dabei werden nun Färbungen mit r verschiedenen Farben betrachtet, und man fragt nach vollständigen Teilgraphen der Größe . Zusätzlich werden Hypergraphen anstelle gewöhnlicher Graphen betrachtet. Der Satz von Ramsey stellt sicher, daß es stets eine Lösung gibt, d.h. eine der geforderten Beziehungen ist stets erfüllt, wenn wir nur hinreichend viele Knoten betrachten.

Die Wiederentdeckung von Erdös und Szekeres

Populär wurde der Satz von Ramsey durch eine Arbeit von P. Erdös und G. Szekeres von 1935. Diese entdeckten diesen Satz unabhängig von F. P. Ramsey und anhand eines völlig anderen Problems. Esther Klein (später Szekeres) entdeckte, daß von fünf Punkten der Ebene stets vier ein konvexes Viereck bilden. Als Verallgemeinerung wurde folgende Variante erkannt: Für alle n gibt es stets ein N, sodaß unter beliebig angeordneten N Punkten in allgemeiner Lage (d.h. keine drei liegen auf einer Geraden) stets n Punkte existieren, die ein konvexes n-Eck bilden.

Klassische Sätze der Ramsey-Theorie

Die Ramsey-Theorie ist heute ein anerkanntes Teilgebiet der Diskreten Mathematik. Einige klassische Sätze lauten wie folgt:

F. P. Ramsey (1930):

Enthält ein Graph hinreichend viele Knoten (abhängig von k), so enthält er entweder eine vollständige oder eine unabhängige Knotenmenge der Größe k.

B. L. van der Waerden (1927):

Färben wir die natürlichen Zahlen mit endlich vielen Farben, so enthält mindestens eine Farbklasse eine beliebig lange arithmetische Folge.

I. Schur (1916):

Färben wir die natürlichen Zahlen mit endlich vielen Farben, so enthält mindestens eine Farbklasse natürliche Zahlen x, y, z mit x+y=z.

Literatur

1

P. Erdös, G. Szekeres. A Combinatorial Problem in Geometry, Composito Math. 2 (1935), 464-470

2

R. L. Graham, B. L. Rothschild, J. H. Spencer. Ramsey Theory, John Wiley & Sons, Wiley-Interscience series in discrete mathematics and optimization, NewYork et al., 1990

3

F. P. Ramsey. On a Problem of Formal Logic, Proc. London Math. Soc. 30 (1930), 361-376

Über dieses Dokument ...

Ramsey-Theorie

This document was generated using the LaTeX2HTML translator Version 96.1-e (April 9, 1996) Copyright © 1993, 1994, 1995, 1996, Nikos Drakos, Computer Based Learning Unit, University of Leeds.

The command line arguments were:
latex2html -split 0 n-schachner-r.

The translation was initiated by Wolfgang Slany on Fri Jan 9 14:32:29 MET 1998