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

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

Теорема стверджує, що для довільних $k,r\in \mathbb {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 \mathbb {N} ,$ залишається відкритим. Усі відомі доведення теореми ван дер Вардена дають лише верхні межі для визначення цих чисел. Найкращий в цей час результат належить англійському математику Тімоті Гауерсу:

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

Джерела

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

Посилання

• J. Karhumaki. Ramsey Theory and Related Topics