Теория Рамсея
Теория Рамсея — раздел математики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок. Названа в честь Фрэнка Рамсея.
Задачи в теории Рамсея обычно звучат в форме вопроса «сколько элементов должно быть в некотором объекте, чтобы гарантированно выполнялось заданное условие или существовала заданная структура». Простейший пример:
- Доказать, что в любой группе из 6 человек найдутся либо 3 человека, знакомые друг с другом, либо 3 человека, попарно незнакомые друг с другом.
Классические результаты
Предположим, например, что мы знаем, что [math]\displaystyle{ n }[/math] кроликов рассажены в [math]\displaystyle{ m }[/math] клеток. Насколько велико должно быть [math]\displaystyle{ n }[/math], чтобы гарантированно в одной из клеток было как минимум 2 кролика? Согласно принципу Дирихле, если [math]\displaystyle{ n\gt m }[/math], то найдется клетка, в которой будут минимум 2 кролика. Теория Рамсея обобщает этот принцип[1].
Теорема Рамсея
Сам Рамсей доказал следующую теорему:
|
Пусть даны числа [math]\displaystyle{ a_1,\, a_2,\, \ldots,\, a_n }[/math]. Тогда существует такое число [math]\displaystyle{ R }[/math], что, как бы мы ни покрасили рёбра полного графа на [math]\displaystyle{ R }[/math] вершинах в [math]\displaystyle{ n }[/math] цветов, найдётся либо полный подграф 1-го цвета на [math]\displaystyle{ a_1 }[/math] вершинах, либо полный подграф 2-го цвета на [math]\displaystyle{ a_2 }[/math] вершинах, … либо полный подграф [math]\displaystyle{ n }[/math]-го цвета на [math]\displaystyle{ a_n }[/math] вершинах.[2] |
Она была также обобщена им на случай гиперграфа.
Минимальное число [math]\displaystyle{ R }[/math], при котором для заданного набора аргументов [math]\displaystyle{ a_1,\, a_2,\, \ldots,\, a_n }[/math] существует указанная в теореме раскраска, называется числом Рамсея. Значения чисел Рамсея известны для очень небольшого количества наборов аргументов.
Теорема ван дер Вардена
Сходна по формулировке, но отличается доказательством теорема ван дер Вардена.
|
Для всякого набора чисел [math]\displaystyle{ a_1,\, a_2,\, \ldots,\, a_n }[/math] существует такое число [math]\displaystyle{ W }[/math], что, как бы мы ни покрасили первые [math]\displaystyle{ W }[/math] натуральных чисел в [math]\displaystyle{ n }[/math] цветов, найдётся либо арифметическая прогрессия 1-го цвета длины [math]\displaystyle{ a_1 }[/math], либо арифметическая прогрессия 2-го цвета длины [math]\displaystyle{ a_2 }[/math], …, либо арифметическая прогрессия [math]\displaystyle{ n }[/math]-го цвета длины [math]\displaystyle{ a_n }[/math].[3] |
Наименьшее такое число называется числом ван дер Вардена.
Вместо множества натуральных чисел можно рассмотреть решётку [math]\displaystyle{ \mathbb Z^n }[/math], а арифметических прогрессий — фигуры в ней, гомотетичные данной, и утверждение теоремы останется верным (обобщённая теорема ван дер Вардена).
Теорема Хейлса — Джеветта
|
Для любых чисел [math]\displaystyle{ n }[/math] и [math]\displaystyle{ c }[/math] можно найти число [math]\displaystyle{ H }[/math] такое, что если ячейки [math]\displaystyle{ H }[/math]-мерного куба со стороной длины [math]\displaystyle{ n }[/math] раскрашены в [math]\displaystyle{ c }[/math] цветов, то существует хотя бы одна линия (линией считаются строки, столбцы, некоторые диагонали) из [math]\displaystyle{ n }[/math] одноцветных ячеек.[4] |
Из этой теоремы следует, что при игре в многомерные крестики-нолики при любой длине строки и любом числе игроков можно найти такое число измерений, что ничья будет невозможна.
Гипотеза Эрдёша — Секереша о выпуклых многоугольниках
|
Для любого натурального [math]\displaystyle{ N }[/math] всякое достаточно большое множество точек в общем положении на плоскости имеет подмножество [math]\displaystyle{ N }[/math] точек, которые являются вершинами выпуклого многоугольника.[5] |
Согласно гипотезе Эрдёша и Секереша о выпуклых многоугольниках, число точек в общем положении, в которых обязательно существует выпуклый [math]\displaystyle{ N }[/math]-угольник задаётся формулой
- [math]\displaystyle{ f(N) = 1 + 2^{N-2} }[/math]
для всех [math]\displaystyle{ N }[/math]. Они же доказали, что во множестве с меньшим числом точек выпуклый [math]\displaystyle{ N }[/math]-угольник может не существовать.
Теорема Крута об одноцветной египетской дроби
|
Для всякой раскраски целых чисел больших [math]\displaystyle{ 1 }[/math] в [math]\displaystyle{ r \gt 0 }[/math] цветов существует конечное одноцветное подмножество [math]\displaystyle{ S }[/math] целых такое, что
При этом максимальный элемент, а значит и размер множества [math]\displaystyle{ S }[/math], ограничен показательной функцией от [math]\displaystyle{ r }[/math] с постоянным основанием. |
Эта гипотеза Эрдёша — Грэма доказана Эрнестом Крутом[англ.] в 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, <http://www.numdam.org/item?id=CM_1935__2__463_0> Архивная копия от 19 февраля 2019 на Wayback Machine.
Литература
- Мартин Гарднер. Глава 17. Теория Рамсея // От мозаик Пенроуза к надёжным шифрам = Penrose Tiles to Trapdoor Ciphers / пер. с англ. Ю. А. Данилова. — М.: Мир, 1993. — С. 288—308. — 416 с. — 10 000 экз. — ISBN 5-03-001991-X.