442
правки
Изменения
→Источники информации
==Числа Рамсея==
{{Определение
|id=def1
|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> .
|proof=
# Докажем с помощью метода математической индукции по <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>
|proof=
Очевидно, <tex>C^{n-1}_{n+m-2}=1</tex> при <tex>n=1</tex> или <tex>m=1</tex>, как и соответствующие числа Рамсея. Индукцией по <tex>n</tex> и <tex>m</tex> при <tex>n,m \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не провести).
Предположим, что <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> в неравенство '''*''' мы получаем.}}
===Свойства чисел Рамсея===Следующими свойствами удобно пользоваться при подсчете значений чисел Рамсея <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>
===Числа Рамсея для раскрасок в несколько цветов===
Теперь обобщим числа Рамсея на произвольное количество цветов.
{{Определение
|id=def3 def4
|definition=
}}
{{Теорема
|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>2)r(k},\;n_1,...,n_k) \le \frac{(n_1+n_2+...+n_k)!}{n_1!*n_2!*...*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 доказательства [[#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>\fracr(n_{(n_1+n_2+...+k-1},n_k)!}</tex> — вершинный граф содержит либо <tex>K_{n_1!*n_2!*...*n_k!}=\sum\limits_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 неравенство из данной [[#ter3|теоремы]] выводится из неравенства 1 по индукциии теорема доказана.
}}
==Числа Рамсея больших размерностей==
{{Определение
|id=def5
|definition=
Пусть <tex>m,k,n_1,\ldots ,n_k \in \mathbb N</tex>, причём <tex>n_1,\ldots ,n_k \geqslant m</tex>. '''Число Рамсея''' <tex>r_m(n_1,\ldots ,n_k)</tex> — наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске <tex>m</tex> называется -элементных подмножеств <tex>x</tex>-элементного множества <tex>M</tex> в <tex>k</tex> цветов для некоторого <tex>i \in [1\ldots k]</tex> обязательно найдётся такое множество <tex>W_i</tex>, что <tex>|W_i|=n_i</tex> и все <tex>m</tex>-элементные подмножества множества <tex>W_i</tex> имеют цвет <tex>i</tex>. Число <tex>m</tex> называют '''размерностью ''' числа Рамсея <tex>r_m(k;n_1,...\ldots ,n_k)</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> существует(то есть, конечно).
|proof=
}}
Еще один способ обобщения классической теории Рамсея — замена клик на произвольные графы-шаблоны.
{{Определение
|id=def7def8|definition=Пусть <tex>H_1,H_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_2H_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> с рёбрами цвета 1 или , либо в <tex>\overline G</tex> найдется подграф изоморфный <tex>H_2</tex> с рёбрами цвета 2.
}}
{{Лемма
|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> вершинах.
|proof=
Зафиксируем <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>.
}}
{{Теорема
|id=ter5
|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> вершинах.
|proof=
}}
==Индуцированная теорема Рамсея==
{{Определение
|id=def12 def9|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=th15. |about=Индуцированная теорема Рамсея|statement=Для любого графа существует рамсеевский граф}}===Случай двудольного графа===Здесь мы будем рассматривать двудольный граф <tex>G</tex>, как
{{Определение|id=def10|definition=Пусть <tex>H</tex> — граф. Граф <tex>G=(V_1</tex> будем называть '''рамсеевским графом''' (Gангл. ''Ramsey’s graph'')для <tex>H</tex>,V_2(если при любой раскраске рёбер графа <tex>G),E(</tex> в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G))</tex>,изоморфный <tex>H</tex>.}}
{{Определение
|id=def16def11|definition=Пусть <tex>H,G</tex> — двудольные графы. Инъективное отображение <tex>\phi:V(H)\rightarrow V'''Индуцированным числом Рамсея''' (G)</tex> назовём погружением, если оно удовлетворяет двум условиямангл.<br>1''induced Ramsey’s number'')<tex>\phi(V_1r_{ind}(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>x \phi(H)=G(in \phi(V(H)))mathbb N</tex>}}{{Утверждение|statement=Отметим, такое что если существует погружение <tex>\phi</tex> двудольного графа <tex>H</tex> в двудольный рамсеевский граф на <tex>G</tex> то индуцированный подграф <tex>\phi(H)x</tex> вершинах для графа <tex>G</tex> изоморфен <tex>H</tex>.}}НапомнимЗаметим, что для множества при замене произвольного графа <tex>X</tex> через <tex>X^kH</tex> на клику мы обозначаем множество всех <tex>k</tex>-элементных подмножеств множества <tex>X</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>}}}
}}