Hales–Jewett-tétel

A Wikipédiából, a szabad enciklopédiából

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

Fogalmak[szerkesztés | forrásszöveg szerkesztése]

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[szerkesztés | forrásszöveg szerkesztése]

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.

További információk[szerkesztés | forrásszöveg szerkesztése]