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

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

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

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


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

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


 Сам Рамсей доказал следующую теорему:
 Пусть даны числа a1,a2,,an. Тогда существует такое число R, что, как бы мы ни покрасили рёбра полного графа на R вершинах в n цветов, найдётся либо полный подграф 1-го цвета на a1 вершинах, либо полный подграф 2-го цвета на a2 вершинах, \ldots либо полный подграф n-го цвета на an вершинах.
 Она была также обобщена им на случай гиперграфа.
 Минимальное число R, при котором для заданного набора аргументов a1,a2,,an существует указанная в теореме раскраска, называется числом Рамсея. Вопрос о значениях чисел Рамсея за небольшим исключением остается открытым.

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


 Сходна по формулировке, но отличается доказательством :
 Для всякого набора чисел a1,a2,,an существует такое число W, что, как бы мы ни покрасили первые W натуральных чисел в n цветов, найдётся либо арифметическая прогрессия 1-го цвета длины a1, либо арифметическая прогрессия 2-го цвета длины a2, \ldots, либо арифметическая прогрессия n-го цвета длины an.
 Наименьшее такое число называется .
 Вместо множества натуральных чисел можно рассмотреть решётку Zn, а арифметических прогрессий — фигуры в ней, гомотетичные данной, и утверждение теоремы останется верным (обобщённая теорема ван дер Вардена).
 предложил приз US\1000задоказательствотого,чточисловандерВарденаW(2,  k)<2^k^2$.

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


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

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


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

f(N)=1+2N2 для всех N
  Они же доказали, что во множестве с меньшим числом точек выпуклый N-угольник может не существовать.

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


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


nS1/n=1.

 При этом максимальный элемент, а значит и размер множества S ограничен показательной функцией от r с постоянным основанием. Эта гипотеза Эрдёша — Грэма доказана в 2003 году.

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


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