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

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

Классические результаты[править | править вики-текст]

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

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

Теорема Рамсея[править | править вики-текст]

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

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


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

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

Теорема ван дер Вардена[править | править вики-текст]

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

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


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

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

Рональд Грэхем (англ.) предложил приз US$1000 за доказательство того, что число ван дер Вардена .[4]

Теорема Хейлса — Джеветта[править | править вики-текст]

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

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

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

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

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

для всех

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

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

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

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

Эта гипотеза Эрдёша — Грэма доказана Эрнестом Крутом (англ.) в 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. (1927). «Beweis einer Baudetschen Vermutung». Nieuw. Arch. Wisk. 15: 212–216.
  4. Graham, Ron (2007). «Some of My Favorite Problems in Ramsey Theory». INTEGERS (The Electronic Journal of Combinatorial Number Theory 7 (2): #A2.
  5. Hales A., Jewett R. Regularity and positional games // Trans. Amer. Math. Soc. 106 (1963), p. 222—229.
  6. 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> 

Ссылки[править | править вики-текст]