Викиконспекты - Вклад участника [ru]

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

2018-12-01T05:44:08Z

188.170.72.247: /* Индуцированная теорема Рамсея */

'''Теория Рамсея''' — раздел математики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок.
==Числа Рамсея==
{{Определение
|id=def1
|definition='''Клика''' (англ. ''clique'') в неориентированном графе <tex>G = (V, E)</tex> {{---}} подмножество вершин <tex>C \subseteq V</tex>, такое что для любых двух вершин в <tex>C</tex> существует ребро, их соединяющее.}}
{{Определение
|id=def2
|definition='''Число Рамсея''' <tex>r(n, m)</tex> (англ. ''Ramsey's number'') {{---}} наименьшее из таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске ребер полного графа на <tex>x</tex> вершинах в два цвета найдется клика на <tex>n</tex> вершинах с ребрами цвета <tex>1</tex> или клика на <tex>m</tex> вершинах с ребрами цвета <tex>2</tex>. }}

[[Файл:RamseyTheoryK5.png|200px|thumb|upright|Раскраска <tex>K_5</tex> без одноцветных треугольников]]
Часто определение для чисел Рамсея дается через задачу "о друзьях и незнакомцах"<ref>[https://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers| Theorem on friends and strangers]</ref>. Пусть на вечеринке каждые два человека могут быть либо друзьями, либо незнакомцами, в общем виде задачи требуется найти, какое минимальное количество людей нужно взять, чтобы хотя бы <tex>n</tex> человек были попарно знакомы, или хотя бы <tex>m</tex> человек были попарно незнакомы. Если мы переформулируем данную задачу в терминах графов, то как раз получим определение числа Рамсея <tex>r(n, m)</tex>, представленное ранее.

Чтобы получить лучшее представление природы чисел Рамсея, приведем пример. Докажем, что <tex>r(3,3) = 6</tex>. Представим, что ребра <tex>K_6</tex> раскрашены в два цвета: красный и синий. Возьмем вершину <tex>v</tex>. Данной вершине, как и всем другим, инцидентны <tex>5</tex> рёбер, тогда, согласно принципу Дирихле, хотя бы три из них одного цвета. Для определенности положим, что хотя бы <tex>3</tex> ребра, соединяющие вершину <tex>v</tex> с вершинами <tex>r</tex>, <tex>s</tex>, <tex>t</tex>, синие. Если хотя бы одно из ребер <tex>rs</tex>, <tex>rt</tex>, <tex>st</tex> синее, то в графе есть синий треугольник (полный граф на трёх вершинах), иначе, если они все красные, есть красный треугольник. Таким образом, <tex>r(3,3) \leqslant 6 </tex>.
Чтобы доказать, что <tex>r(3,3) = 6 </tex>, предъявим такую раскраску графа <tex>K_5</tex>, где нет клики на трех вершинах ни синего, ни красного цвета. Такая раскраска представлена на рисунке справа.

===Теорема Рамсея. Оценки сверху===
{{Теорема|id=ter1|about=1, Теорема Рамсея
|statement= Для любых <tex>n,m \in \mathbb N</tex> существует число <tex>r(n,m)</tex>, при этом <tex>r(n,m) \leqslant r(n,m-1)+r(n-1,m)</tex>, а также если числа <tex>r(n,m-1)</tex> и <tex>r(n-1,m)</tex> четные, то неравенство принимает вид <tex>r(n,m) \leqslant r(n,m-1)+r(n-1,m) - 1</tex> .
|proof=

<tex>1)</tex> Докажем с помощью метода математической индукции по <tex>n+m</tex>.

'''База:''' <tex>r(n,\;1) = r(1,\;n) = 1</tex>, так как граф, состоящий из одной вершины, можно считать полным графом любого цвета.

'''Индукционный переход:''' Пусть <tex>n>1</tex> и <tex>m>1</tex>. Рассмотрим полный чёрно-белый граф из <tex>r(n-1,\;m)+r(n,\;m-1)</tex> вершин. Возьмём произвольную вершину <tex>v</tex> и обозначим через <tex>M</tex> и <tex>N</tex> множества, инцидентные <tex>v</tex> в чёрном и белом подграфе соответственно. Так как в графе <tex>r(n-1,\;m)+r(n,\;m-1)=|M|+|N|+1 </tex> вершин, согласно принципу Дирихле, либо <tex>|M|\geqslant r(n-1,\;m)</tex>, либо <tex>|N|\geqslant r(n,\;m-1)</tex>. Пусть <tex>|M|\geqslant r(n-1,\;m)</tex>. Тогда либо в <tex>M</tex> существует белый <tex>K_m</tex>, что доказывает теорему, либо в <tex>M</tex> есть чёрный <tex>K_{n-1}</tex>, который вместе с <tex>v</tex> образует чёрный <tex>K_n</tex>, в этом случае теорема также доказана. Случай <tex>|N|\geqslant r(n,\;m-1)</tex> рассматривается аналогично.

<tex>2)</tex> Предположим, <tex>p=r(n-1,\;m)</tex> и <tex>q=r(n,\;m-1)</tex> оба чётны. Положим <tex>s=p+q-1</tex> и рассмотрим чёрно-белый граф из <tex>s</tex> вершин. Если <tex>d_i</tex> степень <tex>i</tex>-й вершины в чёрном подграфе, то, согласно [[Лемма о рукопожатиях|лемме о рукопожатиях]], <tex>\sum_{i=1}^s d_i</tex> — чётно. Поскольку <tex>s</tex> нечётно, должно существовать чётное <tex>d_i</tex>. Не умаляя общности, положим, что <tex>d_1</tex> чётно. Обозначим через <tex>M</tex> и <tex>N</tex> вершины, ,инцидентные вершине <tex>1</tex> в чёрном и белом подграфах соответственно. Тогда <tex>|M|=d_1</tex> и <tex>|N|=s-1-d_1</tex> оба чётны. Согласно принципу Дирихле, либо <tex>|M|\geqslant p-1</tex>, либо <tex>N\geqslant q</tex>. Так как <tex>|M|</tex> чётно, а <tex>p-1</tex> нечётно, первое неравенство можно усилить, так что либо <tex>|M|\geqslant p</tex>, либо <tex>|N|\geqslant q</tex>.

Предположим <tex>|M|\geqslant p=r(n-1,\;m)</tex>. Тогда либо подграф, порождённый множеством <tex>M</tex>, содержит белый <tex>K_m</tex> и доказательство завершено, либо он содержит чёрный <tex>K_{n-1}</tex>, который вместе с вершиной <tex>1</tex> образует чёрный <tex>K_n</tex>. Случай <tex>|N|\geqslant q=r(n,\;m-1)</tex> рассматривается аналогично.
}}
{{Утверждение|id=u1|about=1|statement=Для натуральных чисел <tex>m,n</tex> выполняется равенство <tex>r(n,m) \leqslant C_{n+m-2}^{n-1}</tex>
|proof=
Очевидно, <tex>C^{n-1}_{n+m-2}=1</tex> при <tex>n=1</tex> или <tex>m=1</tex>, как и соответствующие числа Рамсея. Индукцией по <tex>n</tex> и <tex>m</tex> при <tex>n,m \geqslant 2</tex> получаем
<tex>r(n,m) \leqslant r(n,m-1)+r(n-1,m) \leqslant C^{n-1}_{n+m-3}+C^{n-2}_{n+m-3}=C^{n-1}_{n+m-2}</tex>
}}

===Оценки снизу===

{{Теорема|id=ter2|about=2
|statement=Для любого натурального числа <tex>k \geqslant 2</tex> выполняется неравенство <tex>r(k,k) \geqslant k^{k/2}</tex>
|proof=
Так как <tex>r(2,2)=2</tex>, достаточно рассмотреть случай <tex>k \geqslant 3</tex>.
Зафиксируем множество различных помеченных вершин <tex>v_i,\ldots,v_n</tex>. Пусть <tex>g(n,k)</tex> {{---}} доля среди всех графов на вершинах <tex>v_i,\ldots,v_n</tex> тех графов, что содержат клику на <tex>k</tex> вершинах. Всего графов на наших вершинах, очевидно <tex>2^{C^2_n}</tex> (каждое из возможных рёбер <tex>C^2_n</tex> можно провести или не провести).

Посчитаем графы с кликой на <tex>k</tex> вершинах следующим образом: существует <tex>C^k_n</tex> способов выбрать <tex>k</tex> вершин для клики в нашем множестве, после чего все рёбра между ними будем считать проведенными, а остальные ребра выбираются произвольно. Таким образом, каждый граф с кликой на <tex>k</tex> вершинах будет посчитан, причём некоторые даже более одного раза. Количестве графов с кликой оказывается не более, чем <tex>C^k_n\cdot 2^{C^2_n-C^2_k}</tex>. Следовательно,

<tex>g(n,k) \leqslant \dfrac{C^k_n}{2^{C^2_k}}<\dfrac{n^k}{k!\cdot 2^{C^2_k}}</tex> <tex>(*)</tex>

Подставив <tex>n<2^{k/2}</tex> в неравенство <tex>(*)</tex> мы получаем

<tex>g(n,k)<\dfrac{2^{k^2/2}\cdot 2^{-C^2_k}}{k!}=\dfrac{2^{k/2}}{k!}<\dfrac12</tex> при <tex>k \geqslant 3</tex>

Предположим, что <tex>r(k,k)=n<2^{k/2}</tex> и разобьём все графы на <tex>n</tex> вершинах на пары <tex>G, \overline G</tex> (граф и его дополнение) Так как <tex>g(n,k)<\dfrac12</tex>, то существует пара, в которой ни <tex>G</tex>, ни <tex>\overline G</tex> не содержат клики на <tex>k</tex> вершинах. Рассмотрим раскраску рёбер <tex>K_n</tex> в два цвета, в которой ребра цвета <tex>1</tex> образуют граф <tex>G</tex>. В такой раскраске нет клики на <tex>k</tex> вершинах ни цвета <tex>1</tex>, ни цвета <tex>1</tex>, получили противоречи противоречие. Значит <tex>n</tex> было выбрано неверно. Из этого следует <tex>r(k,k) \geqslant 2^{k/2}</tex>.
}}

===Свойства чисел Рамсея===
Следующими свойствами удобно пользоваться при подсчете значений чисел Рамсея <tex>r(n,m)</tex> на практике.
* <tex>r(n,m) = r(m,n)</tex>
* <tex>r(1,m) = 1</tex>
* <tex>r(2,m) = m</tex>

===Значения чисел Рамсея===
Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, их известно довольно мало. Далее приведена таблица Станислава Радзишевского <ref>[http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1| Small Ramsey Numbers by Stanisław Radziszowski]</ref>, в которой присутствуют практически все известные числа Рамсея или же промежутки, в которых они находятся.
<center>
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
|+
!colspan="11"|Числа Рамсея
|-align="center"
! width="6%" |<tex>n,\ m</tex>
! width="6%" |<tex>1 </tex>
! width="6%" |<tex>2 </tex>
! width="6%" |<tex>3 </tex>
! width="6%" |<tex>4 </tex>
! width="6%" |<tex>5 </tex>
! width="6%" |<tex>6 </tex>
! width="6%" |<tex>7 </tex>
! width="6%" |<tex>8 </tex>
! width="6%" |<tex>9 </tex>
! width="6%" |<tex>10</tex>
|-align="center"
! <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
|-align="center"
! <tex>2 </tex>
| <tex>1 </tex>
| <tex>2 </tex>
| <tex>3 </tex>
| <tex>4 </tex>
| <tex>5 </tex>
| <tex>6 </tex>
| <tex>7 </tex>
| <tex>8 </tex>
| <tex>9 </tex>
| <tex>10</tex>
|-align="center"
! <tex>3</tex>
| <tex>1</tex>
| <tex>3</tex>
| <tex>6</tex>
| <tex>9</tex>
| <tex>14</tex>
| <tex>18</tex>
| <tex>23</tex>
| <tex>28</tex>
| <tex>36</tex>
| <tex>[40, 42]</tex>
|-align="center"
! <tex>4</tex>
| <tex>1</tex>
| <tex>4</tex>
| <tex>9</tex>
| <tex>18</tex>
| <tex>25</tex>
| <tex>[36, 41]</tex>
| <tex>[49, 61]</tex>
| <tex>[59, 84]</tex>
| <tex>[73, 115]</tex>
| <tex>[92, 149]</tex>
|-align="center"
! <tex>5</tex>
| <tex>1</tex>
| <tex>5</tex>
| <tex>14</tex>
| <tex>25</tex>
| <tex>[43, 48]</tex>
| <tex>[58, 87]</tex>
| <tex>[80, 143]</tex>
| <tex>[101, 216]</tex>
| <tex>[133, 316]</tex>
| <tex>[149, 442]</tex>
|-align="center"
! <tex>6</tex>
| <tex>1</tex>
| <tex>6</tex>
| <tex>18</tex>
| <tex>[36, 41]</tex>
| <tex>[58, 87]</tex>
| <tex>[102, 165]</tex>
| <tex>[115, 298]</tex>
| <tex>[134, 495]</tex>
| <tex>[183, 780]</tex>
| <tex>[204, 1171]</tex>
|-align="center"
! <tex>7</tex>
| <tex>1</tex>
| <tex>7</tex>
| <tex>23</tex>
| <tex>[49, 61]</tex>
| <tex>[80, 143]</tex>
| <tex>[115, 298]</tex>
| <tex>[205, 540]</tex>
| <tex>[217, 1031]</tex>
| <tex>[252, 1713]</tex>
| <tex>[292, 2826]</tex>
|-align="center"
! <tex>8</tex>
| <tex>1</tex>
| <tex>8</tex>
| <tex>28</tex>
| <tex>[56, 84]</tex>
| <tex>[101, 216]</tex>
| <tex>[127, 495]</tex>
| <tex>[217, 1031]</tex>
| <tex>[282, 1870]</tex>
| <tex>[329, 3583]</tex>
| <tex>[343, 6090]</tex>
|-align="center"
! <tex>9</tex>
| <tex>1</tex>
| <tex>9</tex>
| <tex>36</tex>
| <tex>[73, 115]</tex>
| <tex>[133, 316]</tex>
| <tex>[183, 780]</tex>
| <tex>[252, 1713]</tex>
| <tex>[329, 3583]</tex>
| <tex>[565, 6588]</tex>
| <tex>[580, 12677]</tex>
|-align="center"
! <tex>10</tex>
| <tex>1</tex>
| <tex>10</tex>
| <tex>[40, 42]</tex>
| <tex>[92, 149]</tex>
| <tex>[149, 442]</tex>
| <tex>[179, 1171]</tex>
| <tex>[289, 2826]</tex>
| <tex>[343, 6090]</tex>
| <tex>[581, 12677]</tex>
| <tex>[798, 23556]</tex>
|}
</center>

===Числа Рамсея для раскрасок в несколько цветов===
Теперь обобщим числа Рамсея на произвольное количество цветов.
{{Определение
|id=def4
|definition=
'''Число Рамсея''' <tex>r(n_1,\ldots,n_k)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в <tex>k</tex> цветов для некоторого <tex>i \in [1 \ldots k]</tex> обязательно найдётся клика на <tex>n_i</tex> вершинах с рёбрами цвета <tex>i</tex>. <tex>k,n_1,\ldots,n_k \in \mathbb N</tex>
}}

{{Теорема
|id=ter3|about=3,Теорема Рамсея для нескольких цветов
|statement=<tex>\forall k, n_1, \ldots n_k \in \mathbb N </tex> существует соответственное число Рамсея <tex>r(n_1,\ldots,n_k)</tex>, при этом <tex>r(n_1,\ldots,n_k)\leqslant r(n_1,\ldots, n_{k-2}, r(n_{k-1},\;n_k)).</tex>
|proof=
Возьмем граф из <tex>r(n_1,\ldots, n_{k-2}, r(n_{k-1}, n_k))</tex> вершин и окрасим его рёбра в <tex>k</tex> цветов. Пока что будем считать цвета <tex>k-1</tex> и <tex>k</tex> одним цветом. Тогда граф будет <tex>(k-1)</tex>-цветным. Согласно определению числа Рамсея <tex>r(n_1,\ldots,n_{k-2},r(n_{k-1},n_k))</tex>, такой граф либо содержит <tex>K_{n_i}</tex> для некоторого цвета <tex>i</tex>, такого что <tex>1\leqslant i\leqslant k-2</tex> либо <tex>K_{r(k, n_{k-1},n_k)}</tex>, окрашенный общим цветом <tex>k-1</tex> и <tex>k</tex>. В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный <tex>r(n_{k-1},n_k)</tex> — вершинный граф содержит либо <tex>K_{n_{k-1}}</tex> цвета <tex>k-1</tex>, либо <tex>K_{n_k}</tex> цвета <tex>k</tex>. Таким образом любое число Рамсея для раскраски в <tex>k</tex> цветов ограничено некоторым числом Рамсея для меньшего количества цветов, следовательно, <tex>r(n_1,\ldots,n_k)</tex> существует для любых <tex> k, n_1, \ldots n_k, \in \mathbb N </tex>, и теорема доказана.
}}

==Числа Рамсея больших размерностей==
{{Определение
|id=def5
|definition=
Пусть <tex>m,k,n_1,\ldots ,n_k \in \mathbb N</tex>, причём <tex>n_1,\ldots ,n_k \geqslant m</tex>. '''Число Рамсея''' <tex>r_m(n_1,\ldots ,n_k)</tex> — наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске <tex>m</tex>-элементных подмножеств <tex>x</tex>-элементного множества <tex>M</tex> в <tex>k</tex> цветов для некоторого <tex>i \in [1\ldots k]</tex> обязательно найдётся такое множество <tex>W_i</tex>, что <tex>|W_i|=n_i</tex> и все <tex>m</tex>-элементные подмножества множества <tex>W_i</tex> имеют цвет <tex>i</tex>. Число <tex>m</tex> называют '''размерностью''' числа Рамсея <tex>r_m(n_1,\ldots ,n_k)</tex>.
}}
Заметим, что числа Рамсея размерности <tex>2</tex> — это определённые ранее числа Рамсея для клик.

{{Определение
|id=def7|definition=
Для каждого множества <tex>M</tex> через <tex>M^k</tex> мы будем обозначать множество всех <tex>k</tex>-элементных подмножеств <tex>M</tex>.
}}
{{Теорема
|id=ter4|about=4, Теорема Рамсея для чисел больших размерностей
|statement=Пусть <tex>m,k,n_1,\ldots,n_k</tex> {{---}} натуральные числа, причем <tex>k \geqslant 2</tex>, а <tex>n_1,\ldots ,n_k \geqslant m</tex>. Тогда существует число Рамсея <tex>r_m(n_1,\ldots n_k)</tex>.
|proof=
<tex>1)</tex> Мы будем доказывать теорему по индукции. Начнем со случая <tex>k=2</tex>. Приступая к доказательству для числа <tex>r_m(n_1,n_2)</tex> мы будем считать доказанным утверждение теоремы для чисел Рамсея всех меньших размерностей и чисел Рамсея размерности <tex>m</tex> с меньшей суммой <tex>n_1+n_2</tex>. В качестве базы будем использовать случай чисел Рамсея размерности <tex>2</tex> разобранный выше. Итак, мы докажем, что <tex>r_m(n_1,n_2)-1 \leqslant p=r_{m-1}(r_m(n_1-1,n_2),r_m(n_1,n_2-1))</tex>.

Рассмотрим <tex>(p+1)</tex>-элементное множество <tex>M</tex> и выделим в нём элемент <tex>a</tex>. Пусть <tex>M_0=M \setminus \{ a \}</tex>. Пусть <tex>\rho:M^m\rightarrow \{1, 2 \} </tex> — произвольная раскраска в два цвета. Рассмотрим раскраску <tex>\rho': M_0^{m-1} \rightarrow \{1, 2\} </tex> , определённую следующим образом: для каждого множества <tex>B \in M_0^{m-1}</tex> пусть <tex>\rho'(B) = \rho(B \cup \{ a \})</tex>.
Так как <tex>|M_0|=p</tex>, либо существует <tex>r_m(n_1 — 1,n_2)</tex>-элементное подмножество <tex>M_i \subset M_0</tex>, <tex>\rho'(B)=1</tex> на всех <tex>B \in M_1^{m-1}</tex>, либо существует <tex>r_m(n_1,n_2-1)</tex>-элементное подмножество <tex>M_2 \subset M_0</tex>, <tex>\rho'(B)=2</tex> на всех <tex>B \in M_2^{m-1}</tex>. Случаи аналогичны, рассмотрим первый случай и множество <tex>M_1</tex>.
По индукционному предположен из <tex>|M_1|=r_m(n_1-1,n_2)</tex> следует, что либо существует <tex>n_1-1</tex>-элементное подмножество <tex>N_1 \subset M_1</tex>, <tex>\rho(A)=1</tex> на всех <tex>A \in N^m_1</tex>, либо существует <tex>n_2</tex>-элементное подмножество <tex>N_2 \subset M_1</tex>, <tex>\rho(A)=2</tex> на всех <tex>A \in N_2^m</tex>. Во втором случае искомое подмножество найдено (это <tex>N_2</tex>), рассмотрим первый случай и множество <tex>N=N_1 \cup \{a\}</tex>. Пусть <tex>A \in N^m</tex>. Если <tex>A \not\ni a</tex>, то <tex>A \in N_1^m</tex> и следовательно <tex>\rho(A)=1</tex>. Если же <tex>A \ni a</tex>, то множество <tex>A \setminus \{a\} \in N_1^{m-1} \subset M_1^{m-1}</tex> и поэтому <tex>\rho(A)=\rho'(A \setminus \{a \})=1</tex>. Учитывая, что <tex>|N|=n_1</tex>, мы нашли искомое подмножество и в этом случае.

<tex>2)</tex> При <tex>k>2</tex> будем вести индукцию по <tex>k</tex> с доказанной выше базой <tex>k=2</tex>. При <tex>k>2</tex> мы докажем неравенство.
<tex>r_m(n_1,\ldots ,n_k) \leqslant q=r_m(r_m(n_1,\ldots ,n_{k-1}),n_k)</tex>

Для этого мы рассмотрим множество <tex>M</tex> на <tex>q</tex> вершинах и произвольную раскраску <tex>\rho:M^m \rightarrow [1 \ldots k]</tex> в <tex>k</tex>цветов. Рассмотрим раскраску <tex>\rho':M^m \rightarrow \{0,k\}</tex>, в которой цвета <tex>1,\ldots,k-1</tex> раскраски <tex>\rho</tex> склеены в цвет <tex>0</tex>. Тогда существует либо такое подмножество <tex>M_0 \subset M</tex>, что <tex>|M_0|=r_m(n_1,\ldots ,n_{k-1})</tex> и <tex>\rho'(A)=0</tex> на всех <tex>A \in M_0^m</tex>, либо существует такое <tex>n_k</tex>-элементное подмножество <tex>M_k \subset M</tex>, что <tex>\rho(A)=\rho'(A)=k</tex> на всех <tex>A \in M^m_k</tex>. Во втором случае <tex>M_k</tex> — искомое подмножество, а в первом случае заметим, что на любом подмножестве <tex>A \in M_0^m</tex> из <tex>\rho'(A)=0</tex> следует <tex>\rho(A) \in [1 \ldots k-1]</tex>. Исходя из размера множества <tex>M_0</tex> по индукционному предположению получаем, что найдется искомое подмножество множества <tex>M</tex> для одного из цветов <tex>1,\ldots ,k-1</tex>, таким образом неравенство доказано, а из этого следует и существование числа Рамсея <tex>r_m(n_1,\ldots ,n_k)</tex>.
}}

==Числа Рамсея для произвольных графов==
Еще один способ обобщения классической теории Рамсея — замена клик на произвольные графы-шаблоны.
{{Определение
|id=def8
|definition=
Пусть <tex>H_1,H_2</tex> — графы. Число Рамсея <tex>r(H_1,H_2)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в два цвета обязательно найдется подграф, изоморфный <tex>H_1</tex> с рёбрами цвета <tex>1</tex> или подграф изоморфный <tex>H_2</tex> с рёбрами цвета <tex>2</tex>.
}}
Из результатов классической теории Рамсея становится понятно, что числа <tex>r(H_1,H_2)</tex> существуют.

{{Лемма
|id=l1|about=1|statement=Пусть <tex>m>1</tex>, а граф <tex>H</tex> таков, что <tex>v(H) \geqslant (m-1)(n-1)+1</tex> и <tex>\alpha(H) \leqslant m-1</tex>. Тогда граф <tex>H</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах.
|proof=
Зафиксируем <tex>m</tex> и проведем индукцию по <tex>n</tex>.

'''База:''' для <tex>n=1</tex> очевидно.

'''Индукционный переход:''' Пусть верно для <tex>n-1</tex>, докажем для <tex>n</tex>. Рассмотрим произвольное дерево <tex>T_n</tex> на <tex>n</tex> вершинах, пусть дерево <tex>T_{n-1}</tex> получено из <tex>T_n</tex> удалением висячей вершины. Пусть <tex>U</tex> — максимальное независимое множестве вершин графа <tex>H</tex>. Тогда <tex>|U|=\alpha(H) \leqslant m-1</tex>, следовательно <tex>v(H-U) \geqslant (m-1)(n-2)+1</tex> и очевидно <tex>\alpha(H-U) \leqslant m-1</tex>.
По индукционному предположению, граф <tex>H-U</tex> содержит в качестве подграфа дерево <tex>T_{n-1}</tex>. Пусть <tex>a</tex> — вершина этого дерева, присоединив к которой висячую вершину мы получим дерево <tex>T_n</tex>. Заметим, что множество <tex>U \cup</tex> <tex>\{a\}</tex> не является независимым ввиду максимальности <tex>U</tex>. Следовательно, вершина <tex>a</tex> смежна хотя бы с одной вершиной <tex>x \in U</tex>. Отметим, что <tex>x \not\in V(T_{n-1})</tex> и, присоединив вершину <tex>x</tex> к вершине <tex>a</tex> дерева <tex>T_{n-1}</tex>, получим дерево <tex>T_n</tex> в качестве подграфа графа <tex>H</tex>.
}}
{{Теорема
|id=ter5
|author=5
|statement=<tex>r(T_n,K_m)=(m-1)(n-1)+1</tex>, где <tex>T_n</tex> — дерево на <tex>n</tex> вершинах.
|proof=
<tex>1)</tex> Докажем, что <tex>r(T_n,K_m) \geqslant (m-1)(n-1)+1</tex>. Для этого предъявим раскраску рёбер графа <tex>K_{(m-1)(n-1)}</tex>, в которой нет ни одного связного подграфа на <tex>n</tex> вершинах с рёбрами цвета <tex>1</tex> и нет клики на <tex>m</tex> вершинах с рёбрами цвета <tex>2</tex>. Разобьём вершины графа на <tex>m-1</tex> клику по <tex>n-1</tex> вершине и покрасим все рёбра этих клик в цвет <tex>1</tex>. Тогда любой связный подграф с рёбрами цвета <tex>1</tex> содержит не более <tex>n-1</tex> вершины, в частности, нет подграфа с рёбрами цвета <tex>1</tex>, изоморфного <tex>T_n</tex>. Рёбра цвета <tex>2</tex> (то есть, все оставшиеся рёбра) образуют <tex>(m-1)</tex>-дольный граф, в котором, очевидно, нет клики на <tex>m</tex> вершинах.

<tex>2)</tex> Рассмотрим произвольную раскраску рёбер полного графа <tex>K_{(m-1)(n-1)+1}</tex> в два цвета. Предположим, что не существует клики на <tex>m</tex> вершинах с рёбрами цвета <tex>2</tex>. Тогда <tex>m>1</tex> и <tex>\alpha(G_1) \leqslant m-1</tex>. По [[#l1|лемме <tex>1</tex>]], граф <tex>G_1</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах, в частности, дерево, изоморфное <tex>T_n</tex>.
}}

==Индуцированная теорема Рамсея==
{{Определение
|id=def9
|definition=Граф <tex>H</tex> называется '''индуцированным подграфом''' (англ. ''induced subgraph'') графа <tex>G</tex> если две вершины в <tex>H</tex> соединены ребром тогда и только тогда, когда они смежны в <tex>G</tex>. }}

{{Определение
|id=def10
|definition=Пусть <tex>H</tex> — граф. Граф <tex>G</tex> будем называть '''рамсеевским графом''' для <tex>H</tex>, если при любой раскраске рёбер графа <tex>G</tex> в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G</tex> изоморфный <tex>H</tex>.}}

{{Определение
|id=def11
|definition='''Индуцированным числом Рамсея''' (англ. ''induced Ramsey’s number'') <tex>r_{ind}(H)</tex> для графа <tex>H</tex> будем называть минимальное число <tex>x \in \mathbb N</tex>, такое что существует рамсеевский граф на <tex>x</tex> вершинах для графа <tex>H</tex>.}}
Заметим, что при замене произвольного графа <tex>H</tex> на клику мы получаем частный случай классической теоремы Рамсея.

{{Теорема
|id=ter6
|about=6, Индуцированная теорема Рамсея
|statement=Для любого графа <tex>H</tex> существует индуцированное число Рамсея <tex>r(H)</tex>.
}}

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

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

==См. также==
*[[Раскраска графа]]
*[[Раскраска двудольного графа в два цвета]]
*[[Теорема Турана об экстремальном графе]]

== Примечания==
<references />

== Источники информации ==
* [[wikipedia:Ramsey's theorem|Wikipedia — Ramsey's theorem]]
* [[wikipedia:Ramsey theory|Wikipedia — Ramsey theory]]
* [https://vtechworks.lib.vt.edu/bitstream/handle/10919/32873/Dickson_JO_T_2011.pdf?sequence=1&isAllowed=y An Introduction to Ramsey Theory on Graphs]
* [http://people.maths.ox.ac.uk/~gouldm/ramsey.pdf Ramsey Theory]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Дискретная математика]]
[[Категория:Теория графов]]
[[Категория: Раскраски графов]]

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

2018-12-01T05:43:13Z

188.170.72.247: /* Индуцированная теорема Рамсея */

'''Теория Рамсея''' — раздел математики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок.
==Числа Рамсея==
{{Определение
|id=def1
|definition='''Клика''' (англ. ''clique'') в неориентированном графе <tex>G = (V, E)</tex> {{---}} подмножество вершин <tex>C \subseteq V</tex>, такое что для любых двух вершин в <tex>C</tex> существует ребро, их соединяющее.}}
{{Определение
|id=def2
|definition='''Число Рамсея''' <tex>r(n, m)</tex> (англ. ''Ramsey's number'') {{---}} наименьшее из таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске ребер полного графа на <tex>x</tex> вершинах в два цвета найдется клика на <tex>n</tex> вершинах с ребрами цвета <tex>1</tex> или клика на <tex>m</tex> вершинах с ребрами цвета <tex>2</tex>. }}

[[Файл:RamseyTheoryK5.png|200px|thumb|upright|Раскраска <tex>K_5</tex> без одноцветных треугольников]]
Часто определение для чисел Рамсея дается через задачу "о друзьях и незнакомцах"<ref>[https://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers| Theorem on friends and strangers]</ref>. Пусть на вечеринке каждые два человека могут быть либо друзьями, либо незнакомцами, в общем виде задачи требуется найти, какое минимальное количество людей нужно взять, чтобы хотя бы <tex>n</tex> человек были попарно знакомы, или хотя бы <tex>m</tex> человек были попарно незнакомы. Если мы переформулируем данную задачу в терминах графов, то как раз получим определение числа Рамсея <tex>r(n, m)</tex>, представленное ранее.

Чтобы получить лучшее представление природы чисел Рамсея, приведем пример. Докажем, что <tex>r(3,3) = 6</tex>. Представим, что ребра <tex>K_6</tex> раскрашены в два цвета: красный и синий. Возьмем вершину <tex>v</tex>. Данной вершине, как и всем другим, инцидентны <tex>5</tex> рёбер, тогда, согласно принципу Дирихле, хотя бы три из них одного цвета. Для определенности положим, что хотя бы <tex>3</tex> ребра, соединяющие вершину <tex>v</tex> с вершинами <tex>r</tex>, <tex>s</tex>, <tex>t</tex>, синие. Если хотя бы одно из ребер <tex>rs</tex>, <tex>rt</tex>, <tex>st</tex> синее, то в графе есть синий треугольник (полный граф на трёх вершинах), иначе, если они все красные, есть красный треугольник. Таким образом, <tex>r(3,3) \leqslant 6 </tex>.
Чтобы доказать, что <tex>r(3,3) = 6 </tex>, предъявим такую раскраску графа <tex>K_5</tex>, где нет клики на трех вершинах ни синего, ни красного цвета. Такая раскраска представлена на рисунке справа.

===Теорема Рамсея. Оценки сверху===
{{Теорема|id=ter1|about=1, Теорема Рамсея
|statement= Для любых <tex>n,m \in \mathbb N</tex> существует число <tex>r(n,m)</tex>, при этом <tex>r(n,m) \leqslant r(n,m-1)+r(n-1,m)</tex>, а также если числа <tex>r(n,m-1)</tex> и <tex>r(n-1,m)</tex> четные, то неравенство принимает вид <tex>r(n,m) \leqslant r(n,m-1)+r(n-1,m) - 1</tex> .
|proof=

<tex>1)</tex> Докажем с помощью метода математической индукции по <tex>n+m</tex>.

'''База:''' <tex>r(n,\;1) = r(1,\;n) = 1</tex>, так как граф, состоящий из одной вершины, можно считать полным графом любого цвета.

'''Индукционный переход:''' Пусть <tex>n>1</tex> и <tex>m>1</tex>. Рассмотрим полный чёрно-белый граф из <tex>r(n-1,\;m)+r(n,\;m-1)</tex> вершин. Возьмём произвольную вершину <tex>v</tex> и обозначим через <tex>M</tex> и <tex>N</tex> множества, инцидентные <tex>v</tex> в чёрном и белом подграфе соответственно. Так как в графе <tex>r(n-1,\;m)+r(n,\;m-1)=|M|+|N|+1 </tex> вершин, согласно принципу Дирихле, либо <tex>|M|\geqslant r(n-1,\;m)</tex>, либо <tex>|N|\geqslant r(n,\;m-1)</tex>. Пусть <tex>|M|\geqslant r(n-1,\;m)</tex>. Тогда либо в <tex>M</tex> существует белый <tex>K_m</tex>, что доказывает теорему, либо в <tex>M</tex> есть чёрный <tex>K_{n-1}</tex>, который вместе с <tex>v</tex> образует чёрный <tex>K_n</tex>, в этом случае теорема также доказана. Случай <tex>|N|\geqslant r(n,\;m-1)</tex> рассматривается аналогично.

<tex>2)</tex> Предположим, <tex>p=r(n-1,\;m)</tex> и <tex>q=r(n,\;m-1)</tex> оба чётны. Положим <tex>s=p+q-1</tex> и рассмотрим чёрно-белый граф из <tex>s</tex> вершин. Если <tex>d_i</tex> степень <tex>i</tex>-й вершины в чёрном подграфе, то, согласно [[Лемма о рукопожатиях|лемме о рукопожатиях]], <tex>\sum_{i=1}^s d_i</tex> — чётно. Поскольку <tex>s</tex> нечётно, должно существовать чётное <tex>d_i</tex>. Не умаляя общности, положим, что <tex>d_1</tex> чётно. Обозначим через <tex>M</tex> и <tex>N</tex> вершины, ,инцидентные вершине <tex>1</tex> в чёрном и белом подграфах соответственно. Тогда <tex>|M|=d_1</tex> и <tex>|N|=s-1-d_1</tex> оба чётны. Согласно принципу Дирихле, либо <tex>|M|\geqslant p-1</tex>, либо <tex>N\geqslant q</tex>. Так как <tex>|M|</tex> чётно, а <tex>p-1</tex> нечётно, первое неравенство можно усилить, так что либо <tex>|M|\geqslant p</tex>, либо <tex>|N|\geqslant q</tex>.

Предположим <tex>|M|\geqslant p=r(n-1,\;m)</tex>. Тогда либо подграф, порождённый множеством <tex>M</tex>, содержит белый <tex>K_m</tex> и доказательство завершено, либо он содержит чёрный <tex>K_{n-1}</tex>, который вместе с вершиной <tex>1</tex> образует чёрный <tex>K_n</tex>. Случай <tex>|N|\geqslant q=r(n,\;m-1)</tex> рассматривается аналогично.
}}
{{Утверждение|id=u1|about=1|statement=Для натуральных чисел <tex>m,n</tex> выполняется равенство <tex>r(n,m) \leqslant C_{n+m-2}^{n-1}</tex>
|proof=
Очевидно, <tex>C^{n-1}_{n+m-2}=1</tex> при <tex>n=1</tex> или <tex>m=1</tex>, как и соответствующие числа Рамсея. Индукцией по <tex>n</tex> и <tex>m</tex> при <tex>n,m \geqslant 2</tex> получаем
<tex>r(n,m) \leqslant r(n,m-1)+r(n-1,m) \leqslant C^{n-1}_{n+m-3}+C^{n-2}_{n+m-3}=C^{n-1}_{n+m-2}</tex>
}}

===Оценки снизу===

{{Теорема|id=ter2|about=2
|statement=Для любого натурального числа <tex>k \geqslant 2</tex> выполняется неравенство <tex>r(k,k) \geqslant k^{k/2}</tex>
|proof=
Так как <tex>r(2,2)=2</tex>, достаточно рассмотреть случай <tex>k \geqslant 3</tex>.
Зафиксируем множество различных помеченных вершин <tex>v_i,\ldots,v_n</tex>. Пусть <tex>g(n,k)</tex> {{---}} доля среди всех графов на вершинах <tex>v_i,\ldots,v_n</tex> тех графов, что содержат клику на <tex>k</tex> вершинах. Всего графов на наших вершинах, очевидно <tex>2^{C^2_n}</tex> (каждое из возможных рёбер <tex>C^2_n</tex> можно провести или не провести).

Посчитаем графы с кликой на <tex>k</tex> вершинах следующим образом: существует <tex>C^k_n</tex> способов выбрать <tex>k</tex> вершин для клики в нашем множестве, после чего все рёбра между ними будем считать проведенными, а остальные ребра выбираются произвольно. Таким образом, каждый граф с кликой на <tex>k</tex> вершинах будет посчитан, причём некоторые даже более одного раза. Количестве графов с кликой оказывается не более, чем <tex>C^k_n\cdot 2^{C^2_n-C^2_k}</tex>. Следовательно,

<tex>g(n,k) \leqslant \dfrac{C^k_n}{2^{C^2_k}}<\dfrac{n^k}{k!\cdot 2^{C^2_k}}</tex> <tex>(*)</tex>

Подставив <tex>n<2^{k/2}</tex> в неравенство <tex>(*)</tex> мы получаем

<tex>g(n,k)<\dfrac{2^{k^2/2}\cdot 2^{-C^2_k}}{k!}=\dfrac{2^{k/2}}{k!}<\dfrac12</tex> при <tex>k \geqslant 3</tex>

Предположим, что <tex>r(k,k)=n<2^{k/2}</tex> и разобьём все графы на <tex>n</tex> вершинах на пары <tex>G, \overline G</tex> (граф и его дополнение) Так как <tex>g(n,k)<\dfrac12</tex>, то существует пара, в которой ни <tex>G</tex>, ни <tex>\overline G</tex> не содержат клики на <tex>k</tex> вершинах. Рассмотрим раскраску рёбер <tex>K_n</tex> в два цвета, в которой ребра цвета <tex>1</tex> образуют граф <tex>G</tex>. В такой раскраске нет клики на <tex>k</tex> вершинах ни цвета <tex>1</tex>, ни цвета <tex>1</tex>, получили противоречи противоречие. Значит <tex>n</tex> было выбрано неверно. Из этого следует <tex>r(k,k) \geqslant 2^{k/2}</tex>.
}}

===Свойства чисел Рамсея===
Следующими свойствами удобно пользоваться при подсчете значений чисел Рамсея <tex>r(n,m)</tex> на практике.
* <tex>r(n,m) = r(m,n)</tex>
* <tex>r(1,m) = 1</tex>
* <tex>r(2,m) = m</tex>

===Значения чисел Рамсея===
Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, их известно довольно мало. Далее приведена таблица Станислава Радзишевского <ref>[http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1| Small Ramsey Numbers by Stanisław Radziszowski]</ref>, в которой присутствуют практически все известные числа Рамсея или же промежутки, в которых они находятся.
<center>
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
|+
!colspan="11"|Числа Рамсея
|-align="center"
! width="6%" |<tex>n,\ m</tex>
! width="6%" |<tex>1 </tex>
! width="6%" |<tex>2 </tex>
! width="6%" |<tex>3 </tex>
! width="6%" |<tex>4 </tex>
! width="6%" |<tex>5 </tex>
! width="6%" |<tex>6 </tex>
! width="6%" |<tex>7 </tex>
! width="6%" |<tex>8 </tex>
! width="6%" |<tex>9 </tex>
! width="6%" |<tex>10</tex>
|-align="center"
! <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
|-align="center"
! <tex>2 </tex>
| <tex>1 </tex>
| <tex>2 </tex>
| <tex>3 </tex>
| <tex>4 </tex>
| <tex>5 </tex>
| <tex>6 </tex>
| <tex>7 </tex>
| <tex>8 </tex>
| <tex>9 </tex>
| <tex>10</tex>
|-align="center"
! <tex>3</tex>
| <tex>1</tex>
| <tex>3</tex>
| <tex>6</tex>
| <tex>9</tex>
| <tex>14</tex>
| <tex>18</tex>
| <tex>23</tex>
| <tex>28</tex>
| <tex>36</tex>
| <tex>[40, 42]</tex>
|-align="center"
! <tex>4</tex>
| <tex>1</tex>
| <tex>4</tex>
| <tex>9</tex>
| <tex>18</tex>
| <tex>25</tex>
| <tex>[36, 41]</tex>
| <tex>[49, 61]</tex>
| <tex>[59, 84]</tex>
| <tex>[73, 115]</tex>
| <tex>[92, 149]</tex>
|-align="center"
! <tex>5</tex>
| <tex>1</tex>
| <tex>5</tex>
| <tex>14</tex>
| <tex>25</tex>
| <tex>[43, 48]</tex>
| <tex>[58, 87]</tex>
| <tex>[80, 143]</tex>
| <tex>[101, 216]</tex>
| <tex>[133, 316]</tex>
| <tex>[149, 442]</tex>
|-align="center"
! <tex>6</tex>
| <tex>1</tex>
| <tex>6</tex>
| <tex>18</tex>
| <tex>[36, 41]</tex>
| <tex>[58, 87]</tex>
| <tex>[102, 165]</tex>
| <tex>[115, 298]</tex>
| <tex>[134, 495]</tex>
| <tex>[183, 780]</tex>
| <tex>[204, 1171]</tex>
|-align="center"
! <tex>7</tex>
| <tex>1</tex>
| <tex>7</tex>
| <tex>23</tex>
| <tex>[49, 61]</tex>
| <tex>[80, 143]</tex>
| <tex>[115, 298]</tex>
| <tex>[205, 540]</tex>
| <tex>[217, 1031]</tex>
| <tex>[252, 1713]</tex>
| <tex>[292, 2826]</tex>
|-align="center"
! <tex>8</tex>
| <tex>1</tex>
| <tex>8</tex>
| <tex>28</tex>
| <tex>[56, 84]</tex>
| <tex>[101, 216]</tex>
| <tex>[127, 495]</tex>
| <tex>[217, 1031]</tex>
| <tex>[282, 1870]</tex>
| <tex>[329, 3583]</tex>
| <tex>[343, 6090]</tex>
|-align="center"
! <tex>9</tex>
| <tex>1</tex>
| <tex>9</tex>
| <tex>36</tex>
| <tex>[73, 115]</tex>
| <tex>[133, 316]</tex>
| <tex>[183, 780]</tex>
| <tex>[252, 1713]</tex>
| <tex>[329, 3583]</tex>
| <tex>[565, 6588]</tex>
| <tex>[580, 12677]</tex>
|-align="center"
! <tex>10</tex>
| <tex>1</tex>
| <tex>10</tex>
| <tex>[40, 42]</tex>
| <tex>[92, 149]</tex>
| <tex>[149, 442]</tex>
| <tex>[179, 1171]</tex>
| <tex>[289, 2826]</tex>
| <tex>[343, 6090]</tex>
| <tex>[581, 12677]</tex>
| <tex>[798, 23556]</tex>
|}
</center>

===Числа Рамсея для раскрасок в несколько цветов===
Теперь обобщим числа Рамсея на произвольное количество цветов.
{{Определение
|id=def4
|definition=
'''Число Рамсея''' <tex>r(n_1,\ldots,n_k)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в <tex>k</tex> цветов для некоторого <tex>i \in [1 \ldots k]</tex> обязательно найдётся клика на <tex>n_i</tex> вершинах с рёбрами цвета <tex>i</tex>. <tex>k,n_1,\ldots,n_k \in \mathbb N</tex>
}}

{{Теорема
|id=ter3|about=3,Теорема Рамсея для нескольких цветов
|statement=<tex>\forall k, n_1, \ldots n_k \in \mathbb N </tex> существует соответственное число Рамсея <tex>r(n_1,\ldots,n_k)</tex>, при этом <tex>r(n_1,\ldots,n_k)\leqslant r(n_1,\ldots, n_{k-2}, r(n_{k-1},\;n_k)).</tex>
|proof=
Возьмем граф из <tex>r(n_1,\ldots, n_{k-2}, r(n_{k-1}, n_k))</tex> вершин и окрасим его рёбра в <tex>k</tex> цветов. Пока что будем считать цвета <tex>k-1</tex> и <tex>k</tex> одним цветом. Тогда граф будет <tex>(k-1)</tex>-цветным. Согласно определению числа Рамсея <tex>r(n_1,\ldots,n_{k-2},r(n_{k-1},n_k))</tex>, такой граф либо содержит <tex>K_{n_i}</tex> для некоторого цвета <tex>i</tex>, такого что <tex>1\leqslant i\leqslant k-2</tex> либо <tex>K_{r(k, n_{k-1},n_k)}</tex>, окрашенный общим цветом <tex>k-1</tex> и <tex>k</tex>. В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный <tex>r(n_{k-1},n_k)</tex> — вершинный граф содержит либо <tex>K_{n_{k-1}}</tex> цвета <tex>k-1</tex>, либо <tex>K_{n_k}</tex> цвета <tex>k</tex>. Таким образом любое число Рамсея для раскраски в <tex>k</tex> цветов ограничено некоторым числом Рамсея для меньшего количества цветов, следовательно, <tex>r(n_1,\ldots,n_k)</tex> существует для любых <tex> k, n_1, \ldots n_k, \in \mathbb N </tex>, и теорема доказана.
}}

==Числа Рамсея больших размерностей==
{{Определение
|id=def5
|definition=
Пусть <tex>m,k,n_1,\ldots ,n_k \in \mathbb N</tex>, причём <tex>n_1,\ldots ,n_k \geqslant m</tex>. '''Число Рамсея''' <tex>r_m(n_1,\ldots ,n_k)</tex> — наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске <tex>m</tex>-элементных подмножеств <tex>x</tex>-элементного множества <tex>M</tex> в <tex>k</tex> цветов для некоторого <tex>i \in [1\ldots k]</tex> обязательно найдётся такое множество <tex>W_i</tex>, что <tex>|W_i|=n_i</tex> и все <tex>m</tex>-элементные подмножества множества <tex>W_i</tex> имеют цвет <tex>i</tex>. Число <tex>m</tex> называют '''размерностью''' числа Рамсея <tex>r_m(n_1,\ldots ,n_k)</tex>.
}}
Заметим, что числа Рамсея размерности <tex>2</tex> — это определённые ранее числа Рамсея для клик.

{{Определение
|id=def7|definition=
Для каждого множества <tex>M</tex> через <tex>M^k</tex> мы будем обозначать множество всех <tex>k</tex>-элементных подмножеств <tex>M</tex>.
}}
{{Теорема
|id=ter4|about=4, Теорема Рамсея для чисел больших размерностей
|statement=Пусть <tex>m,k,n_1,\ldots,n_k</tex> {{---}} натуральные числа, причем <tex>k \geqslant 2</tex>, а <tex>n_1,\ldots ,n_k \geqslant m</tex>. Тогда существует число Рамсея <tex>r_m(n_1,\ldots n_k)</tex>.
|proof=
<tex>1)</tex> Мы будем доказывать теорему по индукции. Начнем со случая <tex>k=2</tex>. Приступая к доказательству для числа <tex>r_m(n_1,n_2)</tex> мы будем считать доказанным утверждение теоремы для чисел Рамсея всех меньших размерностей и чисел Рамсея размерности <tex>m</tex> с меньшей суммой <tex>n_1+n_2</tex>. В качестве базы будем использовать случай чисел Рамсея размерности <tex>2</tex> разобранный выше. Итак, мы докажем, что <tex>r_m(n_1,n_2)-1 \leqslant p=r_{m-1}(r_m(n_1-1,n_2),r_m(n_1,n_2-1))</tex>.

Рассмотрим <tex>(p+1)</tex>-элементное множество <tex>M</tex> и выделим в нём элемент <tex>a</tex>. Пусть <tex>M_0=M \setminus \{ a \}</tex>. Пусть <tex>\rho:M^m\rightarrow \{1, 2 \} </tex> — произвольная раскраска в два цвета. Рассмотрим раскраску <tex>\rho': M_0^{m-1} \rightarrow \{1, 2\} </tex> , определённую следующим образом: для каждого множества <tex>B \in M_0^{m-1}</tex> пусть <tex>\rho'(B) = \rho(B \cup \{ a \})</tex>.
Так как <tex>|M_0|=p</tex>, либо существует <tex>r_m(n_1 — 1,n_2)</tex>-элементное подмножество <tex>M_i \subset M_0</tex>, <tex>\rho'(B)=1</tex> на всех <tex>B \in M_1^{m-1}</tex>, либо существует <tex>r_m(n_1,n_2-1)</tex>-элементное подмножество <tex>M_2 \subset M_0</tex>, <tex>\rho'(B)=2</tex> на всех <tex>B \in M_2^{m-1}</tex>. Случаи аналогичны, рассмотрим первый случай и множество <tex>M_1</tex>.
По индукционному предположен из <tex>|M_1|=r_m(n_1-1,n_2)</tex> следует, что либо существует <tex>n_1-1</tex>-элементное подмножество <tex>N_1 \subset M_1</tex>, <tex>\rho(A)=1</tex> на всех <tex>A \in N^m_1</tex>, либо существует <tex>n_2</tex>-элементное подмножество <tex>N_2 \subset M_1</tex>, <tex>\rho(A)=2</tex> на всех <tex>A \in N_2^m</tex>. Во втором случае искомое подмножество найдено (это <tex>N_2</tex>), рассмотрим первый случай и множество <tex>N=N_1 \cup \{a\}</tex>. Пусть <tex>A \in N^m</tex>. Если <tex>A \not\ni a</tex>, то <tex>A \in N_1^m</tex> и следовательно <tex>\rho(A)=1</tex>. Если же <tex>A \ni a</tex>, то множество <tex>A \setminus \{a\} \in N_1^{m-1} \subset M_1^{m-1}</tex> и поэтому <tex>\rho(A)=\rho'(A \setminus \{a \})=1</tex>. Учитывая, что <tex>|N|=n_1</tex>, мы нашли искомое подмножество и в этом случае.

<tex>2)</tex> При <tex>k>2</tex> будем вести индукцию по <tex>k</tex> с доказанной выше базой <tex>k=2</tex>. При <tex>k>2</tex> мы докажем неравенство.
<tex>r_m(n_1,\ldots ,n_k) \leqslant q=r_m(r_m(n_1,\ldots ,n_{k-1}),n_k)</tex>

Для этого мы рассмотрим множество <tex>M</tex> на <tex>q</tex> вершинах и произвольную раскраску <tex>\rho:M^m \rightarrow [1 \ldots k]</tex> в <tex>k</tex>цветов. Рассмотрим раскраску <tex>\rho':M^m \rightarrow \{0,k\}</tex>, в которой цвета <tex>1,\ldots,k-1</tex> раскраски <tex>\rho</tex> склеены в цвет <tex>0</tex>. Тогда существует либо такое подмножество <tex>M_0 \subset M</tex>, что <tex>|M_0|=r_m(n_1,\ldots ,n_{k-1})</tex> и <tex>\rho'(A)=0</tex> на всех <tex>A \in M_0^m</tex>, либо существует такое <tex>n_k</tex>-элементное подмножество <tex>M_k \subset M</tex>, что <tex>\rho(A)=\rho'(A)=k</tex> на всех <tex>A \in M^m_k</tex>. Во втором случае <tex>M_k</tex> — искомое подмножество, а в первом случае заметим, что на любом подмножестве <tex>A \in M_0^m</tex> из <tex>\rho'(A)=0</tex> следует <tex>\rho(A) \in [1 \ldots k-1]</tex>. Исходя из размера множества <tex>M_0</tex> по индукционному предположению получаем, что найдется искомое подмножество множества <tex>M</tex> для одного из цветов <tex>1,\ldots ,k-1</tex>, таким образом неравенство доказано, а из этого следует и существование числа Рамсея <tex>r_m(n_1,\ldots ,n_k)</tex>.
}}

==Числа Рамсея для произвольных графов==
Еще один способ обобщения классической теории Рамсея — замена клик на произвольные графы-шаблоны.
{{Определение
|id=def8
|definition=
Пусть <tex>H_1,H_2</tex> — графы. Число Рамсея <tex>r(H_1,H_2)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в два цвета обязательно найдется подграф, изоморфный <tex>H_1</tex> с рёбрами цвета <tex>1</tex> или подграф изоморфный <tex>H_2</tex> с рёбрами цвета <tex>2</tex>.
}}
Из результатов классической теории Рамсея становится понятно, что числа <tex>r(H_1,H_2)</tex> существуют.

{{Лемма
|id=l1|about=1|statement=Пусть <tex>m>1</tex>, а граф <tex>H</tex> таков, что <tex>v(H) \geqslant (m-1)(n-1)+1</tex> и <tex>\alpha(H) \leqslant m-1</tex>. Тогда граф <tex>H</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах.
|proof=
Зафиксируем <tex>m</tex> и проведем индукцию по <tex>n</tex>.

'''База:''' для <tex>n=1</tex> очевидно.

'''Индукционный переход:''' Пусть верно для <tex>n-1</tex>, докажем для <tex>n</tex>. Рассмотрим произвольное дерево <tex>T_n</tex> на <tex>n</tex> вершинах, пусть дерево <tex>T_{n-1}</tex> получено из <tex>T_n</tex> удалением висячей вершины. Пусть <tex>U</tex> — максимальное независимое множестве вершин графа <tex>H</tex>. Тогда <tex>|U|=\alpha(H) \leqslant m-1</tex>, следовательно <tex>v(H-U) \geqslant (m-1)(n-2)+1</tex> и очевидно <tex>\alpha(H-U) \leqslant m-1</tex>.
По индукционному предположению, граф <tex>H-U</tex> содержит в качестве подграфа дерево <tex>T_{n-1}</tex>. Пусть <tex>a</tex> — вершина этого дерева, присоединив к которой висячую вершину мы получим дерево <tex>T_n</tex>. Заметим, что множество <tex>U \cup</tex> <tex>\{a\}</tex> не является независимым ввиду максимальности <tex>U</tex>. Следовательно, вершина <tex>a</tex> смежна хотя бы с одной вершиной <tex>x \in U</tex>. Отметим, что <tex>x \not\in V(T_{n-1})</tex> и, присоединив вершину <tex>x</tex> к вершине <tex>a</tex> дерева <tex>T_{n-1}</tex>, получим дерево <tex>T_n</tex> в качестве подграфа графа <tex>H</tex>.
}}
{{Теорема
|id=ter5
|author=5
|statement=<tex>r(T_n,K_m)=(m-1)(n-1)+1</tex>, где <tex>T_n</tex> — дерево на <tex>n</tex> вершинах.
|proof=
<tex>1)</tex> Докажем, что <tex>r(T_n,K_m) \geqslant (m-1)(n-1)+1</tex>. Для этого предъявим раскраску рёбер графа <tex>K_{(m-1)(n-1)}</tex>, в которой нет ни одного связного подграфа на <tex>n</tex> вершинах с рёбрами цвета <tex>1</tex> и нет клики на <tex>m</tex> вершинах с рёбрами цвета <tex>2</tex>. Разобьём вершины графа на <tex>m-1</tex> клику по <tex>n-1</tex> вершине и покрасим все рёбра этих клик в цвет <tex>1</tex>. Тогда любой связный подграф с рёбрами цвета <tex>1</tex> содержит не более <tex>n-1</tex> вершины, в частности, нет подграфа с рёбрами цвета <tex>1</tex>, изоморфного <tex>T_n</tex>. Рёбра цвета <tex>2</tex> (то есть, все оставшиеся рёбра) образуют <tex>(m-1)</tex>-дольный граф, в котором, очевидно, нет клики на <tex>m</tex> вершинах.

<tex>2)</tex> Рассмотрим произвольную раскраску рёбер полного графа <tex>K_{(m-1)(n-1)+1}</tex> в два цвета. Предположим, что не существует клики на <tex>m</tex> вершинах с рёбрами цвета <tex>2</tex>. Тогда <tex>m>1</tex> и <tex>\alpha(G_1) \leqslant m-1</tex>. По [[#l1|лемме <tex>1</tex>]], граф <tex>G_1</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах, в частности, дерево, изоморфное <tex>T_n</tex>.
}}

==Индуцированная теорема Рамсея==
{{Определение
|id=def9
|definition=Граф <tex>H</tex> называется '''индуцированным подграфом''' (англ. ''induced subgraph'') графа <tex>G</tex> если две вершины в <tex>H</tex> соединены ребром тогда и только тогда, когда они смежны в <tex>G</tex>. }}

{{Определение
|id=def10
|definition=Пусть <tex>H</tex> — граф. Граф <tex>G</tex> будем называть '''рамсеевским графом''' для <tex>H</tex>, если при любой раскраске рёбер графа <tex>G</tex> в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G</tex> изоморфный <tex>H</tex>.}}

{{Определение
|id=def11
|definition='''Индуцированным числом Рамсея''' (англ. ''induced Ramsey number'') <tex>r_{ind}(H)</tex> для графа <tex>H</tex> будем называть минимальное число <tex>x \in \mathbb N</tex>, такое что существует рамсеевский граф на <tex>x</tex> вершинах для графа <tex>H</tex>.}}
Заметим, что при замене произвольного графа <tex>H</tex> на клику мы получаем частный случай классической теоремы Рамсея.

{{Теорема
|id=ter6
|about=6, Индуцированная теорема Рамсея
|statement=Для любого графа <tex>H</tex> существует индуцированное число Рамсея <tex>r(H)</tex>.
}}

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

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

==См. также==
*[[Раскраска графа]]
*[[Раскраска двудольного графа в два цвета]]
*[[Теорема Турана об экстремальном графе]]

== Примечания==
<references />

== Источники информации ==
* [[wikipedia:Ramsey's theorem|Wikipedia — Ramsey's theorem]]
* [[wikipedia:Ramsey theory|Wikipedia — Ramsey theory]]
* [https://vtechworks.lib.vt.edu/bitstream/handle/10919/32873/Dickson_JO_T_2011.pdf?sequence=1&isAllowed=y An Introduction to Ramsey Theory on Graphs]
* [http://people.maths.ox.ac.uk/~gouldm/ramsey.pdf Ramsey Theory]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Дискретная математика]]
[[Категория:Теория графов]]
[[Категория: Раскраски графов]]

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

2018-12-01T05:38:49Z

188.170.72.247: /* Числа Рамсея больших размерностей */

'''Теория Рамсея''' — раздел математики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок.
==Числа Рамсея==
{{Определение
|id=def1
|definition='''Клика''' (англ. ''clique'') в неориентированном графе <tex>G = (V, E)</tex> {{---}} подмножество вершин <tex>C \subseteq V</tex>, такое что для любых двух вершин в <tex>C</tex> существует ребро, их соединяющее.}}
{{Определение
|id=def2
|definition='''Число Рамсея''' <tex>r(n, m)</tex> (англ. ''Ramsey's number'') {{---}} наименьшее из таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске ребер полного графа на <tex>x</tex> вершинах в два цвета найдется клика на <tex>n</tex> вершинах с ребрами цвета <tex>1</tex> или клика на <tex>m</tex> вершинах с ребрами цвета <tex>2</tex>. }}

[[Файл:RamseyTheoryK5.png|200px|thumb|upright|Раскраска <tex>K_5</tex> без одноцветных треугольников]]
Часто определение для чисел Рамсея дается через задачу "о друзьях и незнакомцах"<ref>[https://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers| Theorem on friends and strangers]</ref>. Пусть на вечеринке каждые два человека могут быть либо друзьями, либо незнакомцами, в общем виде задачи требуется найти, какое минимальное количество людей нужно взять, чтобы хотя бы <tex>n</tex> человек были попарно знакомы, или хотя бы <tex>m</tex> человек были попарно незнакомы. Если мы переформулируем данную задачу в терминах графов, то как раз получим определение числа Рамсея <tex>r(n, m)</tex>, представленное ранее.

Чтобы получить лучшее представление природы чисел Рамсея, приведем пример. Докажем, что <tex>r(3,3) = 6</tex>. Представим, что ребра <tex>K_6</tex> раскрашены в два цвета: красный и синий. Возьмем вершину <tex>v</tex>. Данной вершине, как и всем другим, инцидентны <tex>5</tex> рёбер, тогда, согласно принципу Дирихле, хотя бы три из них одного цвета. Для определенности положим, что хотя бы <tex>3</tex> ребра, соединяющие вершину <tex>v</tex> с вершинами <tex>r</tex>, <tex>s</tex>, <tex>t</tex>, синие. Если хотя бы одно из ребер <tex>rs</tex>, <tex>rt</tex>, <tex>st</tex> синее, то в графе есть синий треугольник (полный граф на трёх вершинах), иначе, если они все красные, есть красный треугольник. Таким образом, <tex>r(3,3) \leqslant 6 </tex>.
Чтобы доказать, что <tex>r(3,3) = 6 </tex>, предъявим такую раскраску графа <tex>K_5</tex>, где нет клики на трех вершинах ни синего, ни красного цвета. Такая раскраска представлена на рисунке справа.

===Теорема Рамсея. Оценки сверху===
{{Теорема|id=ter1|about=1, Теорема Рамсея
|statement= Для любых <tex>n,m \in \mathbb N</tex> существует число <tex>r(n,m)</tex>, при этом <tex>r(n,m) \leqslant r(n,m-1)+r(n-1,m)</tex>, а также если числа <tex>r(n,m-1)</tex> и <tex>r(n-1,m)</tex> четные, то неравенство принимает вид <tex>r(n,m) \leqslant r(n,m-1)+r(n-1,m) - 1</tex> .
|proof=

<tex>1)</tex> Докажем с помощью метода математической индукции по <tex>n+m</tex>.

'''База:''' <tex>r(n,\;1) = r(1,\;n) = 1</tex>, так как граф, состоящий из одной вершины, можно считать полным графом любого цвета.

'''Индукционный переход:''' Пусть <tex>n>1</tex> и <tex>m>1</tex>. Рассмотрим полный чёрно-белый граф из <tex>r(n-1,\;m)+r(n,\;m-1)</tex> вершин. Возьмём произвольную вершину <tex>v</tex> и обозначим через <tex>M</tex> и <tex>N</tex> множества, инцидентные <tex>v</tex> в чёрном и белом подграфе соответственно. Так как в графе <tex>r(n-1,\;m)+r(n,\;m-1)=|M|+|N|+1 </tex> вершин, согласно принципу Дирихле, либо <tex>|M|\geqslant r(n-1,\;m)</tex>, либо <tex>|N|\geqslant r(n,\;m-1)</tex>. Пусть <tex>|M|\geqslant r(n-1,\;m)</tex>. Тогда либо в <tex>M</tex> существует белый <tex>K_m</tex>, что доказывает теорему, либо в <tex>M</tex> есть чёрный <tex>K_{n-1}</tex>, который вместе с <tex>v</tex> образует чёрный <tex>K_n</tex>, в этом случае теорема также доказана. Случай <tex>|N|\geqslant r(n,\;m-1)</tex> рассматривается аналогично.

<tex>2)</tex> Предположим, <tex>p=r(n-1,\;m)</tex> и <tex>q=r(n,\;m-1)</tex> оба чётны. Положим <tex>s=p+q-1</tex> и рассмотрим чёрно-белый граф из <tex>s</tex> вершин. Если <tex>d_i</tex> степень <tex>i</tex>-й вершины в чёрном подграфе, то, согласно [[Лемма о рукопожатиях|лемме о рукопожатиях]], <tex>\sum_{i=1}^s d_i</tex> — чётно. Поскольку <tex>s</tex> нечётно, должно существовать чётное <tex>d_i</tex>. Не умаляя общности, положим, что <tex>d_1</tex> чётно. Обозначим через <tex>M</tex> и <tex>N</tex> вершины, ,инцидентные вершине <tex>1</tex> в чёрном и белом подграфах соответственно. Тогда <tex>|M|=d_1</tex> и <tex>|N|=s-1-d_1</tex> оба чётны. Согласно принципу Дирихле, либо <tex>|M|\geqslant p-1</tex>, либо <tex>N\geqslant q</tex>. Так как <tex>|M|</tex> чётно, а <tex>p-1</tex> нечётно, первое неравенство можно усилить, так что либо <tex>|M|\geqslant p</tex>, либо <tex>|N|\geqslant q</tex>.

Предположим <tex>|M|\geqslant p=r(n-1,\;m)</tex>. Тогда либо подграф, порождённый множеством <tex>M</tex>, содержит белый <tex>K_m</tex> и доказательство завершено, либо он содержит чёрный <tex>K_{n-1}</tex>, который вместе с вершиной <tex>1</tex> образует чёрный <tex>K_n</tex>. Случай <tex>|N|\geqslant q=r(n,\;m-1)</tex> рассматривается аналогично.
}}
{{Утверждение|id=u1|about=1|statement=Для натуральных чисел <tex>m,n</tex> выполняется равенство <tex>r(n,m) \leqslant C_{n+m-2}^{n-1}</tex>
|proof=
Очевидно, <tex>C^{n-1}_{n+m-2}=1</tex> при <tex>n=1</tex> или <tex>m=1</tex>, как и соответствующие числа Рамсея. Индукцией по <tex>n</tex> и <tex>m</tex> при <tex>n,m \geqslant 2</tex> получаем
<tex>r(n,m) \leqslant r(n,m-1)+r(n-1,m) \leqslant C^{n-1}_{n+m-3}+C^{n-2}_{n+m-3}=C^{n-1}_{n+m-2}</tex>
}}

===Оценки снизу===

{{Теорема|id=ter2|about=2
|statement=Для любого натурального числа <tex>k \geqslant 2</tex> выполняется неравенство <tex>r(k,k) \geqslant k^{k/2}</tex>
|proof=
Так как <tex>r(2,2)=2</tex>, достаточно рассмотреть случай <tex>k \geqslant 3</tex>.
Зафиксируем множество различных помеченных вершин <tex>v_i,\ldots,v_n</tex>. Пусть <tex>g(n,k)</tex> {{---}} доля среди всех графов на вершинах <tex>v_i,\ldots,v_n</tex> тех графов, что содержат клику на <tex>k</tex> вершинах. Всего графов на наших вершинах, очевидно <tex>2^{C^2_n}</tex> (каждое из возможных рёбер <tex>C^2_n</tex> можно провести или не провести).

Посчитаем графы с кликой на <tex>k</tex> вершинах следующим образом: существует <tex>C^k_n</tex> способов выбрать <tex>k</tex> вершин для клики в нашем множестве, после чего все рёбра между ними будем считать проведенными, а остальные ребра выбираются произвольно. Таким образом, каждый граф с кликой на <tex>k</tex> вершинах будет посчитан, причём некоторые даже более одного раза. Количестве графов с кликой оказывается не более, чем <tex>C^k_n\cdot 2^{C^2_n-C^2_k}</tex>. Следовательно,

<tex>g(n,k) \leqslant \dfrac{C^k_n}{2^{C^2_k}}<\dfrac{n^k}{k!\cdot 2^{C^2_k}}</tex> <tex>(*)</tex>

Подставив <tex>n<2^{k/2}</tex> в неравенство <tex>(*)</tex> мы получаем

<tex>g(n,k)<\dfrac{2^{k^2/2}\cdot 2^{-C^2_k}}{k!}=\dfrac{2^{k/2}}{k!}<\dfrac12</tex> при <tex>k \geqslant 3</tex>

Предположим, что <tex>r(k,k)=n<2^{k/2}</tex> и разобьём все графы на <tex>n</tex> вершинах на пары <tex>G, \overline G</tex> (граф и его дополнение) Так как <tex>g(n,k)<\dfrac12</tex>, то существует пара, в которой ни <tex>G</tex>, ни <tex>\overline G</tex> не содержат клики на <tex>k</tex> вершинах. Рассмотрим раскраску рёбер <tex>K_n</tex> в два цвета, в которой ребра цвета <tex>1</tex> образуют граф <tex>G</tex>. В такой раскраске нет клики на <tex>k</tex> вершинах ни цвета <tex>1</tex>, ни цвета <tex>1</tex>, получили противоречи противоречие. Значит <tex>n</tex> было выбрано неверно. Из этого следует <tex>r(k,k) \geqslant 2^{k/2}</tex>.
}}

===Свойства чисел Рамсея===
Следующими свойствами удобно пользоваться при подсчете значений чисел Рамсея <tex>r(n,m)</tex> на практике.
* <tex>r(n,m) = r(m,n)</tex>
* <tex>r(1,m) = 1</tex>
* <tex>r(2,m) = m</tex>

===Значения чисел Рамсея===
Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, их известно довольно мало. Далее приведена таблица Станислава Радзишевского <ref>[http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1| Small Ramsey Numbers by Stanisław Radziszowski]</ref>, в которой присутствуют практически все известные числа Рамсея или же промежутки, в которых они находятся.
<center>
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
|+
!colspan="11"|Числа Рамсея
|-align="center"
! width="6%" |<tex>n,\ m</tex>
! width="6%" |<tex>1 </tex>
! width="6%" |<tex>2 </tex>
! width="6%" |<tex>3 </tex>
! width="6%" |<tex>4 </tex>
! width="6%" |<tex>5 </tex>
! width="6%" |<tex>6 </tex>
! width="6%" |<tex>7 </tex>
! width="6%" |<tex>8 </tex>
! width="6%" |<tex>9 </tex>
! width="6%" |<tex>10</tex>
|-align="center"
! <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
|-align="center"
! <tex>2 </tex>
| <tex>1 </tex>
| <tex>2 </tex>
| <tex>3 </tex>
| <tex>4 </tex>
| <tex>5 </tex>
| <tex>6 </tex>
| <tex>7 </tex>
| <tex>8 </tex>
| <tex>9 </tex>
| <tex>10</tex>
|-align="center"
! <tex>3</tex>
| <tex>1</tex>
| <tex>3</tex>
| <tex>6</tex>
| <tex>9</tex>
| <tex>14</tex>
| <tex>18</tex>
| <tex>23</tex>
| <tex>28</tex>
| <tex>36</tex>
| <tex>[40, 42]</tex>
|-align="center"
! <tex>4</tex>
| <tex>1</tex>
| <tex>4</tex>
| <tex>9</tex>
| <tex>18</tex>
| <tex>25</tex>
| <tex>[36, 41]</tex>
| <tex>[49, 61]</tex>
| <tex>[59, 84]</tex>
| <tex>[73, 115]</tex>
| <tex>[92, 149]</tex>
|-align="center"
! <tex>5</tex>
| <tex>1</tex>
| <tex>5</tex>
| <tex>14</tex>
| <tex>25</tex>
| <tex>[43, 48]</tex>
| <tex>[58, 87]</tex>
| <tex>[80, 143]</tex>
| <tex>[101, 216]</tex>
| <tex>[133, 316]</tex>
| <tex>[149, 442]</tex>
|-align="center"
! <tex>6</tex>
| <tex>1</tex>
| <tex>6</tex>
| <tex>18</tex>
| <tex>[36, 41]</tex>
| <tex>[58, 87]</tex>
| <tex>[102, 165]</tex>
| <tex>[115, 298]</tex>
| <tex>[134, 495]</tex>
| <tex>[183, 780]</tex>
| <tex>[204, 1171]</tex>
|-align="center"
! <tex>7</tex>
| <tex>1</tex>
| <tex>7</tex>
| <tex>23</tex>
| <tex>[49, 61]</tex>
| <tex>[80, 143]</tex>
| <tex>[115, 298]</tex>
| <tex>[205, 540]</tex>
| <tex>[217, 1031]</tex>
| <tex>[252, 1713]</tex>
| <tex>[292, 2826]</tex>
|-align="center"
! <tex>8</tex>
| <tex>1</tex>
| <tex>8</tex>
| <tex>28</tex>
| <tex>[56, 84]</tex>
| <tex>[101, 216]</tex>
| <tex>[127, 495]</tex>
| <tex>[217, 1031]</tex>
| <tex>[282, 1870]</tex>
| <tex>[329, 3583]</tex>
| <tex>[343, 6090]</tex>
|-align="center"
! <tex>9</tex>
| <tex>1</tex>
| <tex>9</tex>
| <tex>36</tex>
| <tex>[73, 115]</tex>
| <tex>[133, 316]</tex>
| <tex>[183, 780]</tex>
| <tex>[252, 1713]</tex>
| <tex>[329, 3583]</tex>
| <tex>[565, 6588]</tex>
| <tex>[580, 12677]</tex>
|-align="center"
! <tex>10</tex>
| <tex>1</tex>
| <tex>10</tex>
| <tex>[40, 42]</tex>
| <tex>[92, 149]</tex>
| <tex>[149, 442]</tex>
| <tex>[179, 1171]</tex>
| <tex>[289, 2826]</tex>
| <tex>[343, 6090]</tex>
| <tex>[581, 12677]</tex>
| <tex>[798, 23556]</tex>
|}
</center>

===Числа Рамсея для раскрасок в несколько цветов===
Теперь обобщим числа Рамсея на произвольное количество цветов.
{{Определение
|id=def4
|definition=
'''Число Рамсея''' <tex>r(n_1,\ldots,n_k)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в <tex>k</tex> цветов для некоторого <tex>i \in [1 \ldots k]</tex> обязательно найдётся клика на <tex>n_i</tex> вершинах с рёбрами цвета <tex>i</tex>. <tex>k,n_1,\ldots,n_k \in \mathbb N</tex>
}}

{{Теорема
|id=ter3|about=3,Теорема Рамсея для нескольких цветов
|statement=<tex>\forall k, n_1, \ldots n_k \in \mathbb N </tex> существует соответственное число Рамсея <tex>r(n_1,\ldots,n_k)</tex>, при этом <tex>r(n_1,\ldots,n_k)\leqslant r(n_1,\ldots, n_{k-2}, r(n_{k-1},\;n_k)).</tex>
|proof=
Возьмем граф из <tex>r(n_1,\ldots, n_{k-2}, r(n_{k-1}, n_k))</tex> вершин и окрасим его рёбра в <tex>k</tex> цветов. Пока что будем считать цвета <tex>k-1</tex> и <tex>k</tex> одним цветом. Тогда граф будет <tex>(k-1)</tex>-цветным. Согласно определению числа Рамсея <tex>r(n_1,\ldots,n_{k-2},r(n_{k-1},n_k))</tex>, такой граф либо содержит <tex>K_{n_i}</tex> для некоторого цвета <tex>i</tex>, такого что <tex>1\leqslant i\leqslant k-2</tex> либо <tex>K_{r(k, n_{k-1},n_k)}</tex>, окрашенный общим цветом <tex>k-1</tex> и <tex>k</tex>. В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный <tex>r(n_{k-1},n_k)</tex> — вершинный граф содержит либо <tex>K_{n_{k-1}}</tex> цвета <tex>k-1</tex>, либо <tex>K_{n_k}</tex> цвета <tex>k</tex>. Таким образом любое число Рамсея для раскраски в <tex>k</tex> цветов ограничено некоторым числом Рамсея для меньшего количества цветов, следовательно, <tex>r(n_1,\ldots,n_k)</tex> существует для любых <tex> k, n_1, \ldots n_k, \in \mathbb N </tex>, и теорема доказана.
}}

==Числа Рамсея больших размерностей==
{{Определение
|id=def5
|definition=
Пусть <tex>m,k,n_1,\ldots ,n_k \in \mathbb N</tex>, причём <tex>n_1,\ldots ,n_k \geqslant m</tex>. '''Число Рамсея''' <tex>r_m(n_1,\ldots ,n_k)</tex> — наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске <tex>m</tex>-элементных подмножеств <tex>x</tex>-элементного множества <tex>M</tex> в <tex>k</tex> цветов для некоторого <tex>i \in [1\ldots k]</tex> обязательно найдётся такое множество <tex>W_i</tex>, что <tex>|W_i|=n_i</tex> и все <tex>m</tex>-элементные подмножества множества <tex>W_i</tex> имеют цвет <tex>i</tex>. Число <tex>m</tex> называют '''размерностью''' числа Рамсея <tex>r_m(n_1,\ldots ,n_k)</tex>.
}}
Заметим, что числа Рамсея размерности <tex>2</tex> — это определённые ранее числа Рамсея для клик.

{{Определение
|id=def7|definition=
Для каждого множества <tex>M</tex> через <tex>M^k</tex> мы будем обозначать множество всех <tex>k</tex>-элементных подмножеств <tex>M</tex>.
}}
{{Теорема
|id=ter4|about=4, Теорема Рамсея для чисел больших размерностей
|statement=Пусть <tex>m,k,n_1,\ldots,n_k</tex> {{---}} натуральные числа, причем <tex>k \geqslant 2</tex>, а <tex>n_1,\ldots ,n_k \geqslant m</tex>. Тогда существует число Рамсея <tex>r_m(n_1,\ldots n_k)</tex>.
|proof=
<tex>1)</tex> Мы будем доказывать теорему по индукции. Начнем со случая <tex>k=2</tex>. Приступая к доказательству для числа <tex>r_m(n_1,n_2)</tex> мы будем считать доказанным утверждение теоремы для чисел Рамсея всех меньших размерностей и чисел Рамсея размерности <tex>m</tex> с меньшей суммой <tex>n_1+n_2</tex>. В качестве базы будем использовать случай чисел Рамсея размерности <tex>2</tex> разобранный выше. Итак, мы докажем, что <tex>r_m(n_1,n_2)-1 \leqslant p=r_{m-1}(r_m(n_1-1,n_2),r_m(n_1,n_2-1))</tex>.

Рассмотрим <tex>(p+1)</tex>-элементное множество <tex>M</tex> и выделим в нём элемент <tex>a</tex>. Пусть <tex>M_0=M \setminus \{ a \}</tex>. Пусть <tex>\rho:M^m\rightarrow \{1, 2 \} </tex> — произвольная раскраска в два цвета. Рассмотрим раскраску <tex>\rho': M_0^{m-1} \rightarrow \{1, 2\} </tex> , определённую следующим образом: для каждого множества <tex>B \in M_0^{m-1}</tex> пусть <tex>\rho'(B) = \rho(B \cup \{ a \})</tex>.
Так как <tex>|M_0|=p</tex>, либо существует <tex>r_m(n_1 — 1,n_2)</tex>-элементное подмножество <tex>M_i \subset M_0</tex>, <tex>\rho'(B)=1</tex> на всех <tex>B \in M_1^{m-1}</tex>, либо существует <tex>r_m(n_1,n_2-1)</tex>-элементное подмножество <tex>M_2 \subset M_0</tex>, <tex>\rho'(B)=2</tex> на всех <tex>B \in M_2^{m-1}</tex>. Случаи аналогичны, рассмотрим первый случай и множество <tex>M_1</tex>.
По индукционному предположен из <tex>|M_1|=r_m(n_1-1,n_2)</tex> следует, что либо существует <tex>n_1-1</tex>-элементное подмножество <tex>N_1 \subset M_1</tex>, <tex>\rho(A)=1</tex> на всех <tex>A \in N^m_1</tex>, либо существует <tex>n_2</tex>-элементное подмножество <tex>N_2 \subset M_1</tex>, <tex>\rho(A)=2</tex> на всех <tex>A \in N_2^m</tex>. Во втором случае искомое подмножество найдено (это <tex>N_2</tex>), рассмотрим первый случай и множество <tex>N=N_1 \cup \{a\}</tex>. Пусть <tex>A \in N^m</tex>. Если <tex>A \not\ni a</tex>, то <tex>A \in N_1^m</tex> и следовательно <tex>\rho(A)=1</tex>. Если же <tex>A \ni a</tex>, то множество <tex>A \setminus \{a\} \in N_1^{m-1} \subset M_1^{m-1}</tex> и поэтому <tex>\rho(A)=\rho'(A \setminus \{a \})=1</tex>. Учитывая, что <tex>|N|=n_1</tex>, мы нашли искомое подмножество и в этом случае.

<tex>2)</tex> При <tex>k>2</tex> будем вести индукцию по <tex>k</tex> с доказанной выше базой <tex>k=2</tex>. При <tex>k>2</tex> мы докажем неравенство.
<tex>r_m(n_1,\ldots ,n_k) \leqslant q=r_m(r_m(n_1,\ldots ,n_{k-1}),n_k)</tex>

Для этого мы рассмотрим множество <tex>M</tex> на <tex>q</tex> вершинах и произвольную раскраску <tex>\rho:M^m \rightarrow [1 \ldots k]</tex> в <tex>k</tex>цветов. Рассмотрим раскраску <tex>\rho':M^m \rightarrow \{0,k\}</tex>, в которой цвета <tex>1,\ldots,k-1</tex> раскраски <tex>\rho</tex> склеены в цвет <tex>0</tex>. Тогда существует либо такое подмножество <tex>M_0 \subset M</tex>, что <tex>|M_0|=r_m(n_1,\ldots ,n_{k-1})</tex> и <tex>\rho'(A)=0</tex> на всех <tex>A \in M_0^m</tex>, либо существует такое <tex>n_k</tex>-элементное подмножество <tex>M_k \subset M</tex>, что <tex>\rho(A)=\rho'(A)=k</tex> на всех <tex>A \in M^m_k</tex>. Во втором случае <tex>M_k</tex> — искомое подмножество, а в первом случае заметим, что на любом подмножестве <tex>A \in M_0^m</tex> из <tex>\rho'(A)=0</tex> следует <tex>\rho(A) \in [1 \ldots k-1]</tex>. Исходя из размера множества <tex>M_0</tex> по индукционному предположению получаем, что найдется искомое подмножество множества <tex>M</tex> для одного из цветов <tex>1,\ldots ,k-1</tex>, таким образом неравенство доказано, а из этого следует и существование числа Рамсея <tex>r_m(n_1,\ldots ,n_k)</tex>.
}}

==Числа Рамсея для произвольных графов==
Еще один способ обобщения классической теории Рамсея — замена клик на произвольные графы-шаблоны.
{{Определение
|id=def8
|definition=
Пусть <tex>H_1,H_2</tex> — графы. Число Рамсея <tex>r(H_1,H_2)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в два цвета обязательно найдется подграф, изоморфный <tex>H_1</tex> с рёбрами цвета <tex>1</tex> или подграф изоморфный <tex>H_2</tex> с рёбрами цвета <tex>2</tex>.
}}
Из результатов классической теории Рамсея становится понятно, что числа <tex>r(H_1,H_2)</tex> существуют.

{{Лемма
|id=l1|about=1|statement=Пусть <tex>m>1</tex>, а граф <tex>H</tex> таков, что <tex>v(H) \geqslant (m-1)(n-1)+1</tex> и <tex>\alpha(H) \leqslant m-1</tex>. Тогда граф <tex>H</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах.
|proof=
Зафиксируем <tex>m</tex> и проведем индукцию по <tex>n</tex>.

'''База:''' для <tex>n=1</tex> очевидно.

'''Индукционный переход:''' Пусть верно для <tex>n-1</tex>, докажем для <tex>n</tex>. Рассмотрим произвольное дерево <tex>T_n</tex> на <tex>n</tex> вершинах, пусть дерево <tex>T_{n-1}</tex> получено из <tex>T_n</tex> удалением висячей вершины. Пусть <tex>U</tex> — максимальное независимое множестве вершин графа <tex>H</tex>. Тогда <tex>|U|=\alpha(H) \leqslant m-1</tex>, следовательно <tex>v(H-U) \geqslant (m-1)(n-2)+1</tex> и очевидно <tex>\alpha(H-U) \leqslant m-1</tex>.
По индукционному предположению, граф <tex>H-U</tex> содержит в качестве подграфа дерево <tex>T_{n-1}</tex>. Пусть <tex>a</tex> — вершина этого дерева, присоединив к которой висячую вершину мы получим дерево <tex>T_n</tex>. Заметим, что множество <tex>U \cup</tex> <tex>\{a\}</tex> не является независимым ввиду максимальности <tex>U</tex>. Следовательно, вершина <tex>a</tex> смежна хотя бы с одной вершиной <tex>x \in U</tex>. Отметим, что <tex>x \not\in V(T_{n-1})</tex> и, присоединив вершину <tex>x</tex> к вершине <tex>a</tex> дерева <tex>T_{n-1}</tex>, получим дерево <tex>T_n</tex> в качестве подграфа графа <tex>H</tex>.
}}
{{Теорема
|id=ter5
|author=5
|statement=<tex>r(T_n,K_m)=(m-1)(n-1)+1</tex>, где <tex>T_n</tex> — дерево на <tex>n</tex> вершинах.
|proof=
<tex>1)</tex> Докажем, что <tex>r(T_n,K_m) \geqslant (m-1)(n-1)+1</tex>. Для этого предъявим раскраску рёбер графа <tex>K_{(m-1)(n-1)}</tex>, в которой нет ни одного связного подграфа на <tex>n</tex> вершинах с рёбрами цвета <tex>1</tex> и нет клики на <tex>m</tex> вершинах с рёбрами цвета <tex>2</tex>. Разобьём вершины графа на <tex>m-1</tex> клику по <tex>n-1</tex> вершине и покрасим все рёбра этих клик в цвет <tex>1</tex>. Тогда любой связный подграф с рёбрами цвета <tex>1</tex> содержит не более <tex>n-1</tex> вершины, в частности, нет подграфа с рёбрами цвета <tex>1</tex>, изоморфного <tex>T_n</tex>. Рёбра цвета <tex>2</tex> (то есть, все оставшиеся рёбра) образуют <tex>(m-1)</tex>-дольный граф, в котором, очевидно, нет клики на <tex>m</tex> вершинах.

<tex>2)</tex> Рассмотрим произвольную раскраску рёбер полного графа <tex>K_{(m-1)(n-1)+1}</tex> в два цвета. Предположим, что не существует клики на <tex>m</tex> вершинах с рёбрами цвета <tex>2</tex>. Тогда <tex>m>1</tex> и <tex>\alpha(G_1) \leqslant m-1</tex>. По [[#l1|лемме <tex>1</tex>]], граф <tex>G_1</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах, в частности, дерево, изоморфное <tex>T_n</tex>.
}}

==Индуцированная теорема Рамсея==
{{Определение
|id=def9
|definition=Граф <tex>H</tex> называется '''индуцированным подграфом''' (англ. ''induced subgraph'') графа <tex>G</tex> если две вершины в <tex>H</tex> соединены ребром тогда и только тогда, когда они смежны в <tex>G</tex>. }}

{{Определение
|id=def10
|definition=Пусть <tex>H</tex> — граф. Граф <tex>G</tex> будем называть '''рамсеевским графом''' для <tex>H</tex>, если при любой раскраске рёбер графа <tex>G</tex> в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G</tex> изоморфный <tex>H</tex>.}}

{{Определение
|id=def11
|definition='''Индуцированным числом Рамсея''' (англ. ''induced Ramsey number'') <tex>r_{ind}(H)</tex> для графа <tex>H</tex> будем называть минимальное число <tex>x \in \mathbb N</tex>, такое что существует рамсеевский граф для графа <tex>H</tex> на <tex>x</tex> вершинах.}}
Заметим, что при замене произвольного графа <tex>H</tex> на клику мы получаем частный случай классической теоремы Рамсея.

{{Теорема
|id=ter6
|about=6, Индуцированная теорема Рамсея
|statement=Для любого графа <tex>H</tex> существует индуцированное число Рамсея <tex>r(H)</tex>.
}}

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

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

==См. также==
*[[Раскраска графа]]
*[[Раскраска двудольного графа в два цвета]]
*[[Теорема Турана об экстремальном графе]]

== Примечания==
<references />

== Источники информации ==
* [[wikipedia:Ramsey's theorem|Wikipedia — Ramsey's theorem]]
* [[wikipedia:Ramsey theory|Wikipedia — Ramsey theory]]
* [https://vtechworks.lib.vt.edu/bitstream/handle/10919/32873/Dickson_JO_T_2011.pdf?sequence=1&isAllowed=y An Introduction to Ramsey Theory on Graphs]
* [http://people.maths.ox.ac.uk/~gouldm/ramsey.pdf Ramsey Theory]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Дискретная математика]]
[[Категория:Теория графов]]
[[Категория: Раскраски графов]]

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

2018-12-01T05:36:58Z

188.170.72.247: /* Числа Рамсея больших размерностей */

'''Теория Рамсея''' — раздел математики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок.
==Числа Рамсея==
{{Определение
|id=def1
|definition='''Клика''' (англ. ''clique'') в неориентированном графе <tex>G = (V, E)</tex> {{---}} подмножество вершин <tex>C \subseteq V</tex>, такое что для любых двух вершин в <tex>C</tex> существует ребро, их соединяющее.}}
{{Определение
|id=def2
|definition='''Число Рамсея''' <tex>r(n, m)</tex> (англ. ''Ramsey's number'') {{---}} наименьшее из таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске ребер полного графа на <tex>x</tex> вершинах в два цвета найдется клика на <tex>n</tex> вершинах с ребрами цвета <tex>1</tex> или клика на <tex>m</tex> вершинах с ребрами цвета <tex>2</tex>. }}

[[Файл:RamseyTheoryK5.png|200px|thumb|upright|Раскраска <tex>K_5</tex> без одноцветных треугольников]]
Часто определение для чисел Рамсея дается через задачу "о друзьях и незнакомцах"<ref>[https://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers| Theorem on friends and strangers]</ref>. Пусть на вечеринке каждые два человека могут быть либо друзьями, либо незнакомцами, в общем виде задачи требуется найти, какое минимальное количество людей нужно взять, чтобы хотя бы <tex>n</tex> человек были попарно знакомы, или хотя бы <tex>m</tex> человек были попарно незнакомы. Если мы переформулируем данную задачу в терминах графов, то как раз получим определение числа Рамсея <tex>r(n, m)</tex>, представленное ранее.

Чтобы получить лучшее представление природы чисел Рамсея, приведем пример. Докажем, что <tex>r(3,3) = 6</tex>. Представим, что ребра <tex>K_6</tex> раскрашены в два цвета: красный и синий. Возьмем вершину <tex>v</tex>. Данной вершине, как и всем другим, инцидентны <tex>5</tex> рёбер, тогда, согласно принципу Дирихле, хотя бы три из них одного цвета. Для определенности положим, что хотя бы <tex>3</tex> ребра, соединяющие вершину <tex>v</tex> с вершинами <tex>r</tex>, <tex>s</tex>, <tex>t</tex>, синие. Если хотя бы одно из ребер <tex>rs</tex>, <tex>rt</tex>, <tex>st</tex> синее, то в графе есть синий треугольник (полный граф на трёх вершинах), иначе, если они все красные, есть красный треугольник. Таким образом, <tex>r(3,3) \leqslant 6 </tex>.
Чтобы доказать, что <tex>r(3,3) = 6 </tex>, предъявим такую раскраску графа <tex>K_5</tex>, где нет клики на трех вершинах ни синего, ни красного цвета. Такая раскраска представлена на рисунке справа.

===Теорема Рамсея. Оценки сверху===
{{Теорема|id=ter1|about=1, Теорема Рамсея
|statement= Для любых <tex>n,m \in \mathbb N</tex> существует число <tex>r(n,m)</tex>, при этом <tex>r(n,m) \leqslant r(n,m-1)+r(n-1,m)</tex>, а также если числа <tex>r(n,m-1)</tex> и <tex>r(n-1,m)</tex> четные, то неравенство принимает вид <tex>r(n,m) \leqslant r(n,m-1)+r(n-1,m) - 1</tex> .
|proof=

<tex>1)</tex> Докажем с помощью метода математической индукции по <tex>n+m</tex>.

'''База:''' <tex>r(n,\;1) = r(1,\;n) = 1</tex>, так как граф, состоящий из одной вершины, можно считать полным графом любого цвета.

'''Индукционный переход:''' Пусть <tex>n>1</tex> и <tex>m>1</tex>. Рассмотрим полный чёрно-белый граф из <tex>r(n-1,\;m)+r(n,\;m-1)</tex> вершин. Возьмём произвольную вершину <tex>v</tex> и обозначим через <tex>M</tex> и <tex>N</tex> множества, инцидентные <tex>v</tex> в чёрном и белом подграфе соответственно. Так как в графе <tex>r(n-1,\;m)+r(n,\;m-1)=|M|+|N|+1 </tex> вершин, согласно принципу Дирихле, либо <tex>|M|\geqslant r(n-1,\;m)</tex>, либо <tex>|N|\geqslant r(n,\;m-1)</tex>. Пусть <tex>|M|\geqslant r(n-1,\;m)</tex>. Тогда либо в <tex>M</tex> существует белый <tex>K_m</tex>, что доказывает теорему, либо в <tex>M</tex> есть чёрный <tex>K_{n-1}</tex>, который вместе с <tex>v</tex> образует чёрный <tex>K_n</tex>, в этом случае теорема также доказана. Случай <tex>|N|\geqslant r(n,\;m-1)</tex> рассматривается аналогично.

<tex>2)</tex> Предположим, <tex>p=r(n-1,\;m)</tex> и <tex>q=r(n,\;m-1)</tex> оба чётны. Положим <tex>s=p+q-1</tex> и рассмотрим чёрно-белый граф из <tex>s</tex> вершин. Если <tex>d_i</tex> степень <tex>i</tex>-й вершины в чёрном подграфе, то, согласно [[Лемма о рукопожатиях|лемме о рукопожатиях]], <tex>\sum_{i=1}^s d_i</tex> — чётно. Поскольку <tex>s</tex> нечётно, должно существовать чётное <tex>d_i</tex>. Не умаляя общности, положим, что <tex>d_1</tex> чётно. Обозначим через <tex>M</tex> и <tex>N</tex> вершины, ,инцидентные вершине <tex>1</tex> в чёрном и белом подграфах соответственно. Тогда <tex>|M|=d_1</tex> и <tex>|N|=s-1-d_1</tex> оба чётны. Согласно принципу Дирихле, либо <tex>|M|\geqslant p-1</tex>, либо <tex>N\geqslant q</tex>. Так как <tex>|M|</tex> чётно, а <tex>p-1</tex> нечётно, первое неравенство можно усилить, так что либо <tex>|M|\geqslant p</tex>, либо <tex>|N|\geqslant q</tex>.

Предположим <tex>|M|\geqslant p=r(n-1,\;m)</tex>. Тогда либо подграф, порождённый множеством <tex>M</tex>, содержит белый <tex>K_m</tex> и доказательство завершено, либо он содержит чёрный <tex>K_{n-1}</tex>, который вместе с вершиной <tex>1</tex> образует чёрный <tex>K_n</tex>. Случай <tex>|N|\geqslant q=r(n,\;m-1)</tex> рассматривается аналогично.
}}
{{Утверждение|id=u1|about=1|statement=Для натуральных чисел <tex>m,n</tex> выполняется равенство <tex>r(n,m) \leqslant C_{n+m-2}^{n-1}</tex>
|proof=
Очевидно, <tex>C^{n-1}_{n+m-2}=1</tex> при <tex>n=1</tex> или <tex>m=1</tex>, как и соответствующие числа Рамсея. Индукцией по <tex>n</tex> и <tex>m</tex> при <tex>n,m \geqslant 2</tex> получаем
<tex>r(n,m) \leqslant r(n,m-1)+r(n-1,m) \leqslant C^{n-1}_{n+m-3}+C^{n-2}_{n+m-3}=C^{n-1}_{n+m-2}</tex>
}}

===Оценки снизу===

{{Теорема|id=ter2|about=2
|statement=Для любого натурального числа <tex>k \geqslant 2</tex> выполняется неравенство <tex>r(k,k) \geqslant k^{k/2}</tex>
|proof=
Так как <tex>r(2,2)=2</tex>, достаточно рассмотреть случай <tex>k \geqslant 3</tex>.
Зафиксируем множество различных помеченных вершин <tex>v_i,\ldots,v_n</tex>. Пусть <tex>g(n,k)</tex> {{---}} доля среди всех графов на вершинах <tex>v_i,\ldots,v_n</tex> тех графов, что содержат клику на <tex>k</tex> вершинах. Всего графов на наших вершинах, очевидно <tex>2^{C^2_n}</tex> (каждое из возможных рёбер <tex>C^2_n</tex> можно провести или не провести).

Посчитаем графы с кликой на <tex>k</tex> вершинах следующим образом: существует <tex>C^k_n</tex> способов выбрать <tex>k</tex> вершин для клики в нашем множестве, после чего все рёбра между ними будем считать проведенными, а остальные ребра выбираются произвольно. Таким образом, каждый граф с кликой на <tex>k</tex> вершинах будет посчитан, причём некоторые даже более одного раза. Количестве графов с кликой оказывается не более, чем <tex>C^k_n\cdot 2^{C^2_n-C^2_k}</tex>. Следовательно,

<tex>g(n,k) \leqslant \dfrac{C^k_n}{2^{C^2_k}}<\dfrac{n^k}{k!\cdot 2^{C^2_k}}</tex> <tex>(*)</tex>

Подставив <tex>n<2^{k/2}</tex> в неравенство <tex>(*)</tex> мы получаем

<tex>g(n,k)<\dfrac{2^{k^2/2}\cdot 2^{-C^2_k}}{k!}=\dfrac{2^{k/2}}{k!}<\dfrac12</tex> при <tex>k \geqslant 3</tex>

Предположим, что <tex>r(k,k)=n<2^{k/2}</tex> и разобьём все графы на <tex>n</tex> вершинах на пары <tex>G, \overline G</tex> (граф и его дополнение) Так как <tex>g(n,k)<\dfrac12</tex>, то существует пара, в которой ни <tex>G</tex>, ни <tex>\overline G</tex> не содержат клики на <tex>k</tex> вершинах. Рассмотрим раскраску рёбер <tex>K_n</tex> в два цвета, в которой ребра цвета <tex>1</tex> образуют граф <tex>G</tex>. В такой раскраске нет клики на <tex>k</tex> вершинах ни цвета <tex>1</tex>, ни цвета <tex>1</tex>, получили противоречи противоречие. Значит <tex>n</tex> было выбрано неверно. Из этого следует <tex>r(k,k) \geqslant 2^{k/2}</tex>.
}}

===Свойства чисел Рамсея===
Следующими свойствами удобно пользоваться при подсчете значений чисел Рамсея <tex>r(n,m)</tex> на практике.
* <tex>r(n,m) = r(m,n)</tex>
* <tex>r(1,m) = 1</tex>
* <tex>r(2,m) = m</tex>

===Значения чисел Рамсея===
Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, их известно довольно мало. Далее приведена таблица Станислава Радзишевского <ref>[http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1| Small Ramsey Numbers by Stanisław Radziszowski]</ref>, в которой присутствуют практически все известные числа Рамсея или же промежутки, в которых они находятся.
<center>
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
|+
!colspan="11"|Числа Рамсея
|-align="center"
! width="6%" |<tex>n,\ m</tex>
! width="6%" |<tex>1 </tex>
! width="6%" |<tex>2 </tex>
! width="6%" |<tex>3 </tex>
! width="6%" |<tex>4 </tex>
! width="6%" |<tex>5 </tex>
! width="6%" |<tex>6 </tex>
! width="6%" |<tex>7 </tex>
! width="6%" |<tex>8 </tex>
! width="6%" |<tex>9 </tex>
! width="6%" |<tex>10</tex>
|-align="center"
! <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
|-align="center"
! <tex>2 </tex>
| <tex>1 </tex>
| <tex>2 </tex>
| <tex>3 </tex>
| <tex>4 </tex>
| <tex>5 </tex>
| <tex>6 </tex>
| <tex>7 </tex>
| <tex>8 </tex>
| <tex>9 </tex>
| <tex>10</tex>
|-align="center"
! <tex>3</tex>
| <tex>1</tex>
| <tex>3</tex>
| <tex>6</tex>
| <tex>9</tex>
| <tex>14</tex>
| <tex>18</tex>
| <tex>23</tex>
| <tex>28</tex>
| <tex>36</tex>
| <tex>[40, 42]</tex>
|-align="center"
! <tex>4</tex>
| <tex>1</tex>
| <tex>4</tex>
| <tex>9</tex>
| <tex>18</tex>
| <tex>25</tex>
| <tex>[36, 41]</tex>
| <tex>[49, 61]</tex>
| <tex>[59, 84]</tex>
| <tex>[73, 115]</tex>
| <tex>[92, 149]</tex>
|-align="center"
! <tex>5</tex>
| <tex>1</tex>
| <tex>5</tex>
| <tex>14</tex>
| <tex>25</tex>
| <tex>[43, 48]</tex>
| <tex>[58, 87]</tex>
| <tex>[80, 143]</tex>
| <tex>[101, 216]</tex>
| <tex>[133, 316]</tex>
| <tex>[149, 442]</tex>
|-align="center"
! <tex>6</tex>
| <tex>1</tex>
| <tex>6</tex>
| <tex>18</tex>
| <tex>[36, 41]</tex>
| <tex>[58, 87]</tex>
| <tex>[102, 165]</tex>
| <tex>[115, 298]</tex>
| <tex>[134, 495]</tex>
| <tex>[183, 780]</tex>
| <tex>[204, 1171]</tex>
|-align="center"
! <tex>7</tex>
| <tex>1</tex>
| <tex>7</tex>
| <tex>23</tex>
| <tex>[49, 61]</tex>
| <tex>[80, 143]</tex>
| <tex>[115, 298]</tex>
| <tex>[205, 540]</tex>
| <tex>[217, 1031]</tex>
| <tex>[252, 1713]</tex>
| <tex>[292, 2826]</tex>
|-align="center"
! <tex>8</tex>
| <tex>1</tex>
| <tex>8</tex>
| <tex>28</tex>
| <tex>[56, 84]</tex>
| <tex>[101, 216]</tex>
| <tex>[127, 495]</tex>
| <tex>[217, 1031]</tex>
| <tex>[282, 1870]</tex>
| <tex>[329, 3583]</tex>
| <tex>[343, 6090]</tex>
|-align="center"
! <tex>9</tex>
| <tex>1</tex>
| <tex>9</tex>
| <tex>36</tex>
| <tex>[73, 115]</tex>
| <tex>[133, 316]</tex>
| <tex>[183, 780]</tex>
| <tex>[252, 1713]</tex>
| <tex>[329, 3583]</tex>
| <tex>[565, 6588]</tex>
| <tex>[580, 12677]</tex>
|-align="center"
! <tex>10</tex>
| <tex>1</tex>
| <tex>10</tex>
| <tex>[40, 42]</tex>
| <tex>[92, 149]</tex>
| <tex>[149, 442]</tex>
| <tex>[179, 1171]</tex>
| <tex>[289, 2826]</tex>
| <tex>[343, 6090]</tex>
| <tex>[581, 12677]</tex>
| <tex>[798, 23556]</tex>
|}
</center>

===Числа Рамсея для раскрасок в несколько цветов===
Теперь обобщим числа Рамсея на произвольное количество цветов.
{{Определение
|id=def4
|definition=
'''Число Рамсея''' <tex>r(n_1,\ldots,n_k)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в <tex>k</tex> цветов для некоторого <tex>i \in [1 \ldots k]</tex> обязательно найдётся клика на <tex>n_i</tex> вершинах с рёбрами цвета <tex>i</tex>. <tex>k,n_1,\ldots,n_k \in \mathbb N</tex>
}}

{{Теорема
|id=ter3|about=3,Теорема Рамсея для нескольких цветов
|statement=<tex>\forall k, n_1, \ldots n_k \in \mathbb N </tex> существует соответственное число Рамсея <tex>r(n_1,\ldots,n_k)</tex>, при этом <tex>r(n_1,\ldots,n_k)\leqslant r(n_1,\ldots, n_{k-2}, r(n_{k-1},\;n_k)).</tex>
|proof=
Возьмем граф из <tex>r(n_1,\ldots, n_{k-2}, r(n_{k-1}, n_k))</tex> вершин и окрасим его рёбра в <tex>k</tex> цветов. Пока что будем считать цвета <tex>k-1</tex> и <tex>k</tex> одним цветом. Тогда граф будет <tex>(k-1)</tex>-цветным. Согласно определению числа Рамсея <tex>r(n_1,\ldots,n_{k-2},r(n_{k-1},n_k))</tex>, такой граф либо содержит <tex>K_{n_i}</tex> для некоторого цвета <tex>i</tex>, такого что <tex>1\leqslant i\leqslant k-2</tex> либо <tex>K_{r(k, n_{k-1},n_k)}</tex>, окрашенный общим цветом <tex>k-1</tex> и <tex>k</tex>. В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный <tex>r(n_{k-1},n_k)</tex> — вершинный граф содержит либо <tex>K_{n_{k-1}}</tex> цвета <tex>k-1</tex>, либо <tex>K_{n_k}</tex> цвета <tex>k</tex>. Таким образом любое число Рамсея для раскраски в <tex>k</tex> цветов ограничено некоторым числом Рамсея для меньшего количества цветов, следовательно, <tex>r(n_1,\ldots,n_k)</tex> существует для любых <tex> k, n_1, \ldots n_k, \in \mathbb N </tex>, и теорема доказана.
}}

==Числа Рамсея больших размерностей==
{{Определение
|id=def5
|definition=
Пусть <tex>m,k,n_1,\ldots ,n_k \in \mathbb N</tex>, причём <tex>n_1,\ldots ,n_k \geqslant m</tex>. '''Число Рамсея''' <tex>r_m(n_1,\ldots ,n_k)</tex> — наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске <tex>m</tex>-элементных подмножеств <tex>x</tex>-элементного множества <tex>M</tex> в <tex>k</tex> цветов для некоторого <tex>i \in [1\ldots k]</tex> обязательно найдётся такое множество <tex>W_i</tex>, что <tex>|W_i|=n_i</tex> и все <tex>m</tex>-элементные подмножества множества <tex>W_i</tex> имеют цвет <tex>i</tex>. Число <tex>m</tex> называют '''размерностью''' числа Рамсея <tex>r_m(n_1,\ldots ,n_k)</tex>.
}}
Заметим, что числа Рамсея размерности <tex>2</tex> — это определённые ранее числа Рамсея для клик.

{{Определение
|id=def7|definition=
Для каждого множества <tex>M</tex> через <tex>M^k</tex> мы будем обозначать множество всех <tex>k</tex>-элементных подмножеств <tex>M</tex>.
}}
{{Теорема
|id=ter4|about=4, Теорема Рамсея для чисел больших размерностей
|statement=Пусть <tex>m,k,n_1,\ldots,n_k</tex> {{---}} натуральные числа, причем <tex>k \geqslant 2</tex>, а <tex>n_1,\ldots ,n_k \geqslant m</tex>. Тогда существует число Рамсея <tex>r_m(n_1,\ldots n_k)</tex>.
|proof=
<tex>1)</tex> Мы будем доказывать теорему по индукции. Начнем со случая <tex>k=2</tex>. Приступая к доказательству для числа <tex>r_m(n_1,n_2)</tex> мы будем считать доказанным утверждение теоремы для чисел Рамсея всех меньших размерностей и чисел Рамсея размерности <tex>m</tex> с меньшей суммой <tex>n_1+n_2</tex>. В качестве базы будем использовать случай чисел Рамсея размерности <tex>2</tex> разобранный выше. Итак, мы докажем, что <tex>r_m(n_1,n_2)-1 \leqslant p=r_{m-1}(r_m(n_1-1,n_2),r_m(n_1,n_2-1))</tex>.

Рассмотрим <tex>(p+1)</tex>-элементное множество <tex>M</tex> и выделим в нём элемент <tex>a</tex>. Пусть <tex>M_0=M \setminus \{ a \}</tex>. Пусть <tex>\rho:M^m\rightarrow \{1, 2 \} </tex> — произвольная раскраска в два цвета. Рассмотрим раскраску <tex>\rho': M_0^{m-1} \rightarrow \{1, 2\} </tex> , определённую следующим образом: для каждого множества <tex>B \in M_0^{m-1}</tex> пусть <tex>\rho'( B ) = \rho(B \cup \{ a \})</tex>.
Так как <tex>|M_0|=p</tex>, либо существует <tex>r_m(n_1 — 1,n_2)</tex>-элементное подмножество <tex>M_i \subset M_0</tex>, <tex>\rho'( В )=1</tex> на всех <tex>B \in M_1^{m-1}</tex>, либо существует <tex>r_m(n_1,n_2-1)</tex>-элементное подмножество <tex>M_2 \subset M_0</tex>, <tex>\rho'(B)=2</tex> на всех <tex>B \in M_2^{m-1}</tex>. Случаи аналогичны, рассмотрим первый случай и множество <tex>M_1</tex>.
По индукционному предположен из <tex>|M_1|=r_m(n_1-1,n_2)</tex> следует, что либо существует <tex>n_1-1</tex>-элементное подмножество <tex>N_1 \subset M_1</tex>, <tex>\rho(A)=1</tex> на всех <tex>A \in N^m_1</tex>, либо существует <tex>n_2</tex>-элементное подмножество <tex>N_2 \subset M_1</tex>, <tex>\rho(A)=2</tex> на всех <tex>A \in N_2^m</tex>. Во втором случае искомое подмножество найдено (это <tex>N_2</tex>), рассмотрим первый случай и множество <tex>N=N_1 \cup \{a\}</tex>. Пусть <tex>A \in N^m</tex>. Если <tex>A \not\ni a</tex>, то <tex>A \in N_1^m</tex> и следовательно <tex>\rho(A)=1</tex>. Если же <tex>A \ni a</tex>, то множество <tex>A \setminus \{a\} \in N_1^{m-1} \subset M_1^{m-1}</tex> и поэтому <tex>\rho(A)=\rho'(A \setminus \{a \})=1</tex>. Учитывая, что <tex>|N|=n_1</tex>, мы нашли искомое подмножество и в этом случае.

<tex>2)</tex> При <tex>k>2</tex> будем вести индукцию по <tex>k</tex> с доказанной выше базой <tex>k=2</tex>. При <tex>k>2</tex> мы докажем неравенство.
<tex>r_m(n_1,\ldots ,n_k) \leqslant q=r_m(r_m(n_1,\ldots ,n_{k-1}),n_k)</tex>

Для этого мы рассмотрим множество <tex>M</tex> на <tex>q</tex> вершинах и произвольную раскраску <tex>\rho:M^m \rightarrow [1 \ldots k]</tex> в <tex>k</tex>цветов. Рассмотрим раскраску <tex>\rho':M^m \rightarrow \{0,k\}</tex>, в которой цвета <tex>1,\ldots,k-1</tex> раскраски <tex>\rho</tex> склеены в цвет <tex>0</tex>. Тогда существует либо такое подмножество <tex>M_0 \subset M</tex>, что <tex>|M_0|=r_m(n_1,\ldots ,n_{k-1})</tex> и <tex>\rho'(A)=0</tex> на всех <tex>A \in M_0^m</tex>, либо существует такое <tex>n_k</tex>-элементное подмножество <tex>M_k \subset M</tex>, что <tex>\rho(A)=\rho'(A)=k</tex> на всех <tex>A \in M^m_k</tex>. Во втором случае <tex>M_k</tex> — искомое подмножество, а в первом случае заметим, что на любом подмножестве <tex>A \in M_0^m</tex> из <tex>\rho'(A)=0</tex> следует <tex>\rho(A) \in [1 \ldots k-1]</tex>. Исходя из размера множества <tex>M_0</tex> по индукционному предположению получаем, что найдется искомое подмножество множества <tex>M</tex> для одного из цветов <tex>1,\ldots ,k-1</tex>, таким образом неравенство доказано, а из этого следует и существование числа Рамсея <tex>r_m(n_1,\ldots ,n_k)</tex>.
}}

==Числа Рамсея для произвольных графов==
Еще один способ обобщения классической теории Рамсея — замена клик на произвольные графы-шаблоны.
{{Определение
|id=def8
|definition=
Пусть <tex>H_1,H_2</tex> — графы. Число Рамсея <tex>r(H_1,H_2)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в два цвета обязательно найдется подграф, изоморфный <tex>H_1</tex> с рёбрами цвета <tex>1</tex> или подграф изоморфный <tex>H_2</tex> с рёбрами цвета <tex>2</tex>.
}}
Из результатов классической теории Рамсея становится понятно, что числа <tex>r(H_1,H_2)</tex> существуют.

{{Лемма
|id=l1|about=1|statement=Пусть <tex>m>1</tex>, а граф <tex>H</tex> таков, что <tex>v(H) \geqslant (m-1)(n-1)+1</tex> и <tex>\alpha(H) \leqslant m-1</tex>. Тогда граф <tex>H</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах.
|proof=
Зафиксируем <tex>m</tex> и проведем индукцию по <tex>n</tex>.

'''База:''' для <tex>n=1</tex> очевидно.

'''Индукционный переход:''' Пусть верно для <tex>n-1</tex>, докажем для <tex>n</tex>. Рассмотрим произвольное дерево <tex>T_n</tex> на <tex>n</tex> вершинах, пусть дерево <tex>T_{n-1}</tex> получено из <tex>T_n</tex> удалением висячей вершины. Пусть <tex>U</tex> — максимальное независимое множестве вершин графа <tex>H</tex>. Тогда <tex>|U|=\alpha(H) \leqslant m-1</tex>, следовательно <tex>v(H-U) \geqslant (m-1)(n-2)+1</tex> и очевидно <tex>\alpha(H-U) \leqslant m-1</tex>.
По индукционному предположению, граф <tex>H-U</tex> содержит в качестве подграфа дерево <tex>T_{n-1}</tex>. Пусть <tex>a</tex> — вершина этого дерева, присоединив к которой висячую вершину мы получим дерево <tex>T_n</tex>. Заметим, что множество <tex>U \cup</tex> <tex>\{a\}</tex> не является независимым ввиду максимальности <tex>U</tex>. Следовательно, вершина <tex>a</tex> смежна хотя бы с одной вершиной <tex>x \in U</tex>. Отметим, что <tex>x \not\in V(T_{n-1})</tex> и, присоединив вершину <tex>x</tex> к вершине <tex>a</tex> дерева <tex>T_{n-1}</tex>, получим дерево <tex>T_n</tex> в качестве подграфа графа <tex>H</tex>.
}}
{{Теорема
|id=ter5
|author=5
|statement=<tex>r(T_n,K_m)=(m-1)(n-1)+1</tex>, где <tex>T_n</tex> — дерево на <tex>n</tex> вершинах.
|proof=
<tex>1)</tex> Докажем, что <tex>r(T_n,K_m) \geqslant (m-1)(n-1)+1</tex>. Для этого предъявим раскраску рёбер графа <tex>K_{(m-1)(n-1)}</tex>, в которой нет ни одного связного подграфа на <tex>n</tex> вершинах с рёбрами цвета <tex>1</tex> и нет клики на <tex>m</tex> вершинах с рёбрами цвета <tex>2</tex>. Разобьём вершины графа на <tex>m-1</tex> клику по <tex>n-1</tex> вершине и покрасим все рёбра этих клик в цвет <tex>1</tex>. Тогда любой связный подграф с рёбрами цвета <tex>1</tex> содержит не более <tex>n-1</tex> вершины, в частности, нет подграфа с рёбрами цвета <tex>1</tex>, изоморфного <tex>T_n</tex>. Рёбра цвета <tex>2</tex> (то есть, все оставшиеся рёбра) образуют <tex>(m-1)</tex>-дольный граф, в котором, очевидно, нет клики на <tex>m</tex> вершинах.

<tex>2)</tex> Рассмотрим произвольную раскраску рёбер полного графа <tex>K_{(m-1)(n-1)+1}</tex> в два цвета. Предположим, что не существует клики на <tex>m</tex> вершинах с рёбрами цвета <tex>2</tex>. Тогда <tex>m>1</tex> и <tex>\alpha(G_1) \leqslant m-1</tex>. По [[#l1|лемме <tex>1</tex>]], граф <tex>G_1</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах, в частности, дерево, изоморфное <tex>T_n</tex>.
}}

==Индуцированная теорема Рамсея==
{{Определение
|id=def9
|definition=Граф <tex>H</tex> называется '''индуцированным подграфом''' (англ. ''induced subgraph'') графа <tex>G</tex> если две вершины в <tex>H</tex> соединены ребром тогда и только тогда, когда они смежны в <tex>G</tex>. }}

{{Определение
|id=def10
|definition=Пусть <tex>H</tex> — граф. Граф <tex>G</tex> будем называть '''рамсеевским графом''' для <tex>H</tex>, если при любой раскраске рёбер графа <tex>G</tex> в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G</tex> изоморфный <tex>H</tex>.}}

{{Определение
|id=def11
|definition='''Индуцированным числом Рамсея''' (англ. ''induced Ramsey number'') <tex>r_{ind}(H)</tex> для графа <tex>H</tex> будем называть минимальное число <tex>x \in \mathbb N</tex>, такое что существует рамсеевский граф для графа <tex>H</tex> на <tex>x</tex> вершинах.}}
Заметим, что при замене произвольного графа <tex>H</tex> на клику мы получаем частный случай классической теоремы Рамсея.

{{Теорема
|id=ter6
|about=6, Индуцированная теорема Рамсея
|statement=Для любого графа <tex>H</tex> существует индуцированное число Рамсея <tex>r(H)</tex>.
}}

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

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

==См. также==
*[[Раскраска графа]]
*[[Раскраска двудольного графа в два цвета]]
*[[Теорема Турана об экстремальном графе]]

== Примечания==
<references />

== Источники информации ==
* [[wikipedia:Ramsey's theorem|Wikipedia — Ramsey's theorem]]
* [[wikipedia:Ramsey theory|Wikipedia — Ramsey theory]]
* [https://vtechworks.lib.vt.edu/bitstream/handle/10919/32873/Dickson_JO_T_2011.pdf?sequence=1&isAllowed=y An Introduction to Ramsey Theory on Graphs]
* [http://people.maths.ox.ac.uk/~gouldm/ramsey.pdf Ramsey Theory]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Дискретная математика]]
[[Категория:Теория графов]]
[[Категория: Раскраски графов]]

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

2018-12-01T05:30:00Z

188.170.72.247: /* Числа Рамсея */

'''Теория Рамсея''' — раздел математики, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок.
==Числа Рамсея==
{{Определение
|id=def1
|definition='''Клика''' (англ. ''clique'') в неориентированном графе <tex>G = (V, E)</tex> {{---}} подмножество вершин <tex>C \subseteq V</tex>, такое что для любых двух вершин в <tex>C</tex> существует ребро, их соединяющее.}}
{{Определение
|id=def2
|definition='''Число Рамсея''' <tex>r(n, m)</tex> (англ. ''Ramsey's number'') {{---}} наименьшее из таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске ребер полного графа на <tex>x</tex> вершинах в два цвета найдется клика на <tex>n</tex> вершинах с ребрами цвета <tex>1</tex> или клика на <tex>m</tex> вершинах с ребрами цвета <tex>2</tex>. }}

[[Файл:RamseyTheoryK5.png|200px|thumb|upright|Раскраска <tex>K_5</tex> без одноцветных треугольников]]
Часто определение для чисел Рамсея дается через задачу "о друзьях и незнакомцах"<ref>[https://en.wikipedia.org/wiki/Theorem_on_friends_and_strangers| Theorem on friends and strangers]</ref>. Пусть на вечеринке каждые два человека могут быть либо друзьями, либо незнакомцами, в общем виде задачи требуется найти, какое минимальное количество людей нужно взять, чтобы хотя бы <tex>n</tex> человек были попарно знакомы, или хотя бы <tex>m</tex> человек были попарно незнакомы. Если мы переформулируем данную задачу в терминах графов, то как раз получим определение числа Рамсея <tex>r(n, m)</tex>, представленное ранее.

Чтобы получить лучшее представление природы чисел Рамсея, приведем пример. Докажем, что <tex>r(3,3) = 6</tex>. Представим, что ребра <tex>K_6</tex> раскрашены в два цвета: красный и синий. Возьмем вершину <tex>v</tex>. Данной вершине, как и всем другим, инцидентны <tex>5</tex> рёбер, тогда, согласно принципу Дирихле, хотя бы три из них одного цвета. Для определенности положим, что хотя бы <tex>3</tex> ребра, соединяющие вершину <tex>v</tex> с вершинами <tex>r</tex>, <tex>s</tex>, <tex>t</tex>, синие. Если хотя бы одно из ребер <tex>rs</tex>, <tex>rt</tex>, <tex>st</tex> синее, то в графе есть синий треугольник (полный граф на трёх вершинах), иначе, если они все красные, есть красный треугольник. Таким образом, <tex>r(3,3) \leqslant 6 </tex>.
Чтобы доказать, что <tex>r(3,3) = 6 </tex>, предъявим такую раскраску графа <tex>K_5</tex>, где нет клики на трех вершинах ни синего, ни красного цвета. Такая раскраска представлена на рисунке справа.

===Теорема Рамсея. Оценки сверху===
{{Теорема|id=ter1|about=1, Теорема Рамсея
|statement= Для любых <tex>n,m \in \mathbb N</tex> существует число <tex>r(n,m)</tex>, при этом <tex>r(n,m) \leqslant r(n,m-1)+r(n-1,m)</tex>, а также если числа <tex>r(n,m-1)</tex> и <tex>r(n-1,m)</tex> четные, то неравенство принимает вид <tex>r(n,m) \leqslant r(n,m-1)+r(n-1,m) - 1</tex> .
|proof=

<tex>1)</tex> Докажем с помощью метода математической индукции по <tex>n+m</tex>.

'''База:''' <tex>r(n,\;1) = r(1,\;n) = 1</tex>, так как граф, состоящий из одной вершины, можно считать полным графом любого цвета.

'''Индукционный переход:''' Пусть <tex>n>1</tex> и <tex>m>1</tex>. Рассмотрим полный чёрно-белый граф из <tex>r(n-1,\;m)+r(n,\;m-1)</tex> вершин. Возьмём произвольную вершину <tex>v</tex> и обозначим через <tex>M</tex> и <tex>N</tex> множества, инцидентные <tex>v</tex> в чёрном и белом подграфе соответственно. Так как в графе <tex>r(n-1,\;m)+r(n,\;m-1)=|M|+|N|+1 </tex> вершин, согласно принципу Дирихле, либо <tex>|M|\geqslant r(n-1,\;m)</tex>, либо <tex>|N|\geqslant r(n,\;m-1)</tex>. Пусть <tex>|M|\geqslant r(n-1,\;m)</tex>. Тогда либо в <tex>M</tex> существует белый <tex>K_m</tex>, что доказывает теорему, либо в <tex>M</tex> есть чёрный <tex>K_{n-1}</tex>, который вместе с <tex>v</tex> образует чёрный <tex>K_n</tex>, в этом случае теорема также доказана. Случай <tex>|N|\geqslant r(n,\;m-1)</tex> рассматривается аналогично.

<tex>2)</tex> Предположим, <tex>p=r(n-1,\;m)</tex> и <tex>q=r(n,\;m-1)</tex> оба чётны. Положим <tex>s=p+q-1</tex> и рассмотрим чёрно-белый граф из <tex>s</tex> вершин. Если <tex>d_i</tex> степень <tex>i</tex>-й вершины в чёрном подграфе, то, согласно [[Лемма о рукопожатиях|лемме о рукопожатиях]], <tex>\sum_{i=1}^s d_i</tex> — чётно. Поскольку <tex>s</tex> нечётно, должно существовать чётное <tex>d_i</tex>. Не умаляя общности, положим, что <tex>d_1</tex> чётно. Обозначим через <tex>M</tex> и <tex>N</tex> вершины, ,инцидентные вершине <tex>1</tex> в чёрном и белом подграфах соответственно. Тогда <tex>|M|=d_1</tex> и <tex>|N|=s-1-d_1</tex> оба чётны. Согласно принципу Дирихле, либо <tex>|M|\geqslant p-1</tex>, либо <tex>N\geqslant q</tex>. Так как <tex>|M|</tex> чётно, а <tex>p-1</tex> нечётно, первое неравенство можно усилить, так что либо <tex>|M|\geqslant p</tex>, либо <tex>|N|\geqslant q</tex>.

Предположим <tex>|M|\geqslant p=r(n-1,\;m)</tex>. Тогда либо подграф, порождённый множеством <tex>M</tex>, содержит белый <tex>K_m</tex> и доказательство завершено, либо он содержит чёрный <tex>K_{n-1}</tex>, который вместе с вершиной <tex>1</tex> образует чёрный <tex>K_n</tex>. Случай <tex>|N|\geqslant q=r(n,\;m-1)</tex> рассматривается аналогично.
}}
{{Утверждение|id=u1|about=1|statement=Для натуральных чисел <tex>m,n</tex> выполняется равенство <tex>r(n,m) \leqslant C_{n+m-2}^{n-1}</tex>
|proof=
Очевидно, <tex>C^{n-1}_{n+m-2}=1</tex> при <tex>n=1</tex> или <tex>m=1</tex>, как и соответствующие числа Рамсея. Индукцией по <tex>n</tex> и <tex>m</tex> при <tex>n,m \geqslant 2</tex> получаем
<tex>r(n,m) \leqslant r(n,m-1)+r(n-1,m) \leqslant C^{n-1}_{n+m-3}+C^{n-2}_{n+m-3}=C^{n-1}_{n+m-2}</tex>
}}

===Оценки снизу===

{{Теорема|id=ter2|about=2
|statement=Для любого натурального числа <tex>k \geqslant 2</tex> выполняется неравенство <tex>r(k,k) \geqslant k^{k/2}</tex>
|proof=
Так как <tex>r(2,2)=2</tex>, достаточно рассмотреть случай <tex>k \geqslant 3</tex>.
Зафиксируем множество различных помеченных вершин <tex>v_i,\ldots,v_n</tex>. Пусть <tex>g(n,k)</tex> {{---}} доля среди всех графов на вершинах <tex>v_i,\ldots,v_n</tex> тех графов, что содержат клику на <tex>k</tex> вершинах. Всего графов на наших вершинах, очевидно <tex>2^{C^2_n}</tex> (каждое из возможных рёбер <tex>C^2_n</tex> можно провести или не провести).

Посчитаем графы с кликой на <tex>k</tex> вершинах следующим образом: существует <tex>C^k_n</tex> способов выбрать <tex>k</tex> вершин для клики в нашем множестве, после чего все рёбра между ними будем считать проведенными, а остальные ребра выбираются произвольно. Таким образом, каждый граф с кликой на <tex>k</tex> вершинах будет посчитан, причём некоторые даже более одного раза. Количестве графов с кликой оказывается не более, чем <tex>C^k_n\cdot 2^{C^2_n-C^2_k}</tex>. Следовательно,

<tex>g(n,k) \leqslant \dfrac{C^k_n}{2^{C^2_k}}<\dfrac{n^k}{k!\cdot 2^{C^2_k}}</tex> <tex>(*)</tex>

Подставив <tex>n<2^{k/2}</tex> в неравенство <tex>(*)</tex> мы получаем

<tex>g(n,k)<\dfrac{2^{k^2/2}\cdot 2^{-C^2_k}}{k!}=\dfrac{2^{k/2}}{k!}<\dfrac12</tex> при <tex>k \geqslant 3</tex>

Предположим, что <tex>r(k,k)=n<2^{k/2}</tex> и разобьём все графы на <tex>n</tex> вершинах на пары <tex>G, \overline G</tex> (граф и его дополнение) Так как <tex>g(n,k)<\dfrac12</tex>, то существует пара, в которой ни <tex>G</tex>, ни <tex>\overline G</tex> не содержат клики на <tex>k</tex> вершинах. Рассмотрим раскраску рёбер <tex>K_n</tex> в два цвета, в которой ребра цвета <tex>1</tex> образуют граф <tex>G</tex>. В такой раскраске нет клики на <tex>k</tex> вершинах ни цвета <tex>1</tex>, ни цвета <tex>1</tex>, получили противоречи противоречие. Значит <tex>n</tex> было выбрано неверно. Из этого следует <tex>r(k,k) \geqslant 2^{k/2}</tex>.
}}

===Свойства чисел Рамсея===
Следующими свойствами удобно пользоваться при подсчете значений чисел Рамсея <tex>r(n,m)</tex> на практике.
* <tex>r(n,m) = r(m,n)</tex>
* <tex>r(1,m) = 1</tex>
* <tex>r(2,m) = m</tex>

===Значения чисел Рамсея===
Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, их известно довольно мало. Далее приведена таблица Станислава Радзишевского <ref>[http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1| Small Ramsey Numbers by Stanisław Radziszowski]</ref>, в которой присутствуют практически все известные числа Рамсея или же промежутки, в которых они находятся.
<center>
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
|+
!colspan="11"|Числа Рамсея
|-align="center"
! width="6%" |<tex>n,\ m</tex>
! width="6%" |<tex>1 </tex>
! width="6%" |<tex>2 </tex>
! width="6%" |<tex>3 </tex>
! width="6%" |<tex>4 </tex>
! width="6%" |<tex>5 </tex>
! width="6%" |<tex>6 </tex>
! width="6%" |<tex>7 </tex>
! width="6%" |<tex>8 </tex>
! width="6%" |<tex>9 </tex>
! width="6%" |<tex>10</tex>
|-align="center"
! <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
| <tex>1 </tex>
|-align="center"
! <tex>2 </tex>
| <tex>1 </tex>
| <tex>2 </tex>
| <tex>3 </tex>
| <tex>4 </tex>
| <tex>5 </tex>
| <tex>6 </tex>
| <tex>7 </tex>
| <tex>8 </tex>
| <tex>9 </tex>
| <tex>10</tex>
|-align="center"
! <tex>3</tex>
| <tex>1</tex>
| <tex>3</tex>
| <tex>6</tex>
| <tex>9</tex>
| <tex>14</tex>
| <tex>18</tex>
| <tex>23</tex>
| <tex>28</tex>
| <tex>36</tex>
| <tex>[40, 42]</tex>
|-align="center"
! <tex>4</tex>
| <tex>1</tex>
| <tex>4</tex>
| <tex>9</tex>
| <tex>18</tex>
| <tex>25</tex>
| <tex>[36, 41]</tex>
| <tex>[49, 61]</tex>
| <tex>[59, 84]</tex>
| <tex>[73, 115]</tex>
| <tex>[92, 149]</tex>
|-align="center"
! <tex>5</tex>
| <tex>1</tex>
| <tex>5</tex>
| <tex>14</tex>
| <tex>25</tex>
| <tex>[43, 48]</tex>
| <tex>[58, 87]</tex>
| <tex>[80, 143]</tex>
| <tex>[101, 216]</tex>
| <tex>[133, 316]</tex>
| <tex>[149, 442]</tex>
|-align="center"
! <tex>6</tex>
| <tex>1</tex>
| <tex>6</tex>
| <tex>18</tex>
| <tex>[36, 41]</tex>
| <tex>[58, 87]</tex>
| <tex>[102, 165]</tex>
| <tex>[115, 298]</tex>
| <tex>[134, 495]</tex>
| <tex>[183, 780]</tex>
| <tex>[204, 1171]</tex>
|-align="center"
! <tex>7</tex>
| <tex>1</tex>
| <tex>7</tex>
| <tex>23</tex>
| <tex>[49, 61]</tex>
| <tex>[80, 143]</tex>
| <tex>[115, 298]</tex>
| <tex>[205, 540]</tex>
| <tex>[217, 1031]</tex>
| <tex>[252, 1713]</tex>
| <tex>[292, 2826]</tex>
|-align="center"
! <tex>8</tex>
| <tex>1</tex>
| <tex>8</tex>
| <tex>28</tex>
| <tex>[56, 84]</tex>
| <tex>[101, 216]</tex>
| <tex>[127, 495]</tex>
| <tex>[217, 1031]</tex>
| <tex>[282, 1870]</tex>
| <tex>[329, 3583]</tex>
| <tex>[343, 6090]</tex>
|-align="center"
! <tex>9</tex>
| <tex>1</tex>
| <tex>9</tex>
| <tex>36</tex>
| <tex>[73, 115]</tex>
| <tex>[133, 316]</tex>
| <tex>[183, 780]</tex>
| <tex>[252, 1713]</tex>
| <tex>[329, 3583]</tex>
| <tex>[565, 6588]</tex>
| <tex>[580, 12677]</tex>
|-align="center"
! <tex>10</tex>
| <tex>1</tex>
| <tex>10</tex>
| <tex>[40, 42]</tex>
| <tex>[92, 149]</tex>
| <tex>[149, 442]</tex>
| <tex>[179, 1171]</tex>
| <tex>[289, 2826]</tex>
| <tex>[343, 6090]</tex>
| <tex>[581, 12677]</tex>
| <tex>[798, 23556]</tex>
|}
</center>

===Числа Рамсея для раскрасок в несколько цветов===
Теперь обобщим числа Рамсея на произвольное количество цветов.
{{Определение
|id=def4
|definition=
'''Число Рамсея''' <tex>r(n_1,\ldots,n_k)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в <tex>k</tex> цветов для некоторого <tex>i \in [1 \ldots k]</tex> обязательно найдётся клика на <tex>n_i</tex> вершинах с рёбрами цвета <tex>i</tex>. <tex>k,n_1,\ldots,n_k \in \mathbb N</tex>
}}

{{Теорема
|id=ter3|about=3,Теорема Рамсея для нескольких цветов
|statement=<tex>\forall k, n_1, \ldots n_k \in \mathbb N </tex> существует соответственное число Рамсея <tex>r(n_1,\ldots,n_k)</tex>, при этом <tex>r(n_1,\ldots,n_k)\leqslant r(n_1,\ldots, n_{k-2}, r(n_{k-1},\;n_k)).</tex>
|proof=
Возьмем граф из <tex>r(n_1,\ldots, n_{k-2}, r(n_{k-1}, n_k))</tex> вершин и окрасим его рёбра в <tex>k</tex> цветов. Пока что будем считать цвета <tex>k-1</tex> и <tex>k</tex> одним цветом. Тогда граф будет <tex>(k-1)</tex>-цветным. Согласно определению числа Рамсея <tex>r(n_1,\ldots,n_{k-2},r(n_{k-1},n_k))</tex>, такой граф либо содержит <tex>K_{n_i}</tex> для некоторого цвета <tex>i</tex>, такого что <tex>1\leqslant i\leqslant k-2</tex> либо <tex>K_{r(k, n_{k-1},n_k)}</tex>, окрашенный общим цветом <tex>k-1</tex> и <tex>k</tex>. В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный <tex>r(n_{k-1},n_k)</tex> — вершинный граф содержит либо <tex>K_{n_{k-1}}</tex> цвета <tex>k-1</tex>, либо <tex>K_{n_k}</tex> цвета <tex>k</tex>. Таким образом любое число Рамсея для раскраски в <tex>k</tex> цветов ограничено некоторым числом Рамсея для меньшего количества цветов, следовательно, <tex>r(n_1,\ldots,n_k)</tex> существует для любых <tex> k, n_1, \ldots n_k, \in \mathbb N </tex>, и теорема доказана.
}}

==Числа Рамсея больших размерностей==
{{Определение
|id=def5
|definition=
Пусть <tex>m,k,n_1,\ldots ,n_k \in \mathbb N</tex>, причём <tex>n_1,\ldots ,n_k \geqslant m</tex>. '''Число Рамсея''' <tex>r_m(n_1,\ldots ,n_k)</tex> — наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске <tex>m</tex>-элементных подмножеств <tex>x</tex>-элементного множества <tex>M</tex> в <tex>k</tex> цветов для некоторого <tex>i \in [1\ldots k]</tex> обязательно найдётся такое множество <tex>W_i</tex>, что <tex>|W_i|=n_i</tex> и все <tex>m</tex>-элементные подмножества множества <tex>W_i</tex> имеют цвет <tex>i</tex>. Число <tex>m</tex> называют '''размерностью''' числа Рамсея <tex>r_m(n_1,\ldots ,n_k)</tex>.
}}
Заметим, что числа Рамсея размерности <tex>2</tex> — это определённые ранее числа Рамсея для клик.

{{Определение
|id=def7|definition=
Для каждого множества <tex>M</tex> через <tex>M^k</tex> мы будем обозначать множество всех <tex>k</tex>-элементных подмножеств <tex>M</tex>.
}}
{{Теорема
|id=ter4|about=4, Теорема Рамсея для чисел больших размерностей
|statement=Пусть <tex>m,k,n_1,\ldots,n_k</tex> {{---}} натуральные числа, причем <tex>k \geqslant 2</tex>, а <tex>n_1,\ldots ,n_k \geqslant m</tex>. Тогда существует число Рамсея <tex>r_m(n_1,\ldots n_k)</tex>.
|proof=
<tex>1)</tex> Мы будем доказывать теорему по индукции. Начнем со случая <tex>k=2</tex>. Приступая к доказательству для числа <tex>r_m(n_1,n_2)</tex> мы будем считать доказанным утверждение теоремы для чисел Рамсея всех меньших размерностей и чисел Рамсея размерности <tex>m</tex> с меньшей суммой <tex>n_1+n_2</tex>. В качестве базы будем использовать случай чисел Рамсея размерности <tex>2</tex> разобранный выше. Итак, мы докажем, что <tex>r_m(n_1,n_2)-1 \leqslant p=r_{m-1}(r_m(n_1-1,n_2),r_m(n_1,n_2-1))</tex>.

Рассмотрим <tex>(p+1)</tex>-элементное множество <tex>M</tex> и выделим в нём элемент <tex>a</tex>. Пусть <tex>M_0=M \setminus \{ a \}</tex>. Пусть <tex>\rho:M^m\rightarrow \{1, 2 \} </tex> — произвольная раскраска в два цвета. Рассмотрим раскраску <tex>\rho': M_0^{m-1} \rightarrow \{1, 2\} </tex> , определённую следующим образом: для каждого множества <tex>B \in M_0^{m-1}</tex> пусть <tex>\rho'( B ) = \rho(B \cup \{ a \})</tex>.
Так как <tex>|M_0|=p</tex>, либо существует <tex>r_m(n_1 — 1,n_2)</tex>-элементное подмножество <tex>M_i \subset M_0</tex>, для которого <tex>\rho'(В)=1</tex> на всех <tex>B \in M_1^{m-1}</tex>, либо существует <tex>r_m(n_1,n_2-1)</tex>-элементное подмножество <tex>M_2 \subset M_0</tex>, для которого <tex>\rho'(B)=2</tex> на всех <tex>B \in M_2^{m-1}</tex>. Случаи аналогичны, рассмотрим первый случай и множество <tex>M_1</tex>.
По индукционному предположен из <tex>|M_1|=r_m(n_1-1,n_2)</tex> следует, что либо существует <tex>n_1-1</tex>-элементное подмножество <tex>N_1 \subset M_1</tex>, для которого <tex>\rho(A)=1</tex> на всех <tex>A \in N^m_1</tex>, либо существует <tex>n_2</tex>-элементное подмножество <tex>N_2 \subset M_1</tex>, для которого <tex>\rho(A)=2</tex> на всех <tex>A \in N_2^m</tex>. Во втором случае искомое подмножество найдено (это <tex>N_2</tex>), рассмотрим первый случай и множество <tex>N=N_1 \cup \{a\}</tex>. Пусть <tex>A \in N^m</tex>. Если <tex>A \not\ni a</tex>, то <tex>A \in N_1^m</tex> и следовательно <tex>\rho(A)=1</tex>. Если же <tex>A \ni a</tex>, то множество <tex>A \setminus \{a\} \in N_1^{m-1} \subset M_1^{m-1}</tex> и поэтому <tex>\rho(A)=\rho'(A \setminus \{a \})=1</tex>. Учитывая, что <tex>|N|=n_1</tex>, мы нашли искомое подмножество и в этом случае.

<tex>2)</tex> При <tex>k>2</tex> будем вести индукцию по <tex>k</tex> с доказанной выше базой <tex>k=2</tex>. При <tex>k>2</tex> мы докажем неравенство.
<tex>r_m(n_1,\ldots ,n_k) \leqslant q=r_m(r_m(n_1,\ldots ,n_{k-1}),n_k)</tex>

Для этого мы рассмотрим множество <tex>M</tex> на <tex>q</tex> вершинах и произвольную раскраску <tex>\rho:M^m \rightarrow [1 \ldots k]</tex> в <tex>k</tex>цветов. Рассмотрим раскраску <tex>\rho':M^m \rightarrow \{0,k\}</tex>, в которой цвета <tex>1,\ldots,k-1</tex> раскраски <tex>\rho</tex> склеены в цвет <tex>0</tex>. Тогда существует либо такое подмножество <tex>M_0 \subset M</tex>, что <tex>|M_0|=r_m(n_1,\ldots ,n_{k-1})</tex> и <tex>\rho'(A)=0</tex> на всех <tex>A \in M_0^m</tex>, либо существует такое <tex>n_k</tex>-элементное подмножество <tex>M_k \subset M</tex>, что <tex>\rho(A)=\rho'(A)=k</tex> на всех <tex>A \in M^m_k</tex>. Во втором случае <tex>M_k</tex> — искомое подмножество, а в первом случае заметим, что на любом подмножестве <tex>A \in M_0^m</tex> из <tex>\rho'(A)=0</tex> следует <tex>\rho(A) \in [1 \ldots k-1]</tex>. Исходя из размера множества <tex>M_0</tex> по индукционному предположению получаем, что найдется искомое подмножество множества <tex>M</tex> для одного из цветов <tex>1,\ldots ,k-1</tex>, таким образом неравенство доказано, а из этого следует и существование числа Рамсея <tex>r_m(n_1,\ldots ,n_k)</tex>.
}}

==Числа Рамсея для произвольных графов==
Еще один способ обобщения классической теории Рамсея — замена клик на произвольные графы-шаблоны.
{{Определение
|id=def8
|definition=
Пусть <tex>H_1,H_2</tex> — графы. Число Рамсея <tex>r(H_1,H_2)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в два цвета обязательно найдется подграф, изоморфный <tex>H_1</tex> с рёбрами цвета <tex>1</tex> или подграф изоморфный <tex>H_2</tex> с рёбрами цвета <tex>2</tex>.
}}
Из результатов классической теории Рамсея становится понятно, что числа <tex>r(H_1,H_2)</tex> существуют.

{{Лемма
|id=l1|about=1|statement=Пусть <tex>m>1</tex>, а граф <tex>H</tex> таков, что <tex>v(H) \geqslant (m-1)(n-1)+1</tex> и <tex>\alpha(H) \leqslant m-1</tex>. Тогда граф <tex>H</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах.
|proof=
Зафиксируем <tex>m</tex> и проведем индукцию по <tex>n</tex>.

'''База:''' для <tex>n=1</tex> очевидно.

'''Индукционный переход:''' Пусть верно для <tex>n-1</tex>, докажем для <tex>n</tex>. Рассмотрим произвольное дерево <tex>T_n</tex> на <tex>n</tex> вершинах, пусть дерево <tex>T_{n-1}</tex> получено из <tex>T_n</tex> удалением висячей вершины. Пусть <tex>U</tex> — максимальное независимое множестве вершин графа <tex>H</tex>. Тогда <tex>|U|=\alpha(H) \leqslant m-1</tex>, следовательно <tex>v(H-U) \geqslant (m-1)(n-2)+1</tex> и очевидно <tex>\alpha(H-U) \leqslant m-1</tex>.
По индукционному предположению, граф <tex>H-U</tex> содержит в качестве подграфа дерево <tex>T_{n-1}</tex>. Пусть <tex>a</tex> — вершина этого дерева, присоединив к которой висячую вершину мы получим дерево <tex>T_n</tex>. Заметим, что множество <tex>U \cup</tex> <tex>\{a\}</tex> не является независимым ввиду максимальности <tex>U</tex>. Следовательно, вершина <tex>a</tex> смежна хотя бы с одной вершиной <tex>x \in U</tex>. Отметим, что <tex>x \not\in V(T_{n-1})</tex> и, присоединив вершину <tex>x</tex> к вершине <tex>a</tex> дерева <tex>T_{n-1}</tex>, получим дерево <tex>T_n</tex> в качестве подграфа графа <tex>H</tex>.
}}
{{Теорема
|id=ter5
|author=5
|statement=<tex>r(T_n,K_m)=(m-1)(n-1)+1</tex>, где <tex>T_n</tex> — дерево на <tex>n</tex> вершинах.
|proof=
<tex>1)</tex> Докажем, что <tex>r(T_n,K_m) \geqslant (m-1)(n-1)+1</tex>. Для этого предъявим раскраску рёбер графа <tex>K_{(m-1)(n-1)}</tex>, в которой нет ни одного связного подграфа на <tex>n</tex> вершинах с рёбрами цвета <tex>1</tex> и нет клики на <tex>m</tex> вершинах с рёбрами цвета <tex>2</tex>. Разобьём вершины графа на <tex>m-1</tex> клику по <tex>n-1</tex> вершине и покрасим все рёбра этих клик в цвет <tex>1</tex>. Тогда любой связный подграф с рёбрами цвета <tex>1</tex> содержит не более <tex>n-1</tex> вершины, в частности, нет подграфа с рёбрами цвета <tex>1</tex>, изоморфного <tex>T_n</tex>. Рёбра цвета <tex>2</tex> (то есть, все оставшиеся рёбра) образуют <tex>(m-1)</tex>-дольный граф, в котором, очевидно, нет клики на <tex>m</tex> вершинах.

<tex>2)</tex> Рассмотрим произвольную раскраску рёбер полного графа <tex>K_{(m-1)(n-1)+1}</tex> в два цвета. Предположим, что не существует клики на <tex>m</tex> вершинах с рёбрами цвета <tex>2</tex>. Тогда <tex>m>1</tex> и <tex>\alpha(G_1) \leqslant m-1</tex>. По [[#l1|лемме <tex>1</tex>]], граф <tex>G_1</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах, в частности, дерево, изоморфное <tex>T_n</tex>.
}}

==Индуцированная теорема Рамсея==
{{Определение
|id=def9
|definition=Граф <tex>H</tex> называется '''индуцированным подграфом''' (англ. ''induced subgraph'') графа <tex>G</tex> если две вершины в <tex>H</tex> соединены ребром тогда и только тогда, когда они смежны в <tex>G</tex>. }}

{{Определение
|id=def10
|definition=Пусть <tex>H</tex> — граф. Граф <tex>G</tex> будем называть '''рамсеевским графом''' для <tex>H</tex>, если при любой раскраске рёбер графа <tex>G</tex> в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G</tex> изоморфный <tex>H</tex>.}}

{{Определение
|id=def11
|definition='''Индуцированным числом Рамсея''' (англ. ''induced Ramsey number'') <tex>r_{ind}(H)</tex> для графа <tex>H</tex> будем называть минимальное число <tex>x \in \mathbb N</tex>, такое что существует рамсеевский граф для графа <tex>H</tex> на <tex>x</tex> вершинах.}}
Заметим, что при замене произвольного графа <tex>H</tex> на клику мы получаем частный случай классической теоремы Рамсея.

{{Теорема
|id=ter6
|about=6, Индуцированная теорема Рамсея
|statement=Для любого графа <tex>H</tex> существует индуцированное число Рамсея <tex>r(H)</tex>.
}}

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

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

==См. также==
*[[Раскраска графа]]
*[[Раскраска двудольного графа в два цвета]]
*[[Теорема Турана об экстремальном графе]]

== Примечания==
<references />

== Источники информации ==
* [[wikipedia:Ramsey's theorem|Wikipedia — Ramsey's theorem]]
* [[wikipedia:Ramsey theory|Wikipedia — Ramsey theory]]
* [https://vtechworks.lib.vt.edu/bitstream/handle/10919/32873/Dickson_JO_T_2011.pdf?sequence=1&isAllowed=y An Introduction to Ramsey Theory on Graphs]
* [http://people.maths.ox.ac.uk/~gouldm/ramsey.pdf Ramsey Theory]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Дискретная математика]]
[[Категория:Теория графов]]
[[Категория: Раскраски графов]]