19-08-2023
Теория Рамсея, названная в честь Франка Рамсея — раздел математики, изучающий условия, при которых обязан появиться порядок. Задачи в теории Рамсея обычно звучат в форме вопроса «сколько элементов должно быть в некоторой структуре, чтобы гарантированно выполнялось данное условие?».
Содержание |
Предположим, например, что мы знаем, что n кроликов рассажены в m клеток. Насколько велико должно быть n, чтобы гарантированно в одной из клеток было как минимум 2 кролика? Согласно принципу Дирихле, если n > m, то найдется клетка, в которой будут минимум 2 кролика. Теория Рамсея обобщает этот принцип.
Сам Рамсей доказал следующую теорему:
|
Пусть даны числа . Тогда существует такое число R, что, как бы мы ни покрасили рёбра полного графа на R вершинах в n цветов, найдётся либо полный подграф 1-го цвета на вершинах, либо полный подграф 2-го цвета на вершинах, … либо полный подграф n-го цвета на вершинах. |
Она была также обобщена им на случай гиперграфа.
Сходна по формулировке, но отличается доказательством теорема Ван-дер-Вардена (англ.):
|
Для всякого набора чисел существует такое число W, что, как бы мы не покрасили первые W натуральных чисел в n цветов, найдётся либо арифметическая прогрессия 1-го цвета длины , либо арифметическая прогрессия 2-го цвета длины , …, либо арифметическая прогрессия n-го цвета длины . |
Вместо множества натуральных чисел можно рассмотреть решётку , а арифметических прогрессий — фигуры в ней, гомотетичные данной, и утверждение теоремы останется верным (обобщённая теорема Ван-дер-Вардена).
| Это заготовка статьи по математике. Вы можете помочь проекту, исправив и дополнив её. |
Теория Рамсея.