442
правки
Изменения
→Источники информации
{{Определение
|id=def1
|definition='''Клика''' (англ. ''clique'') в [[Основные определения теории графов#Неориентированные графы|неориентированном графе ]] <tex>G = (V, E)</tex> {{---}} подмножество [[Основные определения теории графов#Неориентированные графы|вершин ]] <tex>C \subseteq V</tex>, такое что для любых двух различных вершин в <tex>C</tex> существует [[Основные определения теории графов#def_edge_und|ребро]], их соединяющее. Другими словами, клика графа <tex>G(V, E)</tex> {{---}} [[Основные определения теории графов#defFullGraph|полный]] подграф графа <tex>G(V, E)</tex>.}}
{{Определение
|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>r(3,3) = 6</tex>. Представим, что ребра <tex>K_6</tex> раскрашены в два цвета: красный и синий. Возьмем вершину <tex>v</tex>. Данной вершине, как и всем другим, инцидентны <tex>5</tex> рёбер, тогда, согласно принципу Дирихле, хотя бы три из них одного цвета. Для определенности положим, что хотя бы <tex>3</tex> ребра, соединяющие вершину <tex>v</tex> с вершинами <tex>r</tex>, <tex>s</tex>, <tex>t</tex>, синие. Если хотя бы одно из ребер <tex>rs</tex>, <tex>rt</tex>, <tex>st</tex> синее, то в графе есть синий треугольник (полный граф на трёх вершинах), иначе, если они все красные, есть красный треугольник. Таким образом, <tex>r(3,3) \leqslant 6 </tex>.
Чтобы доказать, что <tex>r(3,3) = 6 </tex>, предъявим такую раскраску графа <tex>K_5</tex>, где нет клики на трех вершинах ни синего, ни красного цвета. Такая раскраска представлена на рисунке справа. Понятно, что предъявлять отдельные раскраски для <tex> K_4</tex>, <tex>K_3</tex> не нужно, так как достаточно взять соответствующие подграфы раскрашенного <tex>K_5</tex>.
===Теорема Рамсея. Оценки сверху===
{{Теорема|id=ter1|about=1, Теорема Рамсея
|statement= Для любых <tex>n,m \in \mathbb N</tex> существует число <tex>r(n,m)</tex>, при этом <tex>r(n,m) \le leqslant r(n,m-1)+r(n-1,m)</tex>, а также если числа <tex>r(n,m-1)</tex> и <tex>r(n-1,m)</tex> четные, то неравенство принимает вид <tex>r(n,m) \le leqslant r(n,m-1)+r(n-1,m) - 1</tex> .
|proof=
}}
{{Утверждение|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=ter2|about=2, Теорема Эрдеша|statement=Для любого натурального числа <tex>k \ge geqslant 2</tex> выполняется неравенство <tex>r(k,k) \ge kgeqslant 2^{k/2}</tex>
|proof=
Так как <tex>r(2,2)=2</tex>, достаточно рассмотреть случай <tex>k \ge geqslant 3</tex>.Зафиксируем множество различных помеченных вершин <tex>v_i,\ldots,v_n</tex>. Пусть <tex>g(n,k)</tex> {{---}} доля среди всех помеченных графов на вершинах <tex>v_i,\ldots,v_nn</tex> вершинах тех графов, что содержат клику на <tex>k</tex> вершинах. Всего графов на наших вершинах, очевидно <tex>2^{C^2_n}</tex> (каждое из возможных рёбер <tex>C^2_n</tex> можно провести или не провести).
Посчитаем графы с кликой на <tex>k</tex> вершинах следующим образом: существует <tex>C^k_n</tex> способов выбрать <tex>k</tex> вершин для клики в нашем множестве, после чего все рёбра между ними будем считать проведенными, а остальные ребра выбираются произвольно. Таким образом, каждый граф с кликой на <tex>k</tex> вершинах будет посчитан, причём некоторые даже более одного раза. Количестве графов с кликой оказывается не более, чем <tex>C^k_n\cdot 2^{C^2_n-C^2_k}</tex>. Следовательно,
<tex>g(n,k) \le leqslant \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>(*)</tex>
Подставив <tex>n<2^{k/2}</tex> в неравенство <tex>(*)</tex> мы получаем
<tex>g(n,k)<\dfrac{2^{k^2/2}\cdot 2^{-C^2_k}}{k!}=\dfrac{2^{k/2}}{k!}<\dfrac12</tex> при <tex>k \ge geqslant 3</tex>
Предположим, что <tex>r(k,k)=n<2^{k/2}</tex> и разобьём все графы на <tex>n</tex> вершинах на пары <tex>\langle G, \overline G\rangle</tex> (граф и его дополнение) . Так как <tex>g(n,k)<\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>12</tex>, получили противоречи противоречие. Значит <tex>n</tex> было выбрано неверно. Из этого следует <tex>r(k,k) \ge geqslant 2^{k/2}</tex>.
}}
===Значения чисел Рамсея===
Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, их известно довольно мало. Далее приведена таблица Станислава Радзишевского <ref>[http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1| Small Ramsey Numbers by Stanisław Radziszowski]</ref>, в которой присутствуют практически все известные числа Рамсея или же промежутки, в которых они находятся.
<center>
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
{{Теорема
|id=ter3|about=3,Теорема Рамсея для нескольких цветов
|statement=<tex>\forall k, n_1, \ldots n_k \in \mathbb N </tex> существует соответственное число Рамсея <tex>r(n_1,\ldots,n_k)</tex>, при этом <tex>r(n_1,\ldots,n_k)\leqslant r(n_1,\ldots, n_{k-2}, r(n_{k-1},\;n_k)).</tex>
|proof=
Возьмем граф из <tex>r(n_1,\ldots, n_{k-2}, r(n_{k-1}, n_k))</tex> вершин и окрасим его рёбра в <tex>k</tex> цветов. Пока что будем считать цвета <tex>k-1</tex> и <tex>k</tex> одним цветом. Тогда граф будет <tex>(k-1)</tex>-цветным. Согласно определению числа Рамсея <tex>r(n_1,\ldots,n_{k-2},r(n_{k-1},n_k))</tex>, такой граф либо содержит <tex>K_{n_i}</tex> для некоторого цвета <tex>i</tex>, такого что <tex>1\leqslant i\leqslant k-2</tex> , либо <tex>K_{r(k, n_{k-1},n_k)}</tex>, окрашенный общим цветом <tex>k-1</tex> и <tex>k</tex>. В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный <tex>r(n_{k-1},n_k)</tex> — вершинный граф содержит либо <tex>K_{n_{k-1}}</tex> цвета <tex>k-1</tex>, либо <tex>K_{n_k}</tex> цвета <tex>k</tex>. Таким образом любое число Рамсея для раскраски в <tex>k</tex> цветов ограничено некоторым числом Рамсея для меньшего количества цветов, следовательно, <tex>r(n_1,\ldots,n_k)</tex> существует для любых <tex> k, n_1, \ldots n_k, \in \mathbb N </tex>, и теорема доказана.
}}
|id=def5
|definition=
Пусть <tex>m,k,n_1,\ldots ,n_k \in \mathbb N</tex>, причём <tex>n_1,\ldots ,n_k \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(k;n_1,\ldots ,n_k)</tex>.
}}
Заметим, что числа Рамсея размерности <tex>2</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=def8
|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_2</tex> — графы. '''Число Рамсея''' <tex>r(H_1,H_2)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что для любого графа <tex>G</tex> на <tex>x</tex> вершинах либо в <tex>G</tex> найдется подграф изоморфный <tex>H_1</tex>, либо в <tex>\overline G</tex> найдется подграф изоморфный <tex>H_2</tex>. }}Несложно показать, что эти определения эквивалентны (аналогично определениям для классических чисел Рамсея). Из результатов классической теории Рамсея становится понятно, что числа <tex>r(H_1,H_2)</tex> существуют.
{{Лемма
|id=l1|about=1|statement=Пусть <tex>m>1</tex>, а граф <tex>H</tex> таков, что <tex>v(H) \ge geqslant (m-1)(n-1)+1</tex> и <tex>\alpha(H) \le leqslant m-1</tex>, где <tex>v(H)</tex> {{---}} количество вершин в графе <tex>H</tex>. Тогда граф <tex>H</tex> содержит в качестве подграфа любое [[Основные определения теории графов#defTree|дерево ]] на <tex>n</tex> вершинах.
|proof=
Зафиксируем <tex>m</tex> и проведем индукцию по <tex>n</tex>.
'''База:''' для <tex>n=1</tex> очевидно.
'''Индукционный переход:''' Пусть верно для <tex>n-1</tex>, докажем для <tex>n</tex>. Рассмотрим произвольное дерево <tex>T_n</tex> на <tex>n</tex> вершинах, пусть дерево <tex>T_{n-1}</tex> получено из <tex>T_n</tex> удалением висячей вершины. Пусть <tex>U</tex> — максимальное независимое множестве множество вершин графа <tex>H</tex>. Тогда <tex>|U|=\alpha(H) \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>r(T_n,K_m)=(m-1)(n-1)+1</tex>, где <tex>T_n</tex> — дерево на <tex>n</tex> вершинах.
|proof=
==Индуцированная теорема Рамсея==
{{Определение
|id=def9
|definition=Граф <tex>H</tex> называется '''индуцированным подграфом ''' (англ. ''induced subraphsubgraph'') графа <tex>G</tex> если две вершины в <tex>H</tex> соединены ребром тогда и только тогда, когда они смежны в <tex>G</tex>. }}
{{Определение
|id=def10
|definition=Пусть <tex>H</tex> — граф. Граф <tex>G</tex> будем называть '''рамсеевским графом''' (англ. ''Ramsey’s graph'') для <tex>H</tex>, если при любой раскраске рёбер графа <tex>G</tex> в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G</tex> изоморфный <tex>H</tex>.}}
{{Определение
|id=def11
|definition='''Индуцированным числом Рамсея'''(англ. ''induced Ramsey Ramsey’s number'') <tex>r_{ind}(H)</tex> для графа <tex>H</tex> будем называть минимальное число <tex>x \in \mathbb N</tex>, такое что существует рамсеевский граф на <tex>x</tex> вершинах для графа <tex>H</tex> на .}}Заметим, что при замене произвольного графа <tex>xH</tex> вершинахна клику мы получаем частный случай классической теоремы Рамсея.}}
{{Теорема
|id=ter6
|about=6, Индуцированная теорема Рамсея
|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> на две доли, а рёбра соединяют вершины из разных долей.{{Определение|id=def11|definition=Пусть <tex>H,G</tex> — двудольные графы. Инъективное отображение <tex>\phi:V(H)\rightarrow V(G)</tex> назовём '''погружением''' (англ. ''immersion''), если оно удовлетворяет двум условиям.<br><tex>1)</tex><tex>\phi(V_1(H)) \subset V_1(G), \phi(V_2(H)) \subset v_2(G)</tex><br><tex>2)</tex><tex>\phi(u)\phi(v) \in E(G)</tex> тогда и только тогда когда <tex>uv\in E(H)</tex>Будем говорить, что двудольный граф <tex>H</tex> погружён в двудольный существует рамсеевский граф <tex>G</tex> и использовать обозначение <tex>\phi(H)=G(\phi(V(H)))</tex>}}{{Лемма|id=l2|about=2|statement=Любой двудольный граф может быть погружен в особый двудольный граф.|proof=Рассмотрим произвольный двудольный граф <tex>P</tex>, пусть <tex>V_1(P)=\{a_1,...,a_n\}, V_2(P)=\{b_1,...,b_n\}</tex>. Положим<tex>V=\{x_1,...,x_n,y_1,...,y_n,z_1,...,z_m\}</tex> Построим погружение <tex>P</tex> в особый двудольный граф <tex>H=(V,V^{n+1},E)</tex>. Изначально положим <tex>\phi(a_i)=x_i</tex>. Попробуем построить такое множество <tex>Y_j\in V^{n+1}</tex>, что <tex>\phi(b_j)=Y_j</tex>. По определению погружения и множества <tex>E(H)</tex>, должно выполняться условие:<br><tex>Y_j\cap\{x_1,...,x_n\}=\phi(N_P(b_j)</tex>Условие оставляет незаполненными <tex>n+1-d_P(b_j)\ge 1</tex> элементов множества <tex>Y_j</tex> (единственное ограничение эти элементы не могут быть вершинами <tex>x_1,...,x_n</tex>). Поместим в <tex>Y_j</tex> элемент-индекс <tex>z_j</tex> (чтобы <tex>Y_j\not=Y_l</tex> при <tex>j \not=l</tex>, и дополним произвольно элементами из <tex>y_1,...,y_n</tex>, чтобы в множестве <tex>Y_j</tex> было ровно <tex>n+1</tex> элементов.
}}
==См. также==
* [[wikipedia:Ramsey's theorem|Wikipedia — Ramsey's theorem]]
* [[wikipedia:Ramsey theory|Wikipedia — Ramsey theory]]
* [http://people.maths.ox.ac.uk/~gouldm/ramsey.pdf Ramsey Theory]
*[https://vtechworks.lib.vt.edu/bitstream/handle/10919/32873/Dickson_JO_T_2011.pdf?sequence=1&isAllowed=y An Introduction to Ramsey Theory on Graphs]
*[http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1| Small Ramsey Numbers by Stanisław Radziszowski]
[[Категория:Дискретная математика и алгоритмы]]
[[Категория:Дискретная математика]]
[[Категория:Теория графов]]
[[Категория: Раскраски графов]]