Hales–Jewett-tétel

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

FogalmakSzerkesztés

Ha N és k természetes számok, jelölje   azon   vektorok halmazát, amelyeknek minden   koordinátája egy 1 és k közötti természetes szám. Egyenesnek az olyan   halmazokat nevezzük, amelyekhez van indexeknek olyan nemüres S halmaza, hogy az  -k S-en kívüli koordinátái azonosak, belül pedig   minden koordinátája i:

 
 .

A tétel állításaSzerkesztés

Ha k, r természetes számok, akkor van olyan   természetes szám, hogy a következő állítás igaz: bárhogy színezzük az   halmazt r színnel, mindig van egyszínű egyenes.

MegjegyzésSzerkesztés

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

További információkSzerkesztés