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

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

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

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

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

Для заданных чисел $a_{1},\,a_{2},\,\ldots ,\,a_{n}$ существует такое число $R$ , что при любой раскраске рёбер полного графа на $R$ вершинах в $n$ цветов, найдётся либо полный подграф 1-го цвета на $a_{1}$ вершинах, либо полный подграф 2-го цвета на $a_{2}$ вершинах, … либо полный подграф $n$ -го цвета на $a_{n}$ вершинах^[2]. Результат был также обобщён Рамсеем на случай гиперграфа.

Минимальное число $R$ , при котором для заданного набора аргументов $a_{1},\,a_{2},\,\ldots ,\,a_{n}$ существует указанная в теореме раскраска, называется числом Рамсея. Значения чисел Рамсея известны для очень небольшого количества наборов аргументов.

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

Сходна по формулировке, но отличается доказательством теорема ван дер Вардена: для всякого набора чисел $a_{1},\,a_{2},\,\ldots ,\,a_{n}$ существует такое число $W$ , что, при любой раскраске первых $W$ натуральных чисел в $n$ цветов найдётся либо арифметическая прогрессия 1-го цвета длины $a_{1}$ , либо арифметическая прогрессия 2-го цвета длины $a_{2}$ , …, либо арифметическая прогрессия $n$ -го цвета длины $a_{n}$ .^[3].

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

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

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

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

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

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

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

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

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

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

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

Для всякой раскраски целых чисел больших $1$ в $r>0$ цветов существует конечное одноцветное подмножество $S$ целых такое, что:

\sum _{n\in S}1/n=1

.

При этом максимальный элемент, а значит и размер множества $S$ , ограничен показательной функцией от $r$ с постоянным основанием.

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

Примечания

↑ Обзор результатов до 1990 года: Graham, R.; Rothschild, B.; Spencer, J. H. (1990), Ramsey Theory (2nd ed.), New York: John Wiley and Sons, ISBN 0-471-50046-1
↑ Ramsey, F. P. On a problem of formal logic (англ.) // Proc. London Math. Soc. Series 2. — 1930. — Vol. 30. — P. 264—286. — doi:10.1112/plms/s2-30.1.264.
↑ van der Waerden, B. L. Beweis einer Baudetschen Vermutung (нем.) // Nieuw. Arch. Wisk.. — 1927. — Bd. 15. — S. 212—216.
↑ Hales A., Jewett R. Regularity and positional games (англ.) // Trans. Amer. Math. Soc.. — 1963. — Vol. 106. — P. 222—229. — doi:10.2307/1993764. Архивировано 19 января 2022 года.
↑ Erdős, P.; Szekeres, G. (1935), "A combinatorial problem in geometry", Compositio Math, 2: 463—470, Архивировано из оригинала 19 февраля 2019, Дата обращения: 25 февраля 2013.

Литература

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

Ссылки

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

[1] Обзор результатов до 1990 года: Graham, R.; Rothschild, B.; Spencer, J. H. (1990), Ramsey Theory (2nd ed.), New York: John Wiley and Sons, ISBN 0-471-50046-1

[2] Ramsey, F. P. On a problem of formal logic (англ.) // Proc. London Math. Soc. Series 2. — 1930. — Vol. 30. — P. 264—286. — doi:10.1112/plms/s2-30.1.264.

[3] van der Waerden, B. L. Beweis einer Baudetschen Vermutung (нем.) // Nieuw. Arch. Wisk.. — 1927. — Bd. 15. — S. 212—216.

[4] Hales A., Jewett R. Regularity and positional games (англ.) // Trans. Amer. Math. Soc.. — 1963. — Vol. 106. — P. 222—229. — doi:10.2307/1993764. Архивировано 19 января 2022 года.

[5] Erdős, P.; Szekeres, G. (1935), "A combinatorial problem in geometry", Compositio Math, 2: 463—470, Архивировано из оригинала 19 февраля 2019, Дата обращения: 25 февраля 2013.

[1]

[2]

[3]

[4]

[5]