Satz von Hales-Jewett

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Der Satz von Hales-Jewett ist ein mathematischer Satz aus der Ramseytheorie. Im Kern behandelt der Satz die Frage, ob hoch-dimensionale Objekte zwingend eine kombinatorische Struktur besitzen.

Er ist nach den amerikanischen Mathematikern Alfred W. Hales und Robert I. Jewett benannt.

Satz von Hales-Jewett

[Bearbeiten | Quelltext bearbeiten]
Kombinatorische Linie im Würfel

Mit bezeichnet man einen -dimensionalen Würfel über Elementen. Als Linie in wird eine passend geordnete Menge von Punkten bezeichnet, so dass in jeder Koordinate entweder

oder

für

wobei letzteres mindestens einmal vorkommt, sonst wäre es nur ein Punkt. Beispielsweise ist eine Linie.

Als -Färbung einer Menge bezeichnet man die Abbildung und für bezeichnet man als Farbe. Man nennt monochromatisch falls konstant auf ist.

Für alle existiert ein , so dass für folgendes gilt: Falls die Knoten -gefärbt sind, dann existiert eine monochromatische Linie.[1]

  • A. W. Hales, R. I. Jewett: Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222–229
  1. Ronald L. Graham, Bruce L. Rothschild, Joel H. Spencer: Ramsey Theory. 2. Auflage. Wiley-Interscience, 1991, ISBN 978-0-471-50046-9, S. 36 (englisch).