Теорема ван дер Вардена

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

Теорема ван дер Вардена — математичне твердження у комбінаториці, зокрема її розділі — теорії Рамсея. Названа на честь голландського математика Бартела ван дер Вардена, котрий вперше довів її[1].

Теорема стверджує, що для довільних k,r \in \N, існує натуральне число W(k, r), таке, що якщо множину \{1,2,\dots,W(k,r)\} розбити на r класів, то принаймні один клас містить k членів арифметичної прогресії.

Наприклад коли r = 2, позначаючи числа кольорами, наприклад червоним і синім. W(3, 2) є більшим ніж 8, тому що, позначивши числа {1, …, 8} таким чином:

       1  2  3  4  5  6  7  8
       B  R  R  B  B  R  R  B 

бачимо, що жодні три числа одного кольору не утворюють арифметичну прогресію. Але додати дев'яте число без утворення такої послідовності неможливо. Тому, W(2, 3) рівне 9.

Питання визначення W(k, r) для довільних k,r \in \N, залишається відкритим. Усі відомі доведення теореми ван дер Вардена дають лише верхні межі для визначення цих чисел. Найкращий в цей час результат належить англійському математику Тімоті Ґоверсу:

W(k,r) \leq 2^{2^{r^{2^{2^{k + 9}}}}}.

Примітки[ред.ред. код]

  1. B. L. van der Waerden: Beweis einer Baudetschen Vermutung, Nieuw. Arch. Wisk., 15(1927), 212–216.

Джерела[ред.ред. код]

  • Грэхем Р. Начала теории Рамсея: Пер. с англ. — М.: Мир, 1984. — 96 с.

Посилання[ред.ред. код]