Открыть главное меню

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

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

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

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

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

Обзор результатов до 1990 г. дан в работе[1].

Теорема РамсеяПравить

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

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

Пусть даны числа  . Тогда существует такое число  , что, как бы мы ни покрасили рёбра полного графа на   вершинах в   цветов, найдётся либо полный подграф 1-го цвета на   вершинах, либо полный подграф 2-го цвета на   вершинах, … либо полный подграф  -го цвета на   вершинах.[2]

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

Минимальное число  , при котором для заданного набора аргументов   существует указанная в теореме раскраска, называется числом Рамсея. Вопрос о значениях чисел Рамсея за небольшим исключением остается открытым.

Теорема ван дер ВарденаПравить

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

Для всякого набора чисел   существует такое число  , что, как бы мы ни покрасили первые   натуральных чисел в   цветов, найдётся либо арифметическая прогрессия 1-го цвета длины  , либо арифметическая прогрессия 2-го цвета длины  , …, либо арифметическая прогрессия  -го цвета длины  .[3]

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

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

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

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

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

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

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

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

  для всех  

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

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

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

 

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

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

Особенности теорииПравить

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

ПримечанияПравить

  1. 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. (1930), "On a problem of formal logic", Proc. London Math. Soc. Series 2 Т. 30: 264–286, DOI 10.1112/plms/s2-30.1.264 
  3. van der Waerden, B. L. Beweis einer Baudetschen Vermutung (неопр.) // Nieuw. Arch. Wisk.. — 1927. — Т. 15. — С. 212—216.
  4. Hales A., Jewett R. Regularity and positional games // Trans. Amer. Math. Soc. 106 (1963), p. 222—229.
  5. 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> 

ЛитератураПравить

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

СсылкиПравить