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 $\mathbf {x} _{1},\dots \mathbf {x} _{t},\mathbf {x} _{i}=(x_{i1},\dots x_{in})$ bezeichnet, so dass in jeder Koordinate $1\leq j\leq n$ entweder

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

oder

$x_{sj}=s$ für $1\leq 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\geq 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