Hales–Jewett-tétel

A Wikipédiából, a szabad enciklopédiából
Jump to navigation Jump to search

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

Fogalmak[szerkeszté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ása[szerkeszté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és[szerkesztés]

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

További információk[szerkesztés]