High Quality Content by WIKIPEDIA articles! Van der Waerden's theorem states that for any positive integers r and k there exists a positive integer N such that if the integers {1, 2, ..., N} are colored, each with one of r different colors, then there are at least k integers in arithmetic progression all of the same color. The smallest such N is the van der Waerden number W(r,k). Van der Waerden numbers are primitive recursive, as proved by Shelah; in fact he proved that they are (at most) on the fifth level mathcal{E}^5 of the Grzegorczyk hierarchy. W(1,k)=k for any integer k, since one color produces only trivial colorings RRRRR...RRR (for the single color denoted R). W(r,2)=r+1, since we may construct a coloring that avoids arithmetic progressions of length 2 by using each color at most once, but once we use a color twice, a length 2 arithmetic progression is formed (e.g., for r=3, the longest coloring we can get that avoids an arithmetic progression of length 2 is RGB).

Данное издание не является оригинальным. Книга печатается по технологии принт-он-деманд после получения заказа.