Hales–Jewett-tétel

A Hales–Jewett-tétel a kombinatorika, ezen belül a Ramsey-elmélet egyik nevezetes tétele.

Fogalmak

Ha N és k természetes számok, jelölje ${\mathscr{H}}(N,k)$ azon $\mathbf{x}=(x_1,\dots ,x_N)$ vektorok halmazát, amelyeknek minden $x_i$ koordinátája egy 1 és k közötti természetes szám. Egyenesnek az olyan $L=\{{\mathbf{x}}_1,\dots ,{\mathbf{x}}_k\}$ halmazokat nevezzük, amelyekhez van indexeknek olyan nemüres S halmaza, hogy az ${\mathbf{x}}_i$-k S-en kívüli koordinátái azonosak, belül pedig ${\mathbf{x}}_i$ minden koordinátája i:

${\mathbf{x}}_i(k)={\mathbf{x}}_j(k),(k\notin S)$

${\mathbf{x}}_i(k)=i(k\in S)$.

A tétel állítása

Ha k, r természetes számok, akkor van olyan $N=HJ(k,r)$ természetes szám, hogy a következő állítás igaz: bárhogy színezzük az ${\mathscr{H}}(N,k)$ halmazt r színnel, mindig van egyszínű egyenes.

Megjegyzés

A Hales–Jewett-tételből következik a van der Waerden-tétel.

További információk

• Science News article on the collaborative proof of the density Hales-Jewett theorem (angolul)
• A detailed proof of Hales-Jewett theorem (angolul)
• A blog post by Steven Landsburg discussing how the proof of this theorem was improved collaboratively on a blog (angolul)