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 ${\displaystyle {\mathcal {H}}(N,k)}$ azon ${\displaystyle {\mathbf {x} }=(x_{1},\dots ,x_{N})}$ vektorok halmazát, amelyeknek minden ${\displaystyle x_{i}}$ koordinátája egy 1 és k közötti természetes szám. Egyenesnek az olyan ${\displaystyle L=\{{\mathbf {x} }_{1},\dots ,{\mathbf {x} }_{k}\}}$ halmazokat nevezzük, amelyekhez van indexeknek olyan nemüres S halmaza, hogy az ${\displaystyle {\mathbf {x} }_{i}}$-k S-en kívüli koordinátái azonosak, belül pedig ${\displaystyle {\mathbf {x} }_{i}}$ minden koordinátája i:

${\displaystyle {\mathbf {x} }_{i}(k)={\mathbf {x} }_{j}(k),(k\notin S)}$

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

A tétel állítása

Ha k, r természetes számok, akkor van olyan ${\displaystyle N=HJ(k,r)}$ természetes szám, hogy a következő állítás igaz: bárhogy színezzük az ${\displaystyle {\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)