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

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

  • Доказать, что в любой группе из 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 году.

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


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