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 ${\mathcal H}(N,k)$ azon ${\mathbf x}=(x_1,\dots,x_N)$ vektorok halmazát, amelyeknek minden $x_i$ koorodiná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 ${\mathcal H}(N,k)$ halmazt r színnel, mindig van egyszínű egyenes.

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)