Рамсей теориясы: Ван дер Ваерден теоремасы

Theorem in Ramsey theory
Van der Waerden's theorem is a theorem in the branch of mathematics called Ramsey theory. Van der Waerden's theorem states that for any given positive integers r and k, there is some number 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 whose elements are of the same color. The least such N is the Van der Waerden number W(r, k), named after the Dutch mathematician B. L. van der Waerden. This was conjectured by Pierre Joseph Henry Baudet in 1921. Waerden heard of it in 1926 and published his proof in 1927, titled Beweis einer Baudetschen Vermutung [Proof of Baudet's conjecture].

The following proof is due to Ron Graham, B. L. Rothschild, and Joel Spencer. Khinchin gives a fairly simple proof of the theorem without estimating W(r, k).

The proof for W(2, 3) depends essentially on proving that W(32, 2) ≤ 33. We divide the integers {1, ,325} into 65 'blocks', each of which can be colored in 32 different ways, and then show that two blocks of the first 33 must be the same color, and there is a block colored the opposite way. Similarly, the proof for W(3, 3) depends on proving that

By a double induction on the number of colors and the length of the progression, the theorem is proved in general.

Furstenberg and Weiss proved an equivalent form of the theorem in 1978, using ergodic theory. The proof of the above theorem is delicate, and the reader is referred to. With this recurrence theorem, the van der Waerden theorem can be proved in the ergodic theoretic style.