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

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

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

Важнейшие результаты[править | править вики-текст]

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

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

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

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


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

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

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

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

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


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

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

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

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

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

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

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

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

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

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

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

\sum_{n\in S}1/n=1.

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

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

Особенности теории[править | править вики-текст]

Для результатов в рамках теории Рамсея характерны два свойства. Во-первых, они неконструктивны. Доказывается, что некоторая структура существует, но не предлагается никакого способа её построения кроме прямого перебора. Во-вторых, чтобы искомые структуры существовали, требуется, чтобы объекты, их содержащие, состояли из очень большого числа элементов. Зависимость числа элементов объекта от размера структуры, как минимум, экспоненциальная. Рональд Грэхем (англ.) предложил приз US$1000 за доказательство того, что число Ван-дер-Вардена W(2,\;k)<2^{k^2}.[5] Обзор результатов до 1990 г. дан в работе[6].

Примечания[править | править вики-текст]

  1. 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 
  2. van der Waerden, B. L. (1927). «Beweis einer Baudetschen Vermutung». Nieuw. Arch. Wisk. 15: 212–216.
  3. Hales A., Jewett R. Regularity and positional games // Trans. Amer. Math. Soc. 106 (1963), p. 222—229.
  4. 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> 
  5. Graham, Ron (2007). «Some of My Favorite Problems in Ramsey Theory». INTEGERS (The Electronic Journal of Combinatorial Number Theory 7 (2): #A2.
  6. Graham, R.; Rothschild, B. & Spencer, J. H. (1990), «Ramsey Theory» (2nd ed.), New York: John Wiley and Sons, ISBN 0-471-50046-1 .

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