Изменения

Основным объектов изучения будут полные {{Определение|id=def1|definition='''Клика''' (англ. ''clique'') в [[Основные определения теории графов#Неориентированные графы|неориентированном графе]] <tex>G(V, ребра которых покрашены E)</tex> {{---}} подмножество [[Основные определения теории графов#Неориентированные графы|вершин]] <tex>C \subseteq V</tex>, такое что для любых двух различных вершин в несколько цветов<tex>C</tex> существует [[Основные определения теории графов#def_edge_und|ребро]], их соединяющее. В дальнейшемДругими словами, для простоты, полный граф на клика графа <tex>nG(V, E)</tex> вершинах будем называть кликой.{{Определение---}} [[Основные определения теории графов#defFullGraph|definition=Пусть полный]] подграф графа <tex>mG(V, n \in \mathbb NE)</tex>. }}{{Определение|id=def2|definition='''Число Рамсея ''' <tex>r(n, m, 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=t1ter1|authorabout=P. Erdos1, G. SzekeresТеорема Рамсея |statement=Пусть Для любых <tex>n,m \ge 2in \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) \leqslant r(n,m-1)+r(n-1,m) - 1</tex> .

 # Докажем с помощью метода математической индукции по <tex>n+m</tex>. <br>'''База:''' <tex>r(n,\;1) = r(1,\;n) = 1</tex>, так как граф, состоящий из одной вершины, можно считать полным графом любого цвета. <br>'''Индукционный переход:''' Пусть <tex>n>1</tex> и <tex>m>1</tex>. Рассмотрим клику на полный чёрно-белый граф из <tex>r(n-1, \;m - 1) + r(n ,\;m- 1, m)</tex> вершинах с рёбрами цветов 1 вершин. Возьмём произвольную вершину <tex>v</tex> и 2 обозначим через <tex>M</tex> и ее произвольную вершину <tex>aN</tex>. Тогда либо от вершины множества вершин, инцидентных <tex>av</tex> отходит хотя бы в чёрном и белом подграфе соответственно. Так как в графе <tex>r(n-1, \;m)+r(n,\;m - 1)=|M|+|N|+1 </tex> рёбер цвета 2 вершин, согласно принципу Дирихле, либо от вершины <tex>a|M|\geqslant r(n-1,\;m)</tex> отходит хотя бы , либо <tex>|N|\geqslant r(n—1n, \;m-1)</tex> рёбер цвета 1. Случаи аналогичны, рассмотрим первый случай и клику на Пусть <tex>|M|\geqslant r(n-1, \;m — 1)</tex> вершинах, соединенных с . Тогда либо в <tex>aM</tex> рёбрами цвета 2. На этих вершинах есть либо клика на существует белый <tex>nK_m</tex> вершинах с ребрами цвета 1, что доказывает теорему, либо клика на в <tex>M</tex> есть чёрный <tex>m—1K_{n-1}</tex> вершинах , который вместе с рёбрами цвета 2. Во втором случае добавим вершину <tex>av</tex> и получим клику на образует чёрный <tex>mK_n</tex> вершинах с рёбрами цвета 2, в этом случае теорема также доказана. Теперь из определения Случай <tex>|N|\geqslant r(n, \;m-1)</tex> следует [[#t1|неравенство]]рассматривается аналогично.2) Рассмотрим клику на # Предположим, <tex>p=r(n-1, \;m-l)+</tex> и <tex>q=r(n,\;m-1, m)</tex> оба чётны. Положим <tex>s=p+q-1</tex> вершинах с рёбрами цветов 1 и 2 и его произвольную вершину рассмотрим чёрно-белый граф из <tex>as</tex>вершин. Если вершине <tex>ad_i</tex> инцидентны хотя бы степень <tex>i</tex>r(n-й вершины в чёрном подграфе, то, согласно [[Лемма о рукопожатиях|лемме о рукопожатиях]],m-<tex> \sum\limits_{i=1)}^s d_i</tex> рёбер цвета 2 или хотя бы  — чётно. Поскольку <tex>r(n-1s</tex> нечётно,m)должно существовать чётное <tex>d_i</tex> рёбер цвета 1. Не умаляя общности, положим, то мы найдём в графе клику на что <tex>d_1</tex> чётно. Обозначим через <tex>nM</tex> вершинах с рёбрами цвета 1 или клику на и <tex>mN</tex> вершинах с рёбрами цвета 2. Остаётся лишь случайвершины, когда инцидентные вершине <tex>a1</tex> инцидентны ровно в чёрном и белом подграфах соответственно. Тогда <tex>r(n, m|M|=d_1</tex> и <tex>|N|=s-1)-1d_1</tex> рёбер цвета 2, то же самое для всех остальных вершиноба чётны. Это означаетСогласно принципу Дирихле, что в графе из рёбер цвета 2 всего либо <tex>r(n, m-1)+r(n|M|\geqslant p-1</tex>, m)-1либо <tex>|N|\geqslant q</tex> вершин и степень каждой вершины равна . Так как <tex>|M|</tex>r(nчётно, m-1)а <tex>p-1</tex>. Однаконечётно, тогда в графе нечётное количество вершин нечётной степени. Противоречие показывает нампервое неравенство можно усилить, так что в случае, когда либо <tex>r(n, m-1)|M|\geqslant p</tex> и , либо <tex>r(n-1,m)|N|\geqslant q</tex> — чётные. <br> Далее проводим рассуждения, выполняется неравенство аналогичные тем, что присутствуют в первом пункте теоремы. Таким образом, <tex>r(n, m)<\leqslant r(n, m-1)+r(n-1, m)-1</tex>.

{{Утверждение|id=ts1u1|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=def2|definition=Графом Рамсея <tex>R(n,m)</tex> назовем такой граф на <tex>r(n,m)-1</tex> вершинах, не содержащий ни клики на <tex>n</tex> вершинах ни независимого множества на <tex>m</tex> вершинах(то есть, граф на ребрах цвета 1 из раскраски в два цвета ребер графа <tex>K_{r(m,n)-1}</tex>, не содержащей ни клики на <tex>n</tex> вершинах с рёбрами цвета 1 ни клики на <tex>m</tex> вершинах с рёбрами цвета 2).}}Граф <tex>R(3,3)</tex> — это цикл на пяти вершинах. Экстремальный граф <tex>R(3,4)</tex> — это цикл на 8 вершинах с проведёнными четырьмя главными диагоналями. Графы <tex>R(3,5)</tex> и <tex>R(4,4)</tex> имеют интересную числовую природу.

{{Теорема|id=ter2|about=2, Теорема Эрдеша|statement=Для любого натурального числа <tex>k \geqslant 2</tex> выполняется неравенство <tex>r(k,k) \geqslant 2^{k/2}</tex>|proof=Так, если ассоциировать 13 вершин графа как <tex>Rr(32,52)=2</tex> с элементами поля вычетов по модулю 13, то рёбра будут соединять вычеты разность которых — кубический вычет по модулю 13 достаточно рассмотреть случай <tex>k \geqslant 3</tex>.Пусть <tex>g(то естьn, 1k)</tex> доля среди помеченных графов на <tex>n</tex> вершинах тех, 5что содержат клику на <tex>k</tex> вершинах. Всего графов на наших вершинах, 8 очевидно <tex>2^{C^2_n}</tex> (каждое из возможных рёбер <tex>C^2_n</tex> можно провести или 12не провести).

Если считать 17 вершин графа Посчитаем графы с кликой на <tex>k</tex> вершинах следующим образом: существует <tex>C^k_n</tex> способов выбрать <tex>R(4,4)k</tex> элементами поля вычетов по модулю 17вершин для клики в нашем множестве, то после чего все рёбра будут соединять вычетымежду ними будем считать проведенными, а остальные ребра выбираются произвольно. Таким образом, разность которых — квадратичный вычет по модулю 17 (то естькаждый граф с кликой на <tex>k</tex> вершинах будет посчитан, 1причём некоторые даже более одного раза. Количестве графов с кликой оказывается не более, чем <tex>C^k_n\cdot 2^{C^2_n-C^2_k}</tex>. Следовательно, 4, 8, 9, 13, 15 или 16).

Существует гипотеза что любой граф <tex>Rg(n,k,) \leqslant \dfrac{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}}<\dfrac{n^k}{k!\cdot 2^{C^2_k}}</tex> изоморфен своему дополнению(или что в раскраске полного графа на <tex>r(k,k*)-1</tex> вершинах в два цвета граф с рёбрами цвета 1 обязательно изоморфен графу с рёбрами цвета 2). Однако, это не белее чем красивое предположение, в обоснование которого можно положите лишь немногие известные примеры.

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

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

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

Подставив ===Свойства чисел Рамсея===Следующими свойствами удобно пользоваться при подсчете значений чисел Рамсея <tex>r(n,m)</tex> на практике.* <tex>r(n,m) = r(m,n)</tex>* <tex>r(1,m) = 1<2^{k/tex>* <tex>r(2},m) = m</tex> в [[#t2|неравенстве]] мы получаем

===Значения чисел Рамсея===Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, их известно довольно мало. Далее приведена таблица Станислава Радзишевского, в которой присутствуют практически все известные числа Рамсея или же промежутки, в которых они находятся.<center>{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+!colspan="11"|Числа Рамсея|-align="center"! width="6%" |<font color="black"><tex>g(n,k)\ m<\frac{2^{k^/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 </2}*2^{tex>|-C^2_k}}{kalign="center"!}<font color=\frac{"black"><tex>2^{k</tex></font>| <tex>1 </tex>| <tex>2}}{k</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"!}<\frac12font color="black"><tex>3</tex></font>| <tex>1</tex> при | <tex>k \ge 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>| <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"! <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, 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"! <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, 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"! <font color="black"><tex>10</tex></font>| <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(kn_1,\ldots,kn_k)=n<2^{k/2}</tex> и разобьём все графы на n вершинах на пары — это наименьшее из всех таких чисел <tex>G, x \in \overline Gmathbb N</tex> (граф и его дополнение) Так как , что при любой раскраске рёбер полного графа на <tex>g(n,k)<\frac12x</tex>, то существует пара, вершинах в которой ни <tex>Gk</tex>, ни цветов для некоторого <tex>i \in [1 \overline Gldots k]</tex> не содержат клики обязательно найдётся клика на <tex>kn_i</tex> вершинах. Рассмотрим раскраску рёбер <tex>K_n</tex> в два с рёбрами цвета, в которой ребра цвета 1 образуют граф <tex>Gi</tex>. В такой раскраске нет клики на <tex>k</tex> вершинах ни цвета 1, ни цвета 2n_1, противоречие. Следовательно <tex>r(k\ldots,k) n_k \in \ge 2^{k/2}mathbb N</tex>.

 {{УтверждениеТеорема|id=ts2ter3|about=Следствие 23,Теорема Рамсея для нескольких цветов|statement=Для любых <tex>\forall k,m 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 \le }, r(n_{k -1},\le m;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},mn_k) )</tex>, такой граф либо содержит <tex>K_{n_i}</tex> для некоторого цвета <tex>i</tex>, такого что <tex>1\leqslant i\ge leqslant k-2^</tex>, либо <tex>K_{r(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</2tex>, либо <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=def2 def5

Пусть <tex>m,k,n_1,...\ldots ,n_k \in \mathbb N</tex>, причём <tex>n_1,\ldots ,n_k \geqslant m</tex>. '''Число Рамсея ''' <tex>rr_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>. Число <tex>m</tex> называют '''размерностью''' числа Рамсея <tex>r_m(n_1,\ldots ,n_k)</tex>.

|id=t3. ter4|about=4, Теорема Рамсея для чисел больших размерностей|statement=Пусть <tex>m,k,n_1,...\ldots,n_k \ge 2</tex> {{--- }} натуральные числа. Тогда выполняются следующие утверждения:, причем <tex>1) r(k;n_1,...,n_k) \le r(k;n_1-1geqslant 2</tex>,n_2,...,n_k)+r(k;а <tex>n_1,n_2-1,...\ldots ,n_k)++r(k;n_1,n_2,...,n_k-1)-k+2\geqslant m</tex>. Тогда существует число Рамсея <tex>2)rr_m(k;n_1,...,n_k) \le \frac{(n_1+n_2+...+ldots n_k)!}{n_1!*n_2!*...*n_k!}</tex>.

1) Доказательстве полностью аналогично пункту 1 доказательства [[#t1|теоремы]] Мы будем доказывать теорему по индукции. Начнем со случая <tex>k=2) Доказательство аналогично [[#ts1|следствию 1]]</tex>. Нужно лишь убедиться в очевидном неравенстве Приступая к доказательству для случаячисла <tex>r_m(n_1, когда хотя бы одно из n_2)</tex> мы будем считать доказанным утверждение теоремы для чисел Рамсея всех меньших размерностей и чисел Рамсея размерности <tex>m</tex> с меньшей суммой <tex>n_1,.+n_2</tex>.В качестве базы будем использовать случай чисел Рамсея размерности <tex>2</tex> разобранный выше.Итак, мы докажем,n_kчто </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>. <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 \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>\fracrho'(B) = \rho(B \cup \{a \})</tex>. <br> Так как <tex>|M_0|=p</tex>, либо существует <tex>r_m(n_1+— 1,n_2+...+n_k)!</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>.<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>.*n_k!}Во втором случае искомое подмножество найдено (это <tex>N_2</tex>), рассмотрим первый случай и множество <tex>N=N_1 \sumcup \limits_{i 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^k{m-1} \fracsubset M_1^{m-1}</tex> и поэтому <tex>\rho(A)=\rho'(A \setminus \{a \})=1</tex>. Учитывая, что <tex>|N|=n_1+</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_in_1,\ldots ,n_{k-1})+...+,n_k)!}{n_1!*</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 \{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_in_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>..*n_k!}Исходя из размера множества <tex>M_0</tex> по индукционному предположению получаем, что найдется искомое подмножество множества <tex>M</tex> для одного из цветов <tex>1,\ldots ,k-1</tex> Следовательно, 2 таким образом неравенство доказано, а из данной теоремы выводится из неравенства 1 по индукцииэтого следует и существование числа Рамсея <tex>r_m(n_1,\ldots ,n_k)</tex>.

==Числа Рамсея больших размерностейдля произвольных графов==Еще один способ обобщения классической теории Рамсея — замена клик на произвольные графы-шаблоны.

|id=def5. def8

Пусть <tex>mH_1,k,n_1,...,n_k \in \mathbb N</tex>, причём <tex>n_1,...,n_k \ge mH_2</tex>— графы. '''Число Рамсея ''' <tex>r_mr(k; n_1H_1,...,n_kH_2)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске <tex>m</tex>-элементных подмножеств рёбер полного графа на <tex>x</tex>-элементного множества <tex>M</tex> вершинах в <tex>k</tex> цветов для некоторого <tex>i \in два цвета обязательно найдется подграф, [[1..kОсновные определения теории графов#isomorphic_graphs|изоморфный]]</tex> обязательно найдётся такое множество <tex>W_i</tex>, что <tex>|W_i|=n_iH_1</tex> и все с рёбрами цвета <tex>m1</tex>-элементные подмножества множества или подграф изоморфный <tex>W_iH_2</tex> имеют цвет с рёбрами цвета <tex>i2</tex>.

|id=def6def16

Число Пусть <tex>mH_1,H_2</tex> называется размерностью числа — графы. '''Число Рамсея ''' <tex>r_mr(k;n_1H_1,H_2)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>,...что для любого графа <tex>G</tex> на <tex>x</tex> вершинах либо в <tex>G</tex> найдется подграф изоморфный <tex>H_1</tex>,n_k) либо в <tex>\overline G</tex> найдется подграф изоморфный <tex>H_2</tex>.

{{Утверждение|id=u2 |statement=1Несложно показать, что эти определения эквивалентны (аналогично определениям для классических чисел Рамсея) Нетрудно понять . Из результатов классической теории Рамсея становится понятно, что числа Рамсея размерности 2 — это определённые выше числа Рамсея для клик<tex>r(H_1,H_2)</tex> существуют.

2) При количестве цветов{{Лемма|id=l1|about=1|statement=Пусть <tex>m>1</tex>, равном 2а граф <tex>H</tex> таков, этот параметр мы будем опускать что <tex>v(H) \geqslant (m-1)(n-1)+1</tex> и писать <tex>r_m\alpha(n_1,n_2H)\leqslant m-1</tex> вместо , где <tex>r_mv(2;n_1,n_2H)</tex> {{---}} количество вершин в графе <tex>H</tex>. Тогда граф <tex>H</tex> содержит в качестве подграфа любое [[Основные определения теории графов#defTree|дерево]] на <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>|id=def7U|definition=\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>MH-U</tex> через содержит в качестве подграфа дерево <tex>M^kT_{n-1}</tex> . Пусть <tex>a</tex> — вершина этого дерева, присоединив к которой висячую вершину, мы будем обозначать получим дерево <tex>T_n</tex>. Заметим, что множество всех <tex>kU \cup</tex><tex>\{a\}</tex> не является независимым ввиду максимальности <tex>U</tex>. Следовательно, вершина <tex>a</tex> смежна хотя бы с одной вершиной <tex>x \in U</tex>. Отметим, что <tex>x</tex> не принадлежит множеству вершин графа <tex>T_{n-элементных подмножеств 1}</tex> и, присоединив вершину <tex>x</tex> к вершине <tex>a</tex> дерева <tex>T_{n-1}</tex>, получим дерево <tex>T_n</tex> в качестве подграфа графа <tex>MH</tex>.

|id=th5. ter5 |author=5, Теорема Хватала|statement=Пусть <tex>r(T_n,K_m)=(m,k,n_1,...,n_k-1)(n-1)+1</tex> - натуральные числа, причем где <tex>k \ge 2T_n</tex>, а — дерево на <tex>n_1,...,n_k \ge mn</tex>вершинах. Тогда число Рамсея <tex>r_m(k;n_1,...n_k)</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>k=2</tex>(то есть, все оставшиеся рёбра) образуют <tex>(m-1)</tex>-дольный граф, в котором, очевидно, нет клики на <tex>m</tex> вершинах. Приступая к доказательству для Теперь воспользуемся вторым [[#def16|определением]] числа Рамсея <tex>r_mr(n_1H_1,n_2H_2)</tex>. Рассмотрим произвольный граф <tex>G</tex> на <tex>{(m-1)(n-1)+1}</tex> вершинах. Предположим, что в графе <tex>G</tex> не существует клики на <tex>m</tex> вершинах. Тогда <tex>m>1</tex> и <tex>\alpha( \overline G)\leqslant m-1</tex>. По [[#l1|лемме <tex>1</tex>]], граф <tex> \overline G</tex> мы будем считать доказанным утверждение теоремы для чисел содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах, в частности, дерево, изоморфное <tex>T_n</tex>.}} ==Индуцированная теорема Рамсея всех меньших размерностей =={{Определение|id=def9|definition=Граф <tex>H</tex> называется '''индуцированным подграфом''' (англ. ''induced subgraph'') графа <tex>G</tex> если две вершины в <tex>H</tex> соединены ребром тогда и чисел Рамсея размерности только тогда, когда они смежны в <tex>mG</tex> с меньшей суммой . }} {{Определение|id=def10|definition=Пусть <tex>n_1+n_2H</tex>— граф. В качестве базы Граф <tex>G</tex> будем использовать случай чисел называть '''рамсеевским графом''' (англ. ''Ramsey’s graph'') для <tex>H</tex>, если при любой раскраске рёбер графа <tex>G</tex> в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G</tex> изоморфный <tex>H</tex>.}} {{Определение|id=def11|definition='''Индуцированным числом Рамсея размерности 2 разобранный выше''' (англ. Итак''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> на клику мы получаем частный случай классической теоремы Рамсея.

Рассмотрим <tex>(p+1)</tex>-элементное множество <tex>M</tex> и выделим в нём элемент <tex>a</tex>. Пусть <tex>M_0=M</tex>\{<tex>a</tex>}. Пусть <tex>\alpha:M^m\rightarrow</tex> {1,2} — произвольная раскраска в два цвета. Рассмотрим раскраску <tex>\alpha': M_0^{m-1}\rightarrow</tex> {1,2}, определённую следующим образом: для каждого множества <tex>B \in M_0^{m-1}</tex> пусть <tex>\alpha'(В) Теорема|id= \alpha(B U</tex>{a}<tex>)</tex>.ter6 Так как <tex>|M_0|about=р</tex>6, либо существует <tex>r_m(n_1 — 1,n_2)</tex>-элементное подмножество <tex>M_i \subset M_0</tex>, для которого <tex>\alpha'(В)Индуцированная теорема Рамсея|statement=1Для любого графа </tex> на всех <tex>B \in M_1^{m-1}H</tex>, либо существует рамсеевский граф <tex>r_m(n_1,n_2-1)</tex>-элементное подмножество <tex>M_2 \subset M_0</tex>, для которого <tex>\alpha'(B)=2</tex> на всех <tex>B \in M_2^{m-1}</tex>. Случаи аналогичны, рассмотрим первый случай и множество <tex>M_1G</tex>.

==Числа Рамсея для произвольных графов==Еще один способ обобщения классической теории Рамсея — замена клик на произЕСлвные графы-шаблоны,Определение 1СДоказательство <ref>[https://math.la.asu.5edu/~andrzej/teach/mat598/lec8. Пусть Нхpdf Induced Ramsey Theorem Proof]</ref> данной теоремы было приведено независимо различными математиками,Н2 — два данных графаоднако благодаря ему получилось предоставить только очень грубые оценки значений индуцированных чисел Рамсея. Висло Рамсея г(Нх,Н2) — зто наименьшее из всех таких В данный момент проблема нахождения сколько-нибудь точных границ индуцированных чисел ж £ N что при любой раскраске рёбер полного врафа на х вершинах е два цвета обязатель­но найдется подграф, изоморфный Нх с рёбрами цвета ] или педграф изоморфный Н2 с рёбрами цвета 2Е принципе из результатов классической теории Рамсея понятие, чте числа г(Нх, Н2) обязательно существуют (тс есть, конечны"является нерешенной задачей математики. Интересно, что иногда их можно точно вычислить,

Лемма 10==Особенности теории==Результаты, полученные в теории Рамсея, обладают двумя главными характеристиками.1Во-первых, они не позволяют получить сами структуры: теоремы лишь доказывают, Пусть т > 1что они существуют, а граф Н такоено алгоритма для их нахождения не предлагают. чтои(Н) > (то—1)(п—1)+1 и <уЕдинственным способ найти нужную конструкцию зачастую является перебор.{Н) < то — 1Во-вторых, чтобы искомые структуры существовали, обычно требуется, чтобы объекты, их содержащие, состояли из очень большого числа элементов. Зависимость числа элементов объекта от размера конструкции обычно, как минимум, экспоненциальная. Тосоа граф Н содержит е качестве посграфа лкбсе дереве ьап вершинах

Доказательство, Зафиксируем т и проведем индукцию не п==См. База для п — 1 очевидна. Докажем индукционный переход п — 1 —> п (п > 1), Рассмотрим произвольнее дереис Тп на п иершинах. пусть дереЕС Tn_i получено из Тп удалением висячей Еергнины Пусть U — максимальнее независимое множестве ьершин также==*[[Раскраска графа Н Тогда \U\ = а(РР) < m — 1. следовательно v{H—U) > (то—1)(п-2)+1 и очевидно a(H-U) < m—1.]]По индукционному предположению, граф H — U содержит *[[Раскраска двудольного графа в качестве подграфа дерево Tn_i Пусть а — Еерглина этого дерева, присоединив к ксторей Еисячую ьершину мы получим дереве Тп. Заметим, чте множе­ство U U {а} не является независимым ввиду максимальности U. следо­вательно, вершина а смежна хотя с одней Есршнной х Е U. Стметим, что х 0 V(Tn-i) и, присоединив ьершину х к ьершине а дерева Tn_i, получим дереЕС Тп е качестве подграфа графа Н. □два цвета]]*[[Теорема Турана об экстремальном графе]]

Теорема 10.5. (V. Chvatal) Пусть Тп — дерево на п верьиьпах. Тогоа r(Tn,Km) = (m-l)(n-l) + l.= Примечания==<references />

Доказательство, 1== Источники информации ==* [[wikipedia:Ramsey's theorem|Wikipedia — Ramsey's theorem]] Докажем, что r(Tn, Кт) > (т * [[wikipedia:Ramsey theory|Wikipedia — 1)(п — 1) + 1Ramsey theory]]* [http://people.maths.ox.ac.uk/~gouldm/ramsey. Дляpdf Ramsey Theory]этего нредъяЕим раскраску рёбер графа ^(т*[https://vtechworks.-1)(тг-1) е ксторей нет ни одного СЕязногс подграфа на п Еершинах с рёбрами цвета 1 и нет клики на т вершинах с рёбрами цвета 2lib.vt. Разсбьём Есршнны графа ш т—1 клику по п— 1 вершине и покрасим Есе рёбра этих клик в цвет 1, Тогда любой сеязный подграф с рёбрами цвета 1 содержит не белее п— 1 вер­шины, в частности, нет подграфа с рёбрами цвета 1, изоморфного Тпedu/bitstream/handle/10919/32873/Dickson_JO_T_2011. Рёбра цвета 2 (тс есть, Есе оставшиеся рёбра) образуют (то — pdf?sequence=1)-дсльный граф е котором, счевидне, нет клики на то вершинах&isAllowed=y An Introduction to Ramsey Theory on Graphs]1) Рассмотрим нроизЕСльную раскраску рёбер полного графа K(m-i)(n-i)+i в два цвета*[http://www. Предположим, что не сушестьует клнки на то вершинах с рёбрами цвета 2combinatorics. Тсгда то > 1 и a(Gi) < m—1org/ojs/index. По лемме 10 1, граф Gi содержит е качестве подграфа любее дерево на п вершинах в частности, дереве, иземерфнее Тп. □php/eljc/article/view/DS1| Small Ramsey Numbers by Stanisław Radziszowski][[Категория:Дискретная математика и алгоритмы]]==Индуцированная теорема Рамсея==[[Категория:Дискретная математика]]===Случай двудольного графа===[[Категория:Теория графов]]===Случай произвольного графа===[[Категория: Раскраски графов]]