Van der Waerden-tétel

Van der Waerden tétele a kombinatorikus számelmélet és általában a kombinatorika egyik fontos tétele.

A tétel szerint, ha ${\displaystyle k,r}$ egynél nagyobb természetes számok, akkor van olyan (legkisebb) ${\displaystyle W(k,r)}$ természetes szám, hogy a következő állítás igaz: akárhogyan osztjuk ${\displaystyle r}$ osztályba az ${\displaystyle \{1,2,\dots ,W(k,r)\}}$ halmazt, valamelyik osztály tartalmaz ${\displaystyle k}$ tagú számtani sorozatot.

Bizonyítás

Az állítás igazolása k-ra vonatkozó indukcióval történik. A k=2 eset nyilvánvaló: ha az 1-től r+1-ig terjedő természetes számokat r osztályba osztjuk, a skatulyaelv szerint valamelyik osztály tartalmaz két elemet, ezek pedig kéttagú számtani sorozatot alkotnak. Másfelől, 1-től r-ig az egész számokat külön-külön osztályba sorolva nincs egy osztályba tartozó, kéttagú számtani sorozat. Tehát ${\displaystyle W(2,r)=r+1}$.

Tegyük fel, hogy k-ra már tudjuk az eredményt és ${\displaystyle W(k,r)}$ létezését szeretnénk igazolni. Ehhez készítsük el a következő ${\displaystyle f(0),f(1),\dots ,f(r)}$ sorozatot: ${\displaystyle f(0)=1}$ és ha ${\displaystyle f(s)}$ megvan, legyen ${\displaystyle f(s+1)=2MN}$, ahol ${\displaystyle N=f(s)}$ és ${\displaystyle M=W(k,r^{N})}$. s-re indukcióval igazoljuk a következő állítást: ha az ${\displaystyle \{1,\dots ,f(s)\}}$ számokat r színnel színezzük, akkor vagy van k+1 hosszú egyszínű számtani sorozat, vagy van s olyan k+1 hosszú számtani sorozat, ${\displaystyle A_{1},\dots ,A_{s}}$, hogy az ${\displaystyle A_{i}}$-k utolsó tagja közös, e tagot elhagyva pedig minden ${\displaystyle A_{i}}$ egyszínű és e színek különbözők.

Ha ezt beláttuk, akkor ${\displaystyle W(k+1,r)}$ választható ${\displaystyle f(r)}$-nek.

Többdimenziós általánosítás

A tétel többdimenziós változatát Gallai Tibor igazolta.

Történet

Issai Schur eredeti kérdése úgy hangzott, igaz-e, hogy minden k természetes számhoz van olyan N természetes szám, hogy ha az 1,…,N számokat két osztályba osztjuk, valamelyik mindenképpen tartalmaz k-tagú számtani sorozatot. Az általános eredményt Bartel Leendert van der Waerden 1927-ben igazolta.

Lásd még

• Hales–Jewett-tétel
• Szemerédi-tétel

Irodalom

• B. L. van der Waerden: Beweis einer Baudetschen Vermutung, Nieuw. Arch. Wisk., 15(1927), 212-216.
• B. L. van der Waerden: Ötlet és meggondolás a matematikában. A Baudet-sejtés bizonyítása, Matematikai Lapok, 22(1971), 25-30.