Теория Рамсея

Теория Рамсея — раздел математики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок. Названа в честь Фрэнка Рамсея.

Задачи в теории Рамсея обычно звучат в форме вопроса «сколько элементов должно быть в некотором объекте, чтобы гарантированно выполнялось заданное условие или существовала заданная структура». Простейший пример:

• Доказать, что в любой группе из 6 человек найдутся либо 3 человека, знакомые друг с другом, либо 3 человека, попарно незнакомые друг с другом.

Классические результаты

Предположим, например, что мы знаем, что $n$ кроликов рассажены в $m$ клеток. Насколько велико должно быть $n$, чтобы гарантированно в одной из клеток было как минимум 2 кролика? Согласно принципу Дирихле, если $n>m$, то найдется клетка, в которой будут минимум 2 кролика. Теория Рамсея обобщает этот принцип.

Теорема Рамсея

Основная статья: Теорема Рамсея

Сам Рамсей доказал следующую теорему:

Пусть даны числа $a_1,a_2,\dots ,a_n$. Тогда существует такое число $R$, что, как бы мы ни покрасили рёбра полного графа на $R$ вершинах в $n$ цветов, найдётся либо полный подграф 1-го цвета на $a_1$ вершинах, либо полный подграф 2-го цвета на $a_2$ вершинах, … либо полный подграф $n$-го цвета на $a_n$ вершинах.

Она была также обобщена им на случай гиперграфа.

Минимальное число $R$, при котором для заданного набора аргументов $a_1,a_2,\dots ,a_n$ существует указанная в теореме раскраска, называется числом Рамсея. Значения чисел Рамсея известны для очень небольшого количества наборов аргументов.

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

Основная статья: Теорема ван дер Вардена

Сходна по формулировке, но отличается доказательством теорема ван дер Вардена.

Для всякого набора чисел $a_1,a_2,\dots ,a_n$ существует такое число $W$, что, как бы мы ни покрасили первые $W$ натуральных чисел в $n$ цветов, найдётся либо арифметическая прогрессия 1-го цвета длины $a_1$, либо арифметическая прогрессия 2-го цвета длины $a_2$, …, либо арифметическая прогрессия $n$-го цвета длины $a_n$.

Наименьшее такое число называется числом ван дер Вардена.

Вместо множества натуральных чисел можно рассмотреть решётку ${\mathbb{\mathbb{Z}}}^n$, а арифметических прогрессий — фигуры в ней, гомотетичные данной, и утверждение теоремы останется верным (обобщённая теорема ван дер Вардена).

Теорема Хейлса — Джеветта

Для любых чисел $n$ и $c$ можно найти число $H$ такое, что если ячейки $H$-мерного куба со стороной длины $n$ раскрашены в $c$ цветов, то существует хотя бы одна линия (линией считаются строки, столбцы, некоторые диагонали) из $n$ одноцветных ячеек.

Из этой теоремы следует, что при игре в многомерные крестики-нолики при любой длине строки и любом числе игроков можно найти такое число измерений, что ничья будет невозможна.

Гипотеза Эрдёша — Секереша о выпуклых многоугольниках

Основная статья: Задача со счастливым концом

Для любого натурального $N$ всякое достаточно большое множество точек в общем положении на плоскости имеет подмножество $N$ точек, которые являются вершинами выпуклого многоугольника.

Согласно гипотезе Эрдёша и Секереша о выпуклых многоугольниках, число точек в общем положении, в которых обязательно существует выпуклый $N$-угольник задаётся формулой

$f(N)=1+2^{N-2}$

для всех $N$. Они же доказали, что во множестве с меньшим числом точек выпуклый $N$-угольник может не существовать.

Теорема Крута об одноцветной египетской дроби

Для всякой раскраски целых чисел больших $1$ в $r>0$ цветов существует конечное одноцветное подмножество $S$ целых такое, что $\sum _{n\in S}1/n=1.$ При этом максимальный элемент, а значит и размер множества $S$, ограничен показательной функцией от $r$ с постоянным основанием.

Эта гипотеза Эрдёша — Грэма доказана Эрнестом Крутом в 2003 году.

Особенности теории

Для результатов в рамках теории Рамсея характерны два свойства. Во-первых, они неконструктивны. Доказывается, что некоторая структура существует, но не предлагается никакого способа её построения кроме прямого перебора. Во-вторых, чтобы искомые структуры существовали, требуется, чтобы объекты, их содержащие, состояли из очень большого числа элементов. Зависимость числа элементов объекта от размера структуры обычно, как минимум, экспоненциальная.

Литература

• Мартин Гарднер. Глава 17. Теория Рамсея // От мозаик Пенроуза к надёжным шифрам = Penrose Tiles to Trapdoor Ciphers / пер. с англ. Ю. А. Данилова. — М.: Мир, 1993. — С. 288—308. — 416 с. — 10 000 экз. — ISBN 5-03-001991-X.

Ссылки

• Теория Рамсея