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}$ 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 ${\mathcal {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)