Изменения

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

|definition='''КликойКлика''' (англ. ''clique'') в [[Основные определения теории графов#Неориентированные графы|неориентированном графе ]] <tex>G = (V, E)</tex> называется {{---}} подмножество [[Основные определения теории графов#Неориентированные графы|вершин ]] <tex>C \subseteq V</tex>, такое что для любых двух различных вершин в <tex>C</tex> существует [[Основные определения теории графов#def_edge_und|ребро]], их соединяющее. Другими словами, клика графа <tex>G(V, E)</tex> {{---}} [[Основные определения теории графов#defFullGraph|полный]] подграф графа <tex>G(V, E)</tex>.}} 

|definition='''Числом Число Рамсея''' <tex>r(m, n)</tex>, где <tex>m, n \in \mathbb N )</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>. }}Существует и другое определение для чисел Рамсея.{{Определение|id=def15|definition='''Число Рамсея''' <tex>r(n, m)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что для любого графа <tex>G</tex> на <tex>x</tex> вершинах либо в <tex>G</tex> найдется <tex>K_n</tex>, либо в <tex>\overline G</tex> найдется граф <tex>K_m</tex>. }}[[Файл:RamseyTheoryK5.png|200px|thumb|upright|Раскраска <tex>K_5</tex> без одноцветных треугольников]]Несложно доказать, что данные определения эквивалентны. Достаточно показать, что раскрашенному в два цвета графу <tex>K_n</tex>, можно однозначно поставить в соответствие граф <tex>G</tex> на <tex>n</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>, где нет клики на трех вершинах ни синего, ни красного цвета. Такая раскраска представлена на рисунке справа. Понятно, что предъявлять отдельные раскраски для <tex> K_4</tex>, <tex>K_3</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) \le 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) \le leqslant r(n,m-1)+r(n-1,m) - 1</tex> .

<tex>1)</tex> # Докажем с помощью метода математической индукции по <tex>n+m</tex>. <br>'''База:''' <tex>r(n,\;1) = r(1,\;n) = 1</tex>, так как 1-вершинный граф , состоящий из одной вершины, можно считать полным графом любого цвета. <br>'''Индукционный переход:''' Пусть <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>ts=p+q-1</tex> и рассмотрим чёрно-белый граф из <tex>ts</tex> вершин. Если <tex>d_i</tex> степень <tex>i</tex>-й вершины в чёрном подграфе, то, согласно [[Лемма о рукопожатиях|лемме о рукопожатиях]], <tex>\sum_sum\limits_{i=1}^t s d_i</tex> — чётно. Поскольку <tex>ts</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|=ts-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>. Предположим <br> Далее проводим рассуждения, аналогичные тем, что присутствуют в первом пункте теоремы. Таким образом, <tex>|M|\geqslant p=r(n-1,\;m)</tex>. Тогда либо подграф\leqslant r(n, порождённый множеством <tex>M</tex>, содержит белый <tex>K_m</tex> и доказательство завершено, либо он содержит чёрный <tex>K_{nm-1}</tex>, который вместе с вершиной 1 образует чёрный <tex>K_n</tex>. Случай <tex>|N|\geqslant q=)+r(n-1,\;m) -1)</tex> рассматривается аналогично.

{{Утверждение|id=u1|about=1|statement=Для натуральных чисел <tex>m,n</tex> выполняется равенство <tex>r(n,m) \le leqslant C_{n+m-2}^{n-1}</tex>

Очевидно, <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 \ge geqslant 2</tex> получаем <tex>r(n,m) \le leqslant r(n,m-1)+r(n-1,m) \le 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 \ge geqslant 2</tex> выполняется неравенство <tex>r(k,k) \ge kgeqslant 2^{k/2}</tex>

Так как <tex>r(2,2)=2</tex>, достаточно рассмотреть случай <tex>k \ge geqslant 3</tex>.Зафиксируем множество различных помеченных вершин <tex>v_i,...,v_n</tex>. Пусть <tex>g(n,k)</tex> — деля доля среди всех помеченных графов на вершинах <tex>v_i,...,v_nn</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) \le leqslant \fracdfrac{C^k_n\cdot 2^{C^2_n-C^2_k}}{2^{C^2_n}}=\dfrac{n!}{(n-k)!\cdot k! \cdot 2^{C^2_k}}=\dfrac{(n-k+1)\cdot(n-k+2)\cdot\ldots \cdot(n-1)\cdot n}{k! \cdot 2^{C^2_k}}<\fracdfrac{n^k}{k!\cdot 2^{C^2_k}}</tex> '''<tex>(*''')</tex>

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

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

Предположим, что <tex>r(k,k)=n<2^{k/2}</tex> и разобьём все графы на <tex>n </tex> вершинах на пары <tex>\langle G, \overline G\rangle</tex> (граф и его дополнение) . Так как <tex>g(n,k)<\frac12dfrac12</tex>, то существует пара<tex>\langle G, \overline G \rangle</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>2</tex>, получили противоречие. Следовательно Значит <tex>n</tex> было выбрано неверно. Из этого следует <tex>r(k,k) \ge geqslant 2^{k/2}</tex>.

Так, если ассоциировать 13 вершин графа ===Свойства чисел Рамсея===Следующими свойствами удобно пользоваться при подсчете значений чисел Рамсея <tex>Rr(3n,5m)</tex> с элементами поля вычетов по модулю 13на практике.* <tex>r(n, то рёбра будут соединять вычеты разность которых — кубический вычет по модулю 13 m) = r(то естьm, n)</tex>* <tex>r(1, 5m) = 1</tex>* <tex>r(2, 8 или 12m).= m</tex>

Если считать 17 вершин графа ===Значения чисел Рамсея===Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, их известно довольно мало. Далее приведена таблица Станислава Радзишевского, в которой присутствуют практически все известные числа Рамсея или же промежутки, в которых они находятся.<center>{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+!colspan="11"|Числа Рамсея|-align="center"! width="6%" |<font color="black"><tex>n,\ m</tex></font>! width="6%" |<font color="black"><tex>1 </tex></font>! width="6%" |<font color="black"><tex>2 </tex></font>! width="6%" |<font color="black"><tex>3 </tex></font>! width="6%" |<font color="black"><tex>4 </tex></font>! width="6%" |<font color="black"><tex>5 </tex></font>! width="6%" |<font color="black"><tex>6 </tex></font>! width="6%" |<font color="black"><tex>7 </tex></font>! width="6%" |<font color="black"><tex>8 </tex></font>! width="6%" |<font color="black"><tex>9 </tex></font>! width="6%" |<font color="black"><tex>10</tex></font>|-align="center"! <font color="black"><tex>1 </tex></font>| <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"! <font color="black"><tex>2 </tex></font>| <tex>1 </tex>| <tex>2 </tex>| <tex>3 </tex>| <tex>R(4</tex>| <tex>5 </tex>| <tex>6 </tex>| <tex>7 </tex>| <tex>8 </tex>| <tex>9 </tex>| <tex>10</tex>|-align="center"! <font color="black"><tex>3</tex></font>| <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"! <font color="black"><tex>4</tex></font>| <tex>1</tex>| <tex>4)</tex> элементами поля вычетов по модулю 17| <tex>9</tex>| <tex>18</tex>| <tex>25</tex>| <tex>[36, то рёбра будут соединять вычеты41]</tex>| <tex>[49, 61]</tex>| <tex>[59, разность которых — квадратичный вычет по модулю 17 (то есть84]</tex>| <tex>[73, 115]</tex>| <tex>[92, 149]</tex>|-align="center"! <font color="black"><tex>5</tex></font>| <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"! <font color="black"><tex>6</tex></font>| <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"! <font color="black"><tex>7</tex></font>| <tex>1</tex>| <tex>7</tex>| <tex>23</tex>| <tex>[49, 261]</tex>| <tex>[80, 143]</tex>| <tex>[115, 298]</tex>| <tex>[205, 540]</tex>| <tex>[217, 1031]</tex>| <tex>[252, 41713]</tex>| <tex>[292, 2826]</tex>|-align="center"! <font color="black"><tex>8</tex></font>| <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"! <font color="black"><tex>9</tex></font>| <tex>1</tex>| <tex>9</tex>| <tex>36</tex>| <tex>[73, 13115]</tex>| <tex>[133, 15 или 16).316]</tex>| <tex>[183, 780]</tex>| <tex>[252, 1713]</tex>| <tex>[329, 3583]</tex>Существует гипотеза что любой граф | <tex>R(k[565,k)6588]</tex> изоморфен своему дополнению(или что в раскраске полного графа на | <tex>r(k[580,k)12677]</tex>|-align="center"! <font color="black"><tex>10</tex></font>| <tex>1</tex> вершинах в два цвета граф с рёбрами цвета 1 обязательно изоморфен графу с рёбрами цвета 2). Однако| <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>

Пусть <tex>k,n_1,...,n_k \in \mathbb N</tex>. '''Число Рамсея ''' <tex>r(k;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 \ge 2in \mathbb N </tex> {{---}} натуральные числа. Тогда выполняются следующие утверждения:существует число Рамсея <tex>1) r(k;n_1,...\ldots,n_k) \le </tex>, при этом <tex>r(k;n_1-1,n_2,...\ldots,n_k)+\leqslant r(k;n_1,n_2\ldots, n_{k-1,...2},n_k)++r(n_{k;n_1,n_2,...,n_k-1)-k+2</tex><tex dpi="150">2)r(k},\;n_1,...,n_k) \le \frac{(n_1+n_2+...+n_k)!}{n_1!\cdot n_2!\cdot ...\cdot n_k!}</tex>

Возьмем граф из <tex>r(n_1,\ldots, n_{k-2}, r(n_{k-1}, n_k) Доказательстве полностью аналогично пункту )</tex> вершин и окрасим его рёбра в <tex>k</tex> цветов. Пока что будем считать цвета <tex>k-1 доказательства [[#ter1|теоремы </tex> и <tex>k</tex> одним цветом. Тогда граф будет <tex>(k-1]] 2) Доказательство аналогично [[#u1|утверждению 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(левая часть в этом случае равна n_{k-1}, а праваяn_k)}</tex>, очевидно не меньше окрашенный общим цветом <tex>k-1) </tex> и <tex>k</tex>. В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметитьзаметим, что полиномиальные коэффициенты из очевидных комбинаторных соображений удовлетворяют соотношению: , по определению числа Рамсея, полный <tex dpi="150">\fracr(n_{(n_1+n_2+...+k-1},n_k)!}</tex> — вершинный граф содержит либо <tex>K_{n_1!\cdot n_2!\cdot ...\cdot n_k!}=\sum\limits_n_{i = k-1}^}</tex> цвета <tex>k\frac-1</tex>, либо <tex>K_{n_k}</tex> цвета <tex>k</tex>. Таким образом любое число Рамсея для раскраски в <tex>k</tex> цветов ограничено некоторым числом Рамсея для меньшего количества цветов, следовательно, <tex>r(n_1+...+(n_i-1)+...+,\ldots,n_k)!}{</tex> существует для любых <tex> k, n_1!, \cdot ...ldots n_k, \cdot (n_i-1)!in \cdot ...\cdot n_k!}mathbb N </tex> Следовательно, 2 неравенство из данной [[#ter3|теоремы]] выводится из неравенства 1 по индукциии теорема доказана.

Пусть <tex>m,k,n_1,...\ldots ,n_k \in \mathbb N</tex>, причём <tex>n_1,...\ldots ,n_k \ge geqslant m</tex>. '''Число Рамсея ''' <tex>r_m(k; 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>.}}{{Определение|id=def6|definition=Число <tex>m</tex> называется называют '''размерностью ''' числа Рамсея <tex>r_m(k;n_1,...\ldots ,n_k)</tex>.}}{{Утверждение|id=u4|about=4|statement=1) Нетрудно понять что числа Рамсея размерности 2 — это определённые выше числа Рамсея для клик<br>2) При количестве цветов, равном 2, этот параметр мы будем опускать и писать <tex>r_m(n_1,n_2)</tex> вместо <tex>r_m(2;n_1,n_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 \ge geqslant 2</tex>, а <tex>n_1,...\ldots ,n_k \ge geqslant m</tex>. Тогда существует число Рамсея <tex>r_m(k;n_1,...\ldots n_k)</tex> существует(то есть, конечно).

1)# Мы будем доказывать теорему по индукции. Начнем со случая <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 \le leqslant p=r_{m-1}(r_m(n_1-1,n_2),r_m(n_1,n_2-1))</tex> . <br> Для каждого множества <tex>M</tex> через <tex>M^k</tex> обозначим множество всех <tex>k</tex>-элементных подмножеств <tex>M</tex>. <br> Рассмотрим <tex>(p+1)</tex>-элементное множество <tex>M</tex> и выделим в нём элемент <tex>a</tex>. Пусть <tex>M_0=M</tex>\setminus \{<tex>a\}</tex>}. Пусть <tex>\rho:M^m\rightarrow</tex> \{1,2\} </tex> — произвольная раскраска в два цвета. Рассмотрим раскраску <tex>\rho': M_0^{m-1}\rightarrow</tex> \{1,2\}</tex> , определённую следующим образом: для каждого множества <tex>B \in M_0^{m-1}</tex> пусть <tex>\rho'(ВB) = \rho(B U</tex>\cup \{a\}<tex>)</tex>.<br> Так как <tex>|M_0|=p</tex>, либо существует <tex>r_m(n_1 — 1,n_2)</tex>-элементное подмножество <tex>M_i M_1 \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>.<br> По индукционному предположен из <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 </tex>\{<tex>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</tex>\setminus \{<tex>a</tex>\}<tex>\in N_1^{m-1} \subset M_1^{m-1}</tex> и поэтому <tex>\rho(A)=\rho'(A</tex>\setminus \{<tex>a</tex>\}<tex>)=1</tex>. Учитывая, что <tex>|N|=n_1</tex>, мы нашли искомое подмножество и в этом случае. 2)# При <tex>k>2</tex> будем вести индукцию по <tex>k</tex> с доказанной выше базой <tex>k=2</tex>. При <tex>k>2</tex> мы докажем неравенство <tex>r_m(k;n_1,...\ldots ,n_k) \le leqslant q=r_m(r_m(k-1;n_1,...\ldots ,n_{k-1}),n_k)</tex> . <br> Для этого мы рассмотрим множество <tex>M</tex> на <tex>q</tex> вершинах и произвольную раскраску <tex>\rho:M^m \rightarrow [1..\ldots k]</tex> в <tex>k</tex>цветов. Рассмотрим раскраску <tex>\rho':M^m \rightarrow </tex>\{<tex>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(k-1;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>.

Пусть <tex>H_1,h_2H_2</tex> — два данных графаграфы. '''Число Рамсея ''' <tex>r(H_1,H_2)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в два цвета обязательно найдется подграф, [[Основные определения теории графов#isomorphic_graphs|изоморфный ]] <tex>H_1</tex> с рёбрами цвета <tex>1 </tex> или подграф изоморфный <tex>H_2</tex> с рёбрами цвета <tex>2</tex>.

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

|id=l1|about=1|statement=Пусть <tex>m>1</tex>, а граф <tex>H</tex> таков, что <tex>v(H) \ge geqslant (m-1)(n-1)+1</tex> и <tex>\alpha(H) \le leqslant m-1</tex>, где <tex>v(H)</tex> {{---}} количество вершин в графе <tex>H</tex>. Тогда граф <tex>H</tex> содержит в качестве подграфа любое [[Основные определения теории графов#defTree|дерево ]] на <tex>n</tex> вершинах.

Зафиксируем <tex>m</tex> и проведем индукцию по <tex>n</tex>.  '''База :''' для <tex>n=1</tex> очевиднаочевидно. Докажем индукционный  '''Индукционный переход :''' Пусть верно для <tex>n-1 \rightarrow </tex>, докажем для <tex>n(n>1</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) \le leqslant m-1</tex>, следовательно <tex>v(H-U) \ge geqslant (m-1)(n-2)+1</tex> и очевидно <tex>\alpha(H-U) \le 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(</tex> не принадлежит множеству вершин графа <tex>T_{n-1})</tex> и, присоединив вершину <tex>x</tex> к вершине <tex>a</tex> дерева <tex>T_{n-1}</tex>, получим дерево <tex>T_n</tex> в качестве подграфа графа <tex>H</tex>.

|author=5, Теорема Хватала|statement=Пусть <tex>T_n</tex> — дерево на <tex>n</tex> вершинах. Тогда <tex>r(T_n,K_m)=(m-1)(n-1)+1</tex>, где <tex>T_n</tex> — дерево на <tex>n</tex> вершинах.

1) ДокажемСперва докажем, что <tex>r(T_n,K_m) \ge 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> вершинах. 2Теперь воспользуемся вторым [[#def16|определением]] числа Рамсея <tex>r(H_1, H_2) </tex>. Рассмотрим произвольную раскраску рёбер полного графа произвольный граф <tex>G</tex> на <tex>K_{(m-1)(n-1)+1}</tex> в два цветавершинах. Предположим, что в графе <tex>G</tex> не существует клики на <tex>m</tex> вершинах с рёбрами цвета 2. Тогда <tex>m>1</tex> и <tex>\alpha(G_1\overline G) \le leqslant m-1</tex>. По [[#l1|лемме <tex>1</tex>]], граф <tex>G_1\overline G</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах , в частности, дерево, изоморфное <tex>T_n</tex>.

|definition=Пусть Граф <tex>H</tex> — графназывается '''индуцированным подграфом''' (англ. Граф ''induced subgraph'') графа <tex>G</tex> называется рамсеееским графом для если две вершины в <tex>H</tex>соединены ребром тогда и только тогда, если при любой раскраске рёбер графа <tex>G</tex> когда они смежны в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G</tex> изоморфный <tex>H</tex>}}При замене произвольного графа <tex>H</tex> на клику мы получаем частный случай классической теоремы Рамсея. Для клики добавленное слово "индуцированный" ничего не меняет. Но значительно усложняет ситуацию для произвольного графа <tex>H</tex>. {{Теорема|id=ter6 |about=6, Индуцированная теорема Рамсея|statement=Для любого графа существует рамсеевский граф}}===Случай двудольного графа===Здесь мы будем рассматривать двудольный граф <tex>G</tex>, как

|definition=Пусть <tex>H,G</tex> — двудольные графыграф. Инъективное отображение Граф <tex>\phi:V(H)\rightarrow V(G)</tex> назовём погружением, если оно удовлетворяет двум условиямбудем называть '''рамсеевским графом''' (англ.<br>1''Ramsey’s graph'')для <tex>\phi(V_1(H)) \subset V_1(G), \phi(V_2(H)) \subset v_2(G)</tex><br>2)<tex>\phi(u)\phi(v) \in E(G)</tex> тогда и только тогда когда <tex>uv\in E(H)</tex>В этом случае будем говорить, что двудольный граф <tex>H</tex> погружён в двудольный граф <tex>G</tex> и использовать обозначение <tex>\phi(H)=G(\phi(V(H)))</tex>}}{{Утверждение|id=u5|about=5|statement=Отметим, что если существует погружение <tex>\phi</tex> двудольного при любой раскраске рёбер графа <tex>HG</tex> в двудольный граф <tex>G</tex> то два цвета существует одноцветный по рёбрам индуцированный подграф <tex>\phi(H)</tex> графа <tex>G</tex> изоморфен изоморфный <tex>H</tex>.}}Напомним, что для множества <tex>X</tex> через <tex>X^k</tex> мы обозначаем множество всех <tex>k</tex>-элементных подмножеств множества <tex>X</tex>.

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

Построим погружение <tex>P</tex> в особый двудольный граф <tex>H=(V,V^{n+1},E)</tex>.{Теорема|id=ter6 Изначально положим <tex>\phi(a_i)|about=x_i</tex>. Попробуем построить такое множество <tex>Y_j\in V^{n+1}</tex>6, что <tex>\phi(b_j)Индуцированная теорема Рамсея|statement=Y_j</tex>. По определению погружения и множества Для любого графа <tex>E(H)</tex>, должно выполняться условие:<br><tex>Y_j\cap\{x_1,...,x_n\}=\phi(N_P(b_j)</tex>Условие оставляет незаполненными <tex>n+1-d_P(b_j)\ge 1</tex> элементов множества <tex>Y_j</tex> (единственное ограничение эти элементы не могут быть вершинами <tex>x_1,...,x_n</tex>). Поместим в <tex>Y_j</tex> элемент-индекс <tex>z_j</tex> (чтобы <tex>Y_j\not=Y_l</tex> при <tex>j \not=l</tex>, и дополним произвольно элементами из <tex>y_1,...,y_n</tex>, чтобы в множестве <tex>Y_j</tex> было ровно существует рамсеевский граф <tex>n+1G</tex> элементов.

{{Лемма|id=l3|about=3|statement=Для любого двудольного графа Доказательство <texref>H</tex> существует такой двудольный граф <tex>G</tex>, что для любой раскраски рёбер <tex>G</tex> в два цвета обязательно существует погружение <tex>\phi</tex> графа <tex>H</tex> в граф <tex>G</tex> в котором все рёбра <tex>\phi(H)</tex> одноцветны.|proof= {{Утверждение|id=u6|about=6|statement=Разумеется, указанный в условии [[#l3|леммы 3]] граф <tex>G</tex> будет рамсеевским графом для <tex>H</tex>. Утверждение леммы более сильноеhttps: мы дополнительно требуем, чтобы все вершины одной доли <tex>H</tex> можно было погрузить в одну долю графа <tex>G</tex>math.}}Ввиду [[#l2|леммы 2]] достаточно доказать утверждение для особого двудольного графа <tex>H=(V,V^k,E(H))</tex>la. Пусть <tex>|V|=n</tex>asu. Докажем что рамсеевским графом для <tex>H<edu/tex> будет особый двудольный граф <tex>G=(U,U^{2k-1},E(G))<~andrzej/tex>, где<br><tex>|U|=r_{2k-1}(2C^k_{2k-1};kn+k-1,...,kn+k-1).<teach/tex> '''**'''<br>Рассмотрим произвольную раскраску рёбер графа <tex>G<mat598/tex> в два цвета 1 и 2lec8. Каждое множество <tex>Y\in U^{2k-1}pdf Induced Ramsey Theorem Proof]</texref> смежно как вершина особого двудольного графа <tex>G</tex> с <tex>2k-1</tex> вершинойданной теоремы было приведено независимо различными математиками, хотя бы <tex>k</tex> из этих рёбер имеет одинаковый цвет. Выберем и зафиксируем для каждого множества <tex>Y</tex> его подмножество <tex>S(Y)</tex>, состоящее из <tex>k</tex> вершин доли <tex>U</tex> соединённых с <tex>Y</tex> рёбрами одинакового цветаоднако благодаря ему получилось предоставить только очень грубые оценки значений индуцированных чисел Рамсея. Пусть <tex>c(Y)\in \{1,2\}</tex> — это цвет рёбер соединяющий <tex>Y</tex> с вершинами из <tex>S(Y)</tex>. Можно считать, что элементы <tex>U</tex> упорядочены. Тогда элементы каждого множества <tex>Y\in U^{2kВ данный момент проблема нахождения сколько-1}</tex> будут упорядочены. Обозначим через <tex>\sigma(Y)</tex> множество номеров <tex>k</tex> элементов множества <tex>S(Y)</tex> в порядке элементов множества <tex>Y</tex>. Тогда <tex>\sigma(Y)</tex> может принимать ровно <tex>C^k_{2k-1}</tex> значенийнибудь точных границ индуцированных чисел Рамсея является нерешенной задачей математики.

Покрасим множество <tex>U^{2k-1}</tex> (то есть все <tex>(2k-1)</tex>-элементные подмножества <tex>U</tex>) ==Особенности теории==Результаты, полученные в <tex>2C^k_{2kтеории Рамсея, обладают двумя главными характеристиками. Во-1}</tex>цветовпервых, они не позволяют получить сами структуры: цветом подмножества <tex>Y</tex> будет пара <tex>(\sigma(Y)теоремы лишь доказывают, что они существуют,c(Y))</tex>но алгоритма для их нахождения не предлагают. Из выбора размера множества <tex>U</tex> (смЕдинственным способ найти нужную конструкцию зачастую является перебор. условие **) следуетВо-вторых, что ceotcndetn такое подмножество <tex>W\subset U</tex>чтобы искомые структуры существовали, что <tex>|W|=kn+k-1</tex> и все подмножества <tex>Y\subset W^{2k-1}</tex> имеют одинаковый цвет <tex>(\sigma(Y)обычно требуется,c(Y))</tex> (не умаляя общности будем считатьчтобы объекты, что <tex>\sigma(Y)=\sigmaих содержащие, c(Y)=1)</tex>состояли из очень большого числа элементов. Мы найдём погружение графа <tex>H</tex> в <tex>G(W)</tex>Зависимость числа элементов объекта от размера конструкции обычно, как минимум, все рёбра в котором покрашены в исходной раскраске в цвет 1 и тем самым докажем леммуэкспоненциальная.

*[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://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1| Small Ramsey Numbers by Stanisław Radziszowski][[Категория: Алгоритмы Дискретная математика и структуры данныхалгоритмы]][[Категория:Дискретная математика]][[Категория:Теория графов]]