Satz von Hales-Jewett

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

Kombinatorische Linie im Würfel

Vorbereitung

Mit $C_t^n=\{(x_1,\dots ,x_n):x_i\in [t]\}$ bezeichnet man einen $n$-dimensionalen Würfel über $t$ Elementen. Als Linie in $C_t^n$ wird eine passend geordnete Menge von Punkten ${𝐱}_1,\dots {𝐱}_t,{𝐱}_i=(x_{i1},\dots x_{in})$ bezeichnet, so dass in jeder Koordinate $1\le j\le n$ entweder

$x_{1j}=x_{2j}=\cdots =x_{tj}$

oder

$x_{sj}=s$ für $1\le s<t+1$

wobei letzteres mindestens einmal vorkommt, sonst wäre es nur ein Punkt. Beispielsweise ist $\{1211,1222,1233,1244\}$ eine Linie.

Als $t$-Färbung einer Menge $T$ bezeichnet man die Abbildung $\chi :T\to [t]$ und für $s\in T$ bezeichnet man $\chi (s)$ als Farbe. Man nennt $M\subseteq T$ monochromatisch falls $\chi$ konstant auf $M$ ist.

Aussage

Für alle $r,t$ existiert ein $HJ(r,t)$, so dass für $n\ge HJ$ folgendes gilt: Falls die Knoten $C_t^n$ $r$-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