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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

f ( N ) = 1 + 2 N − 2 {displaystyle f(N)=1+2^{N-2}} для всех N {displaystyle N} .

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

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

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

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

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