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
Vorbereitung 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.
Aussage Für alle existiert ein , so dass für folgendes gilt: Falls die Knoten -gefärbt sind, dann existiert eine monochromatische Linie.
Literatur
A. W. Hales, R. I. Jewett: Regularity and positional games, Trans. Amer. Math. Soc. 106 (1963), 222–229
Einzelnachweis
Kategorie:Ramseytheorie Kategorie:Graphentheorie Kategorie:Kombinatorik Hales-Jewett, Satz von