Изменения

|definition=Пусть '''Клика''' (англ. ''clique'') в [[Основные определения теории графов#Неориентированные графы|неориентированном графе]] <tex>mG(V, n E)</tex> {{---}} подмножество [[Основные определения теории графов#Неориентированные графы|вершин]] <tex>C \in \mathbb Nsubseteq V</tex>, такое что для любых двух различных вершин в <tex>C</tex> существует [[Основные определения теории графов#def_edge_und|ребро]], их соединяющее. Другими словами, клика графа <tex>G(V, E)</tex> {{---}} [[Основные определения теории графов#defFullGraph|полный]] подграф графа <tex>G(V, E)</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=ter1|about=1, Теорема Рамсея |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>m—1есть чёрный <tex>K_{n-1}</tex> вершинах , который вместе с рёбрами цвета 2. Во втором случае добавим вершину <tex>av</tex> и получим клику на образует чёрный <tex>mK_n</tex> вершинах с рёбрами цвета 2, в этом случае теорема также доказана. Теперь из определения Случай <tex>|N|\geqslant r(n, \;m-1)</tex> следует [[#ter1|неравенство из теоремы 1]]рассматривается аналогично.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>s</tex>r(n-1нечётно,m)должно существовать чётное <tex>d_i</tex> рёбер цвета 1. Не умаляя общности, положим, то мы найдём в графе клику на что <tex>d_1</tex> чётно. Обозначим через <tex>nM</tex> вершинах с рёбрами цвета 1 или клику на и <tex>mN</tex> вершинах с рёбрами цвета 2. Остаётся лишь случайвершины, когда инцидентные вершине <tex>a1</tex> в чёрном и белом подграфах соответственно. Тогда <tex>|M|=d_1</tex> инцидентны ровно и <tex>r(n, m|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=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=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>gr(nk,k) \le \frac{C=n<2^k_n}{k/2^{C^2_k}}</tex> и разобьём все графы на <tex>n</tex> вершинах на пары <tex>\frac{langle G, \overline G \rangle</tex>. Так как <tex>g(n^,k)<\dfrac12</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^{C^2_k}}</tex> Подставив , получили противоречие. Значит <tex>n</tex> было выбрано неверно. Из этого следует <tex>r(k,k) \geqslant 2^{k/2}</tex> в [[#t2|неравенстве]] мы получаем.}}

===Свойства чисел Рамсея===Следующими свойствами удобно пользоваться при подсчете значений чисел Рамсея <tex>gr(n,km)<\frac{2^{k^2/2}tex> на практике.*2^{-C^2_k}}{k!}<tex>r(n,m) =\frac{2^{kr(m,n)</2}}{k!}tex>* <\frac12tex>r(1,m) = 1</tex> при * <tex>k \ge 3r(2,m) = m</tex>

Предположим===Значения чисел Рамсея===Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, их известно довольно мало. Далее приведена таблица Станислава Радзишевского, в которой присутствуют практически все известные числа Рамсея или же промежутки, что в которых они находятся.<center>{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+!colspan="11"|Числа Рамсея|-align="center"! width="6%" |<font color="black"><tex>r(kn,k)\ 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=n"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^{k</tex></font>| <tex>1 </tex>| <tex>2}</tex> и разобьём все графы на n вершинах на пары | <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"! <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>| <tex>9</tex>| <tex>18</tex>| <tex>25</tex>| <tex>G[36, \overline G41]</tex> (граф и его дополнение) Так как | <tex>g(n[49,k)61]</tex>| <\frac12tex>[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>G[43, 48]</tex>| <tex>[58, ни 87]</tex>| <tex>\overline G[80, 143]</tex> не содержат клики на | <tex>k[101, 216]</tex> вершинах. Рассмотрим раскраску рёбер | <tex>K_n[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>G[204, 1171]</tex>. В такой раскраске нет клики на |-align="center"! <font color="black"><tex>7</tex>k</font>| <tex> вершинах ни цвета 1</tex>| <tex>7</tex>| <tex>23</tex>| <tex>[49, 61]</tex>| <tex>[80, 143]</tex>| <tex>[115, ни цвета 2298]</tex>| <tex>[205, противоречие. Следовательно 540]</tex>| <tex>r(k[217,k) \ge 2^{k1031]</2}tex>| <tex>[252, 1713]</tex>.}}| <tex>[292, 2826]</tex>{{Утверждение|id-align=ts2"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>|about-align=Следствие 2"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>|statement-align="center"! <font color=Для любых "black"><tex>10</tex></font>| <tex>1</tex>| <tex>k10</tex>| <tex>[40, 42]</tex>| <tex>[92, 149]</tex>| <tex>[149,m \in \mathbb N442]</tex> таких| <tex>[179, что 1171]</tex>2 \le k \le m| <tex>[289, 2826]</tex>| <tex>[343, выполняется неравенство 6090]</tex>| <tex>r(k[581,m) \ge 2^{k12677]</2}tex>| <tex>[798, 23556]</tex>|}}</center>

|id=def2 def4

Пусть <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=t3. 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>2)r(k},\;n_1,...,n_k) \le \frac{(n_1+n_2+...+n_k)!}{n_1!*n_2!*...*n_k!}</tex>

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

|id=def5.

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

{{Определение|id=def6|definition=Число <tex>m</tex> называется размерностью Заметим, что числа Рамсея размерности <tex>r_m(k;n_1,...,n_k)2</tex>.}}{{Утверждение|id=u2 |statement=1) Нетрудно понять что числа Рамсея размерности 2 — это определённые выше ранее числа Рамсея для клик.

|id=th5ter4|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>\alpharho:M^m\rightarrow</tex> \{1,2\} </tex> — произвольная раскраска в два цвета. Рассмотрим раскраску <tex>\alpharho': M_0^{m-1}\rightarrow</tex> \{1,2\}</tex> , определённую следующим образом: для каждого множества <tex>B \in M_0^{m-1}</tex> пусть <tex>\alpharho'(ВB) = \alpharho(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 \subset M_0</tex>, для которого <tex>\alpharho'(В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>\alpharho'(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>\alpharho(A)=1</tex> на всех <tex>A \in N^m_1</tex>, либо существует <tex>n_2</tex>-элементное подмножество <tex>N_2 \subset M_1</tex>, для которого <tex>\alpharho(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>\alpharho(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>\alpharho(A)=\alpharho'(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>\alpharho:M^m \rightarrow [1..\ldots k]</tex> в <tex>k</tex>цветов. Рассмотрим раскраску <tex>\alpharho':M^m \rightarrow </tex>\{<tex>0,k\}</tex>}, в которой цвета <tex>1,...\ldots,k-1</tex> раскраски <tex>\alpharho</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>\alpharho'(A)=0</tex> на всех <tex>A \in M_0^m</tex>, либо существует такое <tex>n_k</tex>-элементное подмножество <tex>M_k \subset M</tex>, что <tex>\alpharho(A)=\alpharho'(A)=k</tex> на всех <tex>A \in M^m_k</tex>. Во втором случае <tex>M_k</tex> — искомое подмножество, а в первом случае заметим, что на любом подмножестве <tex>A \in M_0^m</tex> из <tex>\alpharho'(A)=0</tex> следует <tex>\alpharho(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=def11def8

Пусть <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> с рёбрами цвета 2}}В принципе из результатов классической теории Рамсея понятие, что числа <tex>r(H_1,H_2)</tex> обязательно существуют (то есть, конечны). {{Лемма|id=lemma1|statement=Пусть <tex>m>1</tex>, а граф <tex>H</tex> таков, что <tex>v(H) \ge (m-1)(n-1)+1</tex> и <tex>\alpha(H) \le m-1</tex>. Тогда граф <tex>H</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах.|proof=Зафиксируем <tex>m</tex> и проведем индукцию по <tex>n</tex>. База для <tex>n=1</tex> очевидна. Докажем индукционный переход <tex>n-1 \rightarrow 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 m-1</tex>, следовательно <tex>v(H-U) \ge (m-1)(n-2)+1</tex> и очевидно <tex>\alpha(H-U) \le 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=th10 |author=V. Chvatal|statement=Пусть <tex>T_n</tex> — дерево на <tex>n</tex> вершинах. Тогда <tex>r(T_n,K_m)=(m-1)(n-1)+1</tex>.|proof=1) Докажем, что <tex>r(T_n,K_m) \ge (m-1)(n-1)+1</tex>. Для этого предъявим раскраску рёбер графа K_{(m-1)(n-1)}, в которой нет ни одного связного подграфа на <tex>n</tex> вершинах с рёбрами цвета 1 Существует и нет клики на <tex>m</tex> вершинах с рёбрами цвета 2. Разобьём вершины графа на <tex>m-1</tex> клику по <tex>n-1</tex> вершине и покрасим все рёбра этих клик в цвет 1. Тогда любой связный подграф с рёбрами цвета 1 содержит не более <tex>n-1</tex> вершины, в частности, нет подграфа с рёбрами цвета 1, изоморфного <tex>T_n</tex>. Рёбра цвета 2 (то есть, все оставшиеся рёбра) образуют <tex>(m-1)</tex>-дольный граф, в котором, очевидно, нет клики на <tex>m</tex> вершинах. 2) Рассмотрим произвольную раскраску рёбер полного графа <tex>K_{(m-1)(n-1)+1}</tex> в два цвета. Предположим, что не существует клики на <tex>m</tex> вершинах с рёбрами цвета 2. Тогда <tex>m>1</tex> и <tex>\alpha(G_1) \le m-1</tex>. По [[#lemma1|лемме]], граф <tex>G_1</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах в частности, дерево, изоморфное <tex>T_n</tex>.}} ==Индуцированная теорема Рамсея==Докажем похожее на теорему другое определение чисел Рамсея, но значительно более сложнее утверждение.{{Определение|id=def12 |definition=Пусть <tex>H</tex> — граф. Граф <tex>G</tex> называется рамсеееским графом для <tex>H</tex>, если при любой раскраске рёбер графа <tex>G</tex> в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G</tex> изоморфный <tex>H</tex>}}При замене произвольного графа <tex>H</tex> на клику мы получаем частный случай классической теоремы Рамсея. Для клики добавленное слово "индуцированный" ничего не меняет. Но значительно усложняет ситуацию для произвольного графа <tex>H</tex>. {{Теорема|id=th15. |about=Индуцированная теорема Рамсея|statement=Для любого графа существует рамсеевский граф}}===Случай двудольного графа===Здесь мы будем рассматривать двудольный граф <tex>G</tex>, как <tex>G=(V_1(G),V_2(G),E(G))</tex>, где <tex>V_1(G)</tex> и <tex>V_2(G)</tex> — разбиение множества вершин <tex>V(G)</tex> на две доли, а рёбра соединяют вершины из разных долейпроизвольных графов.

Пусть <tex>HH_1,GH_2</tex> — двудольные графы. Инъективное отображение <tex>\phi:V(H)\rightarrow V(G)'''Число Рамсея''' </tex> назовём погружением, если оно удовлетворяет двум условиям.<br>1)<tex>\phi(V_1(H)) \subset V_1r(G)H_1, \phi(V_2(H)) \subset v_2(GH_2)</tex><br>2)— это наименьшее из всех таких чисел <tex>\phi(u)\phi(v) x \in E(G)</tex> тогда и только тогда когда <tex>uv\in E(H)mathbb N</tex>В этом случае будем говорить, что двудольный граф <tex>H</tex> погружён в двудольный граф для любого графа <tex>G</tex> и использовать обозначение на <tex>\phi(H)=G(\phi(V(H)))</tex>}}{{Утверждение|statement=Отметим, что если существует погружение <tex>\phi</tex> двудольного графа <tex>Hx</tex> вершинах либо в двудольный граф <tex>G</tex> то индуцированный найдется подграф изоморфный <tex>\phi(H)H_1</tex> графа , либо в <tex>\overline G</tex> изоморфен <tex>H</tex>}}Напомним, что для множества <tex>X</tex> через <tex>X^k</tex> мы обозначаем множество всех <tex>k</tex>-элементных подмножеств множества найдется подграф изоморфный <tex>XH_2</tex>.{{Определение|definition=Назовем особым двудольный граф вида<tex>H=(V,V^k,E(H))</tex>, где <tex>E(H)=</tex>{<tex>xY|x\in V,Y\in V^k, x\in Y</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>v(H)</tex> {{---}} количество вершин в особый двудольный графе <tex>H</tex>. Тогда граф<tex>H</tex> содержит в качестве подграфа любое [[Основные определения теории графов#defTree|дерево]] на <tex>n</tex> вершинах.

Рассмотрим произвольный двудольный граф Зафиксируем <tex>Pm</tex>, пусть и проведем индукцию по <tex>V_1(P)=\{a_1,...,a_n\}, V_2(P)=\{b_1,...,b_n\}n</tex>. Положим<tex>V=\{x_1,...,x_n,y_1,...,y_n,z_1,...,z_m\}</tex>

Построим погружение '''База:''' для <tex>P</tex> в особый двудольный граф <tex>Hn=(V,V^{n+1},E)</tex>очевидно.

Изначально положим '''Индукционный переход:''' Пусть верно для <tex>n-1</tex>\phi(a_i)=x_i, докажем для <tex>n</tex>. Попробуем построить такое множество Рассмотрим произвольное дерево <tex>T_n</tex> на <tex>n</tex> вершинах, пусть дерево <tex>Y_j\in V^T_{n+-1}</tex>, что получено из <tex>\phi(b_j)=Y_jT_n</tex>удалением висячей вершины. По определению погружения и множества Пусть <tex>E(H)U</tex>, должно выполняться условие:— максимальное независимое множество вершин графа <brtex>H</tex>Y_j\cap\{x_1,...,x_n\}Тогда <tex>|U|=\phialpha(N_P(b_jH)\leqslant m-1</tex>Условие оставляет незаполненными , следовательно <tex>v(H-U) \geqslant (m-1)(n-2)+1</tex> и очевидно <tex>\alpha(H-d_P(b_jU)\ge leqslant m-1</tex> элементов множества .По индукционному предположению, граф <tex>Y_jH-U</tex> (единственное ограничение эти элементы не могут быть вершинами содержит в качестве подграфа дерево <tex>x_1,...,x_nT_{n-1}</tex>). Поместим в Пусть <tex>Y_ja</tex> элемент-индекс — вершина этого дерева, присоединив к которой висячую вершину, мы получим дерево <tex>z_jT_n</tex> (чтобы . Заметим, что множество <tex>Y_jU \not=Y_lcup</tex> при <tex>j \not=l{a\}</tex> не является независимым ввиду максимальности <tex>U</tex>. Следовательно, и дополним произвольно элементами из вершина <tex>a</tex> смежна хотя бы с одной вершиной <tex>x \in U</tex>y_1,...Отметим,y_nчто <tex>x</tex> не принадлежит множеству вершин графа <tex>T_{n-1}</tex>и, чтобы в множестве присоединив вершину <tex>x</tex> к вершине <tex>Y_ja</tex> было ровно дерева <tex>T_{n+-1}</tex>, получим дерево <tex>T_n</tex> в качестве подграфа графа <tex>H</tex> элементов.

 {{ЛеммаТеорема|id=ter5 |author=5, Теорема Хватала|statement=Для любого двудольного графа <tex>Hr(T_n,K_m)=(m-1)(n-1)+1</tex>, где <tex>T_n</tex> существует такой двудольный граф — дерево на <tex>Gn</tex>вершинах.|proof=Сперва докажем, что для любой раскраски <tex>r(T_n,K_m) \geqslant (m-1)(n-1)+1</tex>. Для этого предъявим раскраску рёбер графа <tex>GK_{(m-1)(n-1)}</tex> , в два которой нет ни одного связного подграфа на <tex>n</tex> вершинах с рёбрами цвета <tex>1</tex> и нет клики на <tex>m</tex> вершинах с рёбрами цвета обязательно существует погружение <tex>\phi2</tex> . Разобьём вершины графа на <tex>m-1</tex> клику по <tex>Hn-1</tex> вершине и покрасим все рёбра этих клик в граф цвет <tex>1</tex>. Тогда любой связный подграф с рёбрами цвета <tex>1</tex> содержит не более <tex>Gn-1</tex> вершины, в котором частности, нет подграфа с рёбрами цвета <tex>1</tex>, изоморфного <tex>T_n</tex>. Рёбра цвета <tex>2</tex> (то есть, все оставшиеся рёбра ) образуют <tex>\phi(Hm-1)</tex> одноцветны-дольный граф, в котором, очевидно, нет клики на <tex>m</tex> вершинах.Теперь воспользуемся вторым [[#def16|proof= определением]] числа Рамсея <tex>r(H_1, H_2)</tex>. Рассмотрим произвольный граф <tex>G</tex> на <tex>{{Утверждение|statement=Разумеется(m-1)(n-1)+1}</tex> вершинах. Предположим, указанный что в условии леммы граф графе <tex>G</tex> будет рамсеевским графом для не существует клики на <tex>Hm</tex>вершинах. Утверждение леммы более сильное: мы дополнительно требуемТогда <tex>m>1</tex> и <tex>\alpha( \overline G) \leqslant m-1</tex>. По [[#l1|лемме <tex>1</tex>]], чтобы все вершины одной доли граф <tex> \overline G</tex> содержит в качестве подграфа любое дерево на <tex>Hn</tex> можно было погрузить вершинах, в одну долю графа частности, дерево, изоморфное <tex>GT_n</tex>.

Можно считать, что элементы ==Индуцированная теорема Рамсея=={{Определение|id=def9|definition=Граф <tex>UH</tex> упорядоченыназывается '''индуцированным подграфом''' (англ. Тогда элементы каждого множества <tex>Y\in U^{2k-1}</tex> будут упорядочены. Обозначим через <tex>\sigma(Y''induced subgraph'')графа </tex> множество номеров <tex>kG</tex> элементов множества если две вершины в <tex>S(Y)H</tex> соединены ребром тогда и только тогда, когда они смежны в порядке элементов множества <tex>YG</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}Определение|id=def10|definition=Пусть </tex>цветов: цветом подмножества <tex>Y</tex> будет пара <tex>(\sigma(Y),c(Y))H</tex>— граф. Из выбора размера множества Граф <tex>UG</tex> будем называть '''рамсеевским графом''' (смангл. условие''Ramsey’s graph'') следует, что ceotcndetn такое подмножество для <tex>W\subset UH</tex>, что если при любой раскраске рёбер графа <tex>|W|=kn+k-1G</tex> и все подмножества в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>Y\subset W^{2k-1}</tex> имеют одинаковый цвет <tex>(\sigma(Y),c(Y))</tex> (не умаляя общности будем считать, что <tex>\sigma(Y)=\sigma, c(Y)=1)G</tex>. Мы найдём погружение графа изоморфный <tex>H</tex> в <tex>G(W)</tex>, все рёбра в котором покрашены в исходной раскраске в цвет 1 и тем самым докажем лемму.}}

Занумеруем элементы множества {{Определение|id=def11|definition='''Индуцированным числом Рамсея''' (англ. ''induced Ramsey’s number'') <tex>Wr_{ind}(H)</tex> в порядке их следования в для графа <tex>UH</tex>: пусть будем называть минимальное число <tex>W=x \in \{w_1mathbb N</tex>,такое что существует рамсеевский граф на <tex>x</tex> вершинах для графа <tex>H</tex>...,w_{kn+k-1}\}Заметим, что при замене произвольного графа <tex>H</tex>на клику мы получаем частный случай классической теоремы Рамсея. Введем обозначения

Положим <tex>\phi(a_i)=t_i</tex>. Остаётся корректно определить <tex>\phi(Z)</tex> для каждого множества <tex>Z\in V^k</tex>. Прежде чем построить <tex>\phi(Z)=Y\in U^{2k-1}</tex> мы положим <tex>S(Y)=\{\phi(x):x\in Z\}</tex>. Из определения погружения понятно, что тогда должно выполняться условие <tex>S(Y)Теорема|id=Y\cap T</tex>, а следовательно, нам нужно дополнить множество <tex>Y</tex> еще <tex>k-1</tex> элементами, не входящими в множество <tex>T</tex>. Мы сделаем это так, чтобы множество порядков номеров элементов множества <tex>S(Y)</tex> среди элементов множества <tex>Y</tex> было <tex>\sigma(Y)=\sigma</tex>: так как <tex>t_iter6 |about=w_ki</tex>6, не входящих в <tex>T</tex> элементов <tex>W</tex> хватит, чтобы обеспечить это.Индуцированная теорема Рамсея Так как по выбору множества <tex>W</tex> мы имеем <tex>\sigma(Y)|statement=\sigma</tex>, множество Для любого графа <tex>S(Y)H</tex> выбрано корректно и, опять же в силу выбора <tex>W</tex>, все рёбра особого двудольного графа существует рамсеевский граф <tex>G</tex> между вершинами из <tex>S(Y)=\{\phi(x):x\in Z\}</tex> и <tex>Y=\phi(Z)</tex> покрашены в цвет 1. В завершение остается лишь добавить, что при <tex>Z\not=Z'</tex> мы по построению имеем <tex>S(\phi(Z))\not=S(\phi(Z'))</tex>, поэтому <tex>\phi(Z)\not=\phi(Z')</tex>. Таким образом искомое погружение построено.

===Случай произвольного графа==={{Теорема|statement=Для произвольного графа Доказательство <texref>H</tex> существует рамсеевский граф.|proof=Пусть <tex>k=v(H),n=r(k,k)</tex>. Пронумеруем вершины графа <tex>H</tex>. Построим граф <tex>G^0</tex> следующим образом[https: разместим его вершины в виде таблице <tex>n \times C^k_n</tex>. Таким образом в каждом столбце вершины окажутся пронумерованы числами от 1 до <tex>n</tex>, как соответствующие строки таблицыmath. В каждом столбце одним из <tex>C^k_n</tex> способов разместим граф <tex>H</tex> (каждый столбец соответствует одному из возможных способов размещения)la. Все рёбра графа <tex>G^0</tex> будут рёбрами указанных копий графа <tex>H</tex>asu. Граф <tex>G^0<edu/tex> является <tex>n<~andrzej/tex>-дольным, его естественное разбиение на доли задаётся таблицей: <tex>V_i(G^0)<teach/tex> — это вершины, соответствующие <tex>i<mat598/tex> ряду таблицыlec8. Мы последовательно в несколько шагов будем перестраивать наш граф с помощью леммы, так, чтобы вершины последующих графов также разбивались на <tex>n</tex> долей и записывались в виде таблицы. Каждый шаг будет соответствовать одной паре строк таблицы. '''Шаг перестройки графа.''' Итак, пусть мы имеем <tex>n</tex>-дольный граф <tex>G^l</tex>, доли которого <tex>V_i=V_i(G^l)</tex> (где <tex>i\in [1..npdf Induced Ramsey Theorem Proof]</tex>). Пусть с парой строк (и, соответственно, долей) <tex>i,j</tex> мы еще не выполняли шаг. Очевидно, граф <tex>G_{i,j}=G^l(V_i\cup V_j)</tex> двудолен и для него по лемме существует двудольный рамсеевский граф <tex>P_{i,j}</tex>. Более того если вершины <tex>P_{i,j}</tex> разбиты на две доли <tex>W_i</tex> и <tex>W_j</tex>, то для любой раскраски рёбер в два цвета существует одноцветное погружение <tex>\phi</tex> графа <tex>G_{i,j}</tex> в <tex>P_{i,j}</tex> в котором <tex>\phi(V_i)\subset W_i</tex> и <tex>\phi(V_j)\subset W_j</tex>. Назовём таксе погружение одноцветным. Перейдём к построению <tex>G^{l+1}</tex>. Заменим <tex>V_i</tex> на <tex>W_i</tex> и <tex>V_j</tex> на <tex>W_j</tex>, проведем между этими долями все рёбра графа <texref>P_{iданной теоремы было приведено независимо различными математиками,j}</tex>. Наша цель в том, чтобы для любого погружения <tex>G_{i,j}</tex> в <tex>P_{i,j}</tex> была содержащая его копия <tex>G^l</tex> (причем доли этой копии лежали в соответствующих строках таблицы графа <tex>G^{l+1}</tex> Занумеруем всевозможные погружения <tex>G_{i,j}</tex> в <tex>P_{i,j}</tex>: пусть это <tex>G_{i,j}(1),...,G_{i,j}(q)</tex>. Каждому погружению <tex>G_{i,j}(s)</tex> мы поставим в соответствие отдельные копии всех отличных от <tex>V_i</tex> и <tex>V_j</tex> долей: <tex>V_1(s),...,V_n(s)</tex>. Положим <tex>V_i(s)=V(G_{i,j}(s))\cap W_i</tex> и <tex>V_j(s)=V(G_{i,j}(s))\cap W_j</tex>. На этих долях построим копию графа <tex>G^l</tex>однако благодаря ему получилось предоставить только очень грубые оценки значений индуцированных чисел Рамсея. В результате для каждого погружения графа <tex>G_{i,j}</tex> в <tex>P_{i,j}</tex> мы построили свою копию графа <tex>G^l</tex>данный момент проблема нахождения сколько-нибудь точных границ индуцированных чисел Рамсея является нерешенной задачей математики.

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

Итак, докажем, что <tex>G=G^{C^2_n}</tex> и есть рамсеевский граф для <tex>H</tex>=См. Пусть <tex>p_1,...,p_{C^2_n}</tex> — именно такая нумерация пар строк в нашей таблице, в порядке которой совершались шаги перестройки также==*[[Раскраска графа. Рассмотрим произвольную раскраску рёбер <tex>\rho</tex> ]]*[[Раскраска двудольного графа <tex>G</tex> в два цвета и докажем следующий факт.]]{{Утверждение|statement=Для каждого <tex>l\in *[[0..C^2_nТеорема Турана об экстремальном графе]]</tex> существует изоморфный <tex>G^l</tex> индуцированный подграф графа <tex>G</tex>, в котором для пар строк <tex>p_{l+1},...,p_{C^2_n}</tex> все рёбра между вершинами соответствующих пар строк в раскраске <tex>\rho</tex> одноцветны.|proof=Индукция с обратным ходом от <tex>l=C^2_n</tex> к <tex>l=0</tex>. База для <tex>l=C^2_n</tex> очевидна. Докажем переход <tex>l\rightarrow l-1</tex>

Итак рассмотрим наш изоморфный <tex>G^l</tex> подграф, который мы для простоты будем обозначать <tex>G^l</tex> и пару строку <tex>p_l</tex> в нем: пусть это строки <tex>i</tex> и <tex>j</tex>, a <tex>P_{i,j}</tex> и <tex>G_{i,j}</tex> — те двудольные графы между этими строками, что описаны в шаге построения. Так как <tex>P_{i,j}</tex> (подграф графа <tex>G^l</tex>) — рамсеевский граф для <tex>G_{i,j}</tex>, мы можем выбрать одноцветное в раскраске <tex>\rho</tex> погружение <tex>G_{i,j}</tex> в <tex>P_{i,j}</tex> и соответствующая ему по построению копия <tex>G^{l-1}</tex> будет искомым (из построения очевидно, что индуцированным!) подграфом <tex>G^l</tex> а значит, и <tex>G== Примечания==<references /tex> }}

Таким образом, существует изоморфный <tex>G^0<== Источники информации ==* [[wikipedia:Ramsey's theorem|Wikipedia — Ramsey's theorem]]* [[wikipedia:Ramsey theory|Wikipedia — Ramsey theory]]* [http:/tex> индуцированный под­граф графа <tex>G</tex>, в котором для каждой пары строк <tex>i,j<people.maths.ox.ac.uk/tex> все ребра между вершинами соответствующих строк одноцветны в раскраске <tex>\rho<~gouldm/tex>ramsey. Будем обозначать этот граф просто <tex>G^0<pdf Ramsey Theory]*[https:/tex>/vtechworks. Рассмотрим граф <tex>K_n<lib.vt.edu/tex>, вершины которого соответствуют строкам таблицы и покрасим каждое ребро в цвет, в который покрашены рёбра <tex>G^0<bitstream/handle/10919/32873/tex> между соответствующими строкамиDickson_JO_T_2011. Так как <tex>npdf?sequence=r(k,k)<1&isAllowed=y An Introduction to Ramsey Theory on Graphs]*[http:/tex>, существуют <tex>k</tex> вершин, между которыми все рёбра одноцветныwww.combinatorics. Рассмотрим столбец графа <tex>G^0<org/tex>, в котором <tex>H<ojs/tex> размещён именно в строчках, соответствующих этим <tex>k</tex> вершинамindex. Подграф <tex>H'<php/tex> графа <tex>G^0<eljc/tex> на вершинах этого столбца и соответствующих строчках изоморфен <tex>H<article/tex>, по построению является индуцированным подграфом графа <tex>G^0<view/tex> DS1| Small Ramsey Numbers by Stanisław Radziszowski][[Категория:Дискретная математика и все его рёбра одноцветны в раскраске <tex>\rho</tex>. Остаётся лишь заметить, что <tex>H'</tex> — индуцированный подграф графа <tex>G</tex>.алгоритмы]][[Категория:Дискретная математика]][[Категория:Теория графов]]}}[[Категория: Раскраски графов]]