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 $𝐱=(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=\{{𝐱}_1,\dots ,{𝐱}_k\}$ halmazokat nevezzük, amelyekhez van indexeknek olyan nemüres S halmaza, hogy az ${𝐱}_i$-k S-en kívüli koordinátái azonosak, belül pedig ${𝐱}_i$ minden koordinátája i:

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

${𝐱}_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 Sablon:En
• A detailed proof of Hales-Jewett theorem Sablon:En
• A blog post by Steven Landsburg discussing how the proof of this theorem was improved collaboratively on a blog Sablon:En