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 $k,r$ egynél nagyobb természetes számok, akkor van olyan (legkisebb) $W(k,r)$ természetes szám, hogy a következő állítás igaz: akárhogyan osztjuk $r$ részre az $\{1,2,\dots,W(k,r)\}$ halmazt, valamelyik rész tartalmaz $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 a az 1-től r+1-ig terjedő természetes számokat r részre osztjuk, valamelyik rész tartalmaz két elemet, ezek pedig kéttagú számtani sorozatot alkotnak. Tehát $W(2,r)=r+1$.

Tegyük fel, hogy k-ra már tudjuk az eredményt és $W(k,r)$ létezését szeretnénk igazolni. Ehhez készítsük el a következő $f(0),f(1),\dots,f(r)$ sorozatot: $f(0)=1$ és ha $f(s)$ megvan, legyen $f(s+1)=2MN$, ahol $N=f(s)$ és $M=W(k,r^N)$. s-re indukcióval igazoljuk a következő állítást: ha az $\{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, $A_1,\dots,A_s$, hogy az $A_i$-k utolsó tagja közös, e tagot elhagyva pedig minden $A_i$ egyszínű és e színek különbözők.

Ha ezt beláttuk, akkor $W(k+1,r)$ választható $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 részre 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.