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

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

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

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

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

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

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

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

• J. Karhumaki. Ramsey Theory and Related Topics