Теория Рамсея — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Числа Рамсея для раскрасок в несколько цветов)
(Метки: правка с мобильного устройства, правка из мобильной версии)
(Источники информации)
 
(не показаны 32 промежуточные версии 5 участников)
Строка 3: Строка 3:
 
{{Определение
 
{{Определение
 
|id=def1
 
|id=def1
|definition='''Клика''' (англ. ''clique'') в неориентированном графе <tex>G(V, E)</tex> {{---}} подмножество вершин <tex>C \subseteq V</tex>, такое что для любых двух различных вершин в <tex>C</tex> существует ребро, их соединяющее. Другими словами, клика графа <tex>G(V, E)</tex> {{---}} полный подграф графа <tex>G(V, E)</tex>. }}
+
|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
 
|id=def2
Строка 17: Строка 17:
 
===Пример===
 
===Пример===
 
Чтобы получить лучшее представление природы чисел Рамсея, приведем пример. Докажем, что <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_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>.
+
Чтобы доказать, что <tex>r(3,3) = 6 </tex>, предъявим такую раскраску графа  <tex>K_5</tex>, где нет клики на трех вершинах ни синего, ни красного цвета. Такая раскраска представлена на рисунке справа. Понятно, что предъявлять отдельные раскраски для <tex> K_4</tex>, <tex>K_3</tex> не нужно,  так как достаточно взять  соответствующие подграфы раскрашенного <tex>K_5</tex>.
  
 
===Теорема Рамсея. Оценки сверху===
 
===Теорема Рамсея. Оценки сверху===
Строка 24: Строка 24:
 
|proof=
 
|proof=
  
<tex>1)</tex> Докажем с помощью метода математической индукции по <tex>n+m</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)+r(n,\;m-1)</tex> вершин. Возьмём произвольную вершину <tex>v</tex> и обозначим через <tex>M</tex> и <tex>N</tex> множества вершин, инцидентных <tex>v</tex> в чёрном и белом подграфе соответственно. Так как в графе <tex>r(n-1,\;m)+r(n,\;m-1)=|M|+|N|+1 </tex>  вершин, согласно принципу Дирихле, либо <tex>|M|\geqslant r(n-1,\;m)</tex>, либо <tex>|N|\geqslant r(n,\;m-1)</tex>. Пусть <tex>|M|\geqslant r(n-1,\;m)</tex>. Тогда либо в <tex>M</tex> существует белый <tex>K_m</tex>, что доказывает теорему, либо в <tex>M</tex> есть чёрный <tex>K_{n-1}</tex>, который вместе с <tex>v</tex> образует чёрный <tex>K_n</tex>, в этом случае теорема также доказана. Случай <tex>|N|\geqslant r(n,\;m-1)</tex> рассматривается аналогично.
 
+
# Предположим, <tex>p=r(n-1,\;m)</tex> и <tex>q=r(n,\;m-1)</tex> оба чётны. Положим <tex>s=p+q-1</tex> и рассмотрим чёрно-белый граф из <tex>s</tex> вершин. Если <tex>d_i</tex> степень <tex>i</tex>-й вершины в чёрном подграфе, то, согласно [[Лемма о рукопожатиях|лемме о рукопожатиях]], <tex> \sum\limits_{i=1}^s d_i</tex> — чётно. Поскольку <tex>s</tex> нечётно, должно существовать чётное <tex>d_i</tex>. Не умаляя общности, положим, что <tex>d_1</tex> чётно. Обозначим через <tex>M</tex> и <tex>N</tex> вершины, инцидентные вершине <tex>1</tex> в чёрном и белом подграфах соответственно. Тогда <tex>|M|=d_1</tex> и <tex>|N|=s-1-d_1</tex> оба чётны. Согласно принципу Дирихле, либо <tex>|M|\geqslant p-1</tex>, либо <tex>|N|\geqslant q</tex>. Так как <tex>|M|</tex> чётно, а <tex>p-1</tex> нечётно, первое неравенство можно усилить, так что либо <tex>|M|\geqslant p</tex>, либо <tex>|N|\geqslant q</tex>. <br> Далее проводим рассуждения, аналогичные тем, что присутствуют в первом пункте теоремы. Таким образом,  <tex>r(n,m) \leqslant r(n,m-1)+r(n-1,m) - 1</tex>.
'''База:''' <tex>r(n,\;1) = r(1,\;n) = 1</tex>, так как граф, состоящий из одной вершины, можно считать полным графом любого цвета.
 
 
 
'''Индукционный переход:''' Пусть <tex>n>1</tex> и <tex>m>1</tex>. Рассмотрим полный чёрно-белый граф из <tex>r(n-1,\;m)+r(n,\;m-1)</tex> вершин. Возьмём произвольную вершину <tex>v</tex> и обозначим через <tex>M</tex> и <tex>N</tex> множества, инцидентные <tex>v</tex> в чёрном и белом подграфе соответственно. Так как в графе <tex>r(n-1,\;m)+r(n,\;m-1)=|M|+|N|+1 </tex>  вершин, согласно принципу Дирихле, либо <tex>|M|\geqslant r(n-1,\;m)</tex>, либо <tex>|N|\geqslant r(n,\;m-1)</tex>. Пусть <tex>|M|\geqslant r(n-1,\;m)</tex>. Тогда либо в <tex>M</tex> существует белый <tex>K_m</tex>, что доказывает теорему, либо в <tex>M</tex> есть чёрный <tex>K_{n-1}</tex>, который вместе с <tex>v</tex> образует чёрный <tex>K_n</tex>, в этом случае теорема также доказана. Случай <tex>|N|\geqslant r(n,\;m-1)</tex> рассматривается аналогично.
 
 
 
<tex>2)</tex>  Предположим, <tex>p=r(n-1,\;m)</tex> и <tex>q=r(n,\;m-1)</tex> оба чётны. Положим <tex>s=p+q-1</tex> и рассмотрим чёрно-белый граф из <tex>s</tex> вершин. Если <tex>d_i</tex> степень <tex>i</tex>-й вершины в чёрном подграфе, то, согласно [[Лемма о рукопожатиях|лемме о рукопожатиях]], <tex>\sum_{i=1}^s d_i</tex> — чётно. Поскольку <tex>s</tex> нечётно, должно существовать чётное <tex>d_i</tex>. Не умаляя общности, положим, что <tex>d_1</tex> чётно. Обозначим через <tex>M</tex> и <tex>N</tex> вершины, инцидентные вершине <tex>1</tex> в чёрном и белом подграфах соответственно. Тогда <tex>|M|=d_1</tex> и <tex>|N|=s-1-d_1</tex> оба чётны. Согласно принципу Дирихле, либо <tex>|M|\geqslant p-1</tex>, либо <tex>|N|\geqslant q</tex>. Так как <tex>|M|</tex> чётно, а <tex>p-1</tex> нечётно, первое неравенство можно усилить, так что либо <tex>|M|\geqslant p</tex>, либо <tex>|N|\geqslant q</tex>.
 
 
 
Далее проводим рассуждения, аналогичные тем, что присутствуют в первом пункте теоремы. Таким образом,  <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) \leqslant C_{n+m-2}^{n-1}</tex>
 
{{Утверждение|id=u1|about=1|statement=Для натуральных чисел <tex>m,n</tex> выполняется равенство <tex>r(n,m) \leqslant C_{n+m-2}^{n-1}</tex>
Строка 42: Строка 35:
 
===Оценки снизу===
 
===Оценки снизу===
  
{{Теорема|id=ter2|about=2, Эрдеша
+
{{Теорема|id=ter2|about=2, Теорема Эрдеша
 
|statement=Для любого натурального числа <tex>k \geqslant 2</tex> выполняется неравенство <tex>r(k,k) \geqslant 2^{k/2}</tex>
 
|statement=Для любого натурального числа <tex>k \geqslant 2</tex> выполняется неравенство <tex>r(k,k) \geqslant 2^{k/2}</tex>
 
|proof=
 
|proof=
Строка 50: Строка 43:
 
Посчитаем графы с кликой на <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>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) \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}{k!\cdot 2^{C^2_k}}</tex> <tex>(*)</tex>
+
<tex>g(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>(*)</tex>
  
 
Подставив <tex>n<2^{k/2}</tex> в неравенство <tex>(*)</tex> мы получаем
 
Подставив <tex>n<2^{k/2}</tex> в неравенство <tex>(*)</tex> мы получаем
Строка 66: Строка 59:
  
 
===Значения чисел Рамсея===
 
===Значения чисел Рамсея===
Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, их известно довольно мало. Далее приведена таблица Станислава Радзишевского <ref>[http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1| Small Ramsey Numbers by  Stanisław Radziszowski]</ref>, в которой присутствуют  практически все известные числа Рамсея или же промежутки, в которых они находятся.
+
Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, их известно довольно мало. Далее приведена таблица Станислава Радзишевского, в которой присутствуют  практически все известные числа Рамсея или же промежутки, в которых они находятся.
 
<center>
 
<center>
 
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
 
{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"
Строка 228: Строка 221:
 
}}
 
}}
 
Заметим, что числа Рамсея размерности <tex>2</tex> — это определённые ранее числа Рамсея для клик.
 
Заметим, что числа Рамсея размерности <tex>2</tex> — это определённые ранее числа Рамсея для клик.
 
 
{{Определение
 
|id=def7|definition=
 
Для каждого множества <tex>M</tex> через <tex>M^k</tex> мы будем обозначать множество всех <tex>k</tex>-элементных подмножеств <tex>M</tex>.
 
}}
 
  
 
{{Теорема
 
{{Теорема
Строка 239: Строка 226:
 
|statement=Пусть <tex>m,k,n_1,\ldots,n_k</tex> {{---}} натуральные числа, причем <tex>k \geqslant 2</tex>, а <tex>n_1,\ldots ,n_k \geqslant m</tex>. Тогда существует число Рамсея <tex>r_m(n_1,\ldots n_k)</tex>.  
 
|statement=Пусть <tex>m,k,n_1,\ldots,n_k</tex> {{---}} натуральные числа, причем <tex>k \geqslant 2</tex>, а <tex>n_1,\ldots ,n_k \geqslant m</tex>. Тогда существует число Рамсея <tex>r_m(n_1,\ldots n_k)</tex>.  
 
|proof=
 
|proof=
<tex>1)</tex> Мы будем доказывать теорему по индукции. Начнем со случая <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 \leqslant p=r_{m-1}(r_m(n_1-1,n_2),r_m(n_1,n_2-1))</tex>.
+
# Мы будем доказывать теорему по индукции. Начнем со случая <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 \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>\rho'(B) = \rho(B \cup \{ a \})</tex>. <br> Так как <tex>|M_0|=p</tex>, либо существует <tex>r_m(n_1 — 1,n_2)</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>. Во втором случае искомое подмножество найдено (это <tex>N_2</tex>), рассмотрим первый случай и множество <tex>N=N_1 \cup \{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^{m-1} \subset 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_1,\ldots ,n_{k-1}),n_k)</tex>. <br> Для этого мы рассмотрим множество <tex>M</tex> на <tex>q</tex> вершинах и произвольную раскраску <tex>\rho:M^m \rightarrow [1 \ldots k]</tex> в <tex>k</tex>цветов. Рассмотрим раскраску <tex>\rho':M^m \rightarrow \{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_1,\ldots ,n_{k-1})</tex> и <tex>\rho'(A)=0</tex> на всех <tex>A \in M_0^m</tex>, либо существует такое <tex>n_k</tex>-элементное подмножество <tex>M_k \subset M</tex>, что <tex>\rho(A)=\rho'(A)=k</tex> на всех <tex>A \in M^m_k</tex>. Во втором случае <tex>M_k</tex> — искомое подмножество, а в первом случае заметим, что на любом подмножестве <tex>A \in M_0^m</tex> из <tex>\rho'(A)=0</tex> следует <tex>\rho(A) \in [1 \ldots k-1]</tex>. Исходя из размера множества <tex>M_0</tex> по индукционному предположению получаем, что найдется искомое подмножество множества <tex>M</tex> для одного из цветов <tex>1,\ldots ,k-1</tex>, таким образом неравенство доказано, а из этого следует и существование числа Рамсея <tex>r_m(n_1,\ldots ,n_k)</tex>.  
Рассмотрим <tex>(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>\rho'(B) = \rho(B \cup \{ a \})</tex>.
 
Так как <tex>|M_0|=p</tex>, либо существует <tex>r_m(n_1 — 1,n_2)</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>.
 
По индукционному предположен из <tex>|M_1|=r_m(n_1-1,n_2)</tex> следует, что либо существует <tex>n_1-1</tex>-элементное подмножество <tex>N_1 \subset M_1</tex>,  <tex>\rho(A)=1</tex> на всех <tex>A \in N^m_1</tex>, либо существует <tex>n_2</tex>-элементное подмножество <tex>N_2 \subset M_1</tex>,  <tex>\rho(A)=2</tex> на всех <tex>A \in N_2^m</tex>. Во втором случае искомое подмножество найдено (это <tex>N_2</tex>), рассмотрим первый случай и множество <tex>N=N_1 \cup \{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^{m-1} \subset M_1^{m-1}</tex> и поэтому <tex>\rho(A)=\rho'(A \setminus \{a \})=1</tex>. Учитывая, что <tex>|N|=n_1</tex>, мы нашли искомое подмножество и в этом случае.
 
 
 
<tex>2)</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_1,\ldots ,n_{k-1}),n_k)</tex>
 
 
 
Для этого мы рассмотрим множество <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_1,\ldots ,n_{k-1})</tex> и <tex>\rho'(A)=0</tex> на всех <tex>A \in M_0^m</tex>, либо существует такое <tex>n_k</tex>-элементное подмножество <tex>M_k \subset M</tex>, что <tex>\rho(A)=\rho'(A)=k</tex> на всех <tex>A \in M^m_k</tex>. Во втором случае <tex>M_k</tex> — искомое подмножество, а в первом случае заметим, что на любом подмножестве <tex>A \in M_0^m</tex> из <tex>\rho'(A)=0</tex> следует <tex>\rho(A) \in [1 \ldots k-1]</tex>. Исходя из размера множества <tex>M_0</tex> по индукционному предположению получаем, что найдется искомое подмножество множества <tex>M</tex> для одного из цветов <tex>1,\ldots ,k-1</tex>, таким образом неравенство доказано, а из этого следует и существование числа Рамсея <tex>r_m(n_1,\ldots ,n_k)</tex>.  
 
 
}}
 
}}
  
Строка 256: Строка 235:
 
|id=def8
 
|id=def8
 
|definition=
 
|definition=
Пусть <tex>H_1,H_2</tex> — графы. '''Число Рамсея''' <tex>r(H_1,H_2)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в два цвета обязательно найдется подграф, изоморфный <tex>H_1</tex> с рёбрами цвета <tex>1</tex> или подграф изоморфный <tex>H_2</tex> с рёбрами цвета <tex>2</tex>.  
+
Пусть <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>.  
 
}}
 
}}
 
Существует и другое определение чисел Рамсея для произвольных графов.
 
Существует и другое определение чисел Рамсея для произвольных графов.
Строка 267: Строка 246:
  
 
{{Лемма
 
{{Лемма
|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> содержит в качестве подграфа любое дерево на <tex>n</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> вершинах.
 
|proof=
 
|proof=
 
Зафиксируем <tex>m</tex> и проведем индукцию по <tex>n</tex>.  
 
Зафиксируем <tex>m</tex> и проведем индукцию по <tex>n</tex>.  
Строка 273: Строка 252:
 
'''База:''' для <tex>n=1</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) \leqslant m-1</tex>, следовательно <tex>v(H-U) \geqslant (m-1)(n-2)+1</tex> и очевидно <tex>\alpha(H-U) \leqslant m-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) \leqslant m-1</tex>, следовательно <tex>v(H-U) \geqslant (m-1)(n-2)+1</tex> и очевидно <tex>\alpha(H-U) \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</tex> не принадлежит множеству вершин графа <tex>T_{n-1}</tex> и, присоединив вершину <tex>x</tex> к вершине <tex>a</tex> дерева <tex>T_{n-1}</tex>, получим дерево <tex>T_n</tex> в качестве подграфа графа <tex>H</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</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  
 
|id=ter5  
|author=5, Хватала
+
|author=5, Теорема Хватала
 
|statement=<tex>r(T_n,K_m)=(m-1)(n-1)+1</tex>, где <tex>T_n</tex> — дерево на <tex>n</tex> вершинах.
 
|statement=<tex>r(T_n,K_m)=(m-1)(n-1)+1</tex>, где <tex>T_n</tex> — дерево на <tex>n</tex> вершинах.
 
|proof=
 
|proof=
<tex>1)</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>2</tex> (то есть, все оставшиеся рёбра) образуют <tex>(m-1)</tex>-дольный граф, в котором, очевидно, нет клики на <tex>m</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>2</tex> (то есть, все оставшиеся рёбра) образуют <tex>(m-1)</tex>-дольный граф, в котором, очевидно, нет клики на <tex>m</tex> вершинах.
 
+
Теперь воспользуемся вторым [[#def16|определением]] числа Рамсея <tex>r(H_1, H_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>.
<tex>2)</tex> Воспользуемся вторым [[#def16|определением]] числа Рамсея <tex>r(H_1, H_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>.
 
 
}}
 
}}
  
Строка 293: Строка 271:
 
{{Определение
 
{{Определение
 
|id=def10
 
|id=def10
|definition=Пусть <tex>H</tex> — граф. Граф <tex>G</tex> будем называть '''рамсеевским графом''' для <tex>H</tex>, если при любой раскраске рёбер графа <tex>G</tex> в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G</tex> изоморфный <tex>H</tex>.}}
+
|definition=Пусть <tex>H</tex> — граф. Граф <tex>G</tex> будем называть '''рамсеевским графом''' (англ. ''Ramsey’s graph'') для <tex>H</tex>, если при любой раскраске рёбер графа <tex>G</tex> в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G</tex> изоморфный <tex>H</tex>.}}
  
 
{{Определение
 
{{Определение
Строка 323: Строка 301:
 
* [[wikipedia:Ramsey's theorem|Wikipedia — Ramsey's theorem]]
 
* [[wikipedia:Ramsey's theorem|Wikipedia — Ramsey's theorem]]
 
* [[wikipedia:Ramsey theory|Wikipedia — Ramsey theory]]
 
* [[wikipedia:Ramsey theory|Wikipedia — 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://people.maths.ox.ac.uk/~gouldm/ramsey.pdf 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]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика и алгоритмы]]
 
[[Категория:Дискретная математика]]
 
[[Категория:Дискретная математика]]
 
[[Категория:Теория графов]]
 
[[Категория:Теория графов]]
 
[[Категория: Раскраски графов]]
 
[[Категория: Раскраски графов]]

Текущая версия на 09:57, 24 июня 2019

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

Числа Рамсея[править]

Определение:
Клика (англ. clique) в неориентированном графе [math]G(V, E)[/math] — подмножество вершин [math]C \subseteq V[/math], такое что для любых двух различных вершин в [math]C[/math] существует ребро, их соединяющее. Другими словами, клика графа [math]G(V, E)[/math]полный подграф графа [math]G(V, E)[/math].


Определение:
Число Рамсея [math]r(n, m)[/math] (англ. Ramsey's number) — наименьшее из таких чисел [math]x \in \mathbb N[/math], что при любой раскраске ребер полного графа на [math]x[/math] вершинах в два цвета найдется клика на [math]n[/math] вершинах с ребрами цвета [math]1[/math] или клика на [math]m[/math] вершинах с ребрами цвета [math]2[/math].

Существует и другое определение для чисел Рамсея.

Определение:
Число Рамсея [math]r(n, m)[/math] — это наименьшее из всех таких чисел [math]x \in \mathbb N[/math], что для любого графа [math]G[/math] на [math]x[/math] вершинах либо в [math]G[/math] найдется [math]K_n[/math], либо в [math]\overline G[/math] найдется граф [math]K_m[/math].
Раскраска [math]K_5[/math] без одноцветных треугольников

Несложно доказать, что данные определения эквивалентны. Достаточно показать, что раскрашенному в два цвета графу [math]K_n[/math], можно однозначно поставить в соответствие граф [math]G[/math] на [math]n[/math] вершинах. Довольно часто определение для чисел Рамсея дается через задачу "о друзьях и незнакомцах"[1]. Пусть на вечеринке каждые два человека могут быть либо друзьями, либо незнакомцами, в общем виде задачи требуется найти, какое минимальное количество людей нужно взять, чтобы хотя бы [math]n[/math] человек были попарно знакомы, или хотя бы [math]m[/math] человек были попарно незнакомы. Если мы переформулируем данную задачу в терминах графов, то как раз получим определение числа Рамсея [math]r(n, m)[/math], представленное ранее.

Пример[править]

Чтобы получить лучшее представление природы чисел Рамсея, приведем пример. Докажем, что [math]r(3,3) = 6[/math]. Представим, что ребра [math]K_6[/math] раскрашены в два цвета: красный и синий. Возьмем вершину [math]v[/math]. Данной вершине, как и всем другим, инцидентны [math]5[/math] рёбер, тогда, согласно принципу Дирихле, хотя бы три из них одного цвета. Для определенности положим, что хотя бы [math]3[/math] ребра, соединяющие вершину [math]v[/math] с вершинами [math]r[/math], [math]s[/math], [math]t[/math], синие. Если хотя бы одно из ребер [math]rs[/math], [math]rt[/math], [math]st[/math] синее, то в графе есть синий треугольник (полный граф на трёх вершинах), иначе, если они все красные, есть красный треугольник. Таким образом, [math]r(3,3) \leqslant 6 [/math]. Чтобы доказать, что [math]r(3,3) = 6 [/math], предъявим такую раскраску графа [math]K_5[/math], где нет клики на трех вершинах ни синего, ни красного цвета. Такая раскраска представлена на рисунке справа. Понятно, что предъявлять отдельные раскраски для [math] K_4[/math], [math]K_3[/math] не нужно, так как достаточно взять соответствующие подграфы раскрашенного [math]K_5[/math].

Теорема Рамсея. Оценки сверху[править]

Теорема (1, Теорема Рамсея):
Для любых [math]n,m \in \mathbb N[/math] существует число [math]r(n,m)[/math], при этом [math]r(n,m) \leqslant r(n,m-1)+r(n-1,m)[/math], а также если числа [math]r(n,m-1)[/math] и [math]r(n-1,m)[/math] четные, то неравенство принимает вид [math]r(n,m) \leqslant r(n,m-1)+r(n-1,m) - 1[/math] .
Доказательство:
[math]\triangleright[/math]
  1. Докажем с помощью метода математической индукции по [math]n+m[/math].
    База: [math]r(n,\;1) = r(1,\;n) = 1[/math], так как граф, состоящий из одной вершины, можно считать полным графом любого цвета.
    Индукционный переход: Пусть [math]n\gt 1[/math] и [math]m\gt 1[/math]. Рассмотрим полный чёрно-белый граф из [math]r(n-1,\;m)+r(n,\;m-1)[/math] вершин. Возьмём произвольную вершину [math]v[/math] и обозначим через [math]M[/math] и [math]N[/math] множества вершин, инцидентных [math]v[/math] в чёрном и белом подграфе соответственно. Так как в графе [math]r(n-1,\;m)+r(n,\;m-1)=|M|+|N|+1 [/math] вершин, согласно принципу Дирихле, либо [math]|M|\geqslant r(n-1,\;m)[/math], либо [math]|N|\geqslant r(n,\;m-1)[/math]. Пусть [math]|M|\geqslant r(n-1,\;m)[/math]. Тогда либо в [math]M[/math] существует белый [math]K_m[/math], что доказывает теорему, либо в [math]M[/math] есть чёрный [math]K_{n-1}[/math], который вместе с [math]v[/math] образует чёрный [math]K_n[/math], в этом случае теорема также доказана. Случай [math]|N|\geqslant r(n,\;m-1)[/math] рассматривается аналогично.
  2. Предположим, [math]p=r(n-1,\;m)[/math] и [math]q=r(n,\;m-1)[/math] оба чётны. Положим [math]s=p+q-1[/math] и рассмотрим чёрно-белый граф из [math]s[/math] вершин. Если [math]d_i[/math] степень [math]i[/math]-й вершины в чёрном подграфе, то, согласно лемме о рукопожатиях, [math] \sum\limits_{i=1}^s d_i[/math] — чётно. Поскольку [math]s[/math] нечётно, должно существовать чётное [math]d_i[/math]. Не умаляя общности, положим, что [math]d_1[/math] чётно. Обозначим через [math]M[/math] и [math]N[/math] вершины, инцидентные вершине [math]1[/math] в чёрном и белом подграфах соответственно. Тогда [math]|M|=d_1[/math] и [math]|N|=s-1-d_1[/math] оба чётны. Согласно принципу Дирихле, либо [math]|M|\geqslant p-1[/math], либо [math]|N|\geqslant q[/math]. Так как [math]|M|[/math] чётно, а [math]p-1[/math] нечётно, первое неравенство можно усилить, так что либо [math]|M|\geqslant p[/math], либо [math]|N|\geqslant q[/math].
    Далее проводим рассуждения, аналогичные тем, что присутствуют в первом пункте теоремы. Таким образом, [math]r(n,m) \leqslant r(n,m-1)+r(n-1,m) - 1[/math].
[math]\triangleleft[/math]
Утверждение (1):
Для натуральных чисел [math]m,n[/math] выполняется равенство [math]r(n,m) \leqslant C_{n+m-2}^{n-1}[/math]
[math]\triangleright[/math]

Очевидно, [math]C^{n-1}_{n+m-2}=1[/math] при [math]n=1[/math] или [math]m=1[/math], как и соответствующие числа Рамсея. Индукцией по [math]n[/math] и [math]m[/math] при [math]n,m \geqslant 2[/math] получаем

[math]r(n,m) \leqslant r(n,m-1)+r(n-1,m) \leqslant C^{n-1}_{n+m-3}+C^{n-2}_{n+m-3}=C^{n-1}_{n+m-2}[/math]
[math]\triangleleft[/math]

Оценки снизу[править]

Теорема (2, Теорема Эрдеша):
Для любого натурального числа [math]k \geqslant 2[/math] выполняется неравенство [math]r(k,k) \geqslant 2^{k/2}[/math]
Доказательство:
[math]\triangleright[/math]

Так как [math]r(2,2)=2[/math], достаточно рассмотреть случай [math]k \geqslant 3[/math]. Пусть [math]g(n, k)[/math] доля среди помеченных графов на [math]n[/math] вершинах тех, что содержат клику на [math]k[/math] вершинах. Всего графов на наших вершинах, очевидно [math]2^{C^2_n}[/math] (каждое из возможных рёбер [math]C^2_n[/math] можно провести или не провести).

Посчитаем графы с кликой на [math]k[/math] вершинах следующим образом: существует [math]C^k_n[/math] способов выбрать [math]k[/math] вершин для клики в нашем множестве, после чего все рёбра между ними будем считать проведенными, а остальные ребра выбираются произвольно. Таким образом, каждый граф с кликой на [math]k[/math] вершинах будет посчитан, причём некоторые даже более одного раза. Количестве графов с кликой оказывается не более, чем [math]C^k_n\cdot 2^{C^2_n-C^2_k}[/math]. Следовательно,

[math]g(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}}\lt \dfrac{n^k}{k!\cdot 2^{C^2_k}}[/math] [math](*)[/math]

Подставив [math]n\lt 2^{k/2}[/math] в неравенство [math](*)[/math] мы получаем

[math]g(n,k)\lt \dfrac{2^{k^2/2}\cdot 2^{-C^2_k}}{k!}=\dfrac{2^{k/2}}{k!}\lt \dfrac12[/math] при [math]k \geqslant 3[/math]

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

Свойства чисел Рамсея[править]

Следующими свойствами удобно пользоваться при подсчете значений чисел Рамсея [math]r(n,m)[/math] на практике.

  • [math]r(n,m) = r(m,n)[/math]
  • [math]r(1,m) = 1[/math]
  • [math]r(2,m) = m[/math]

Значения чисел Рамсея[править]

Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, их известно довольно мало. Далее приведена таблица Станислава Радзишевского, в которой присутствуют практически все известные числа Рамсея или же промежутки, в которых они находятся.

Числа Рамсея
[math]n,\ m[/math] [math]1 [/math] [math]2 [/math] [math]3 [/math] [math]4 [/math] [math]5 [/math] [math]6 [/math] [math]7 [/math] [math]8 [/math] [math]9 [/math] [math]10[/math]
[math]1 [/math] [math]1 [/math] [math]1 [/math] [math]1 [/math] [math]1 [/math] [math]1 [/math] [math]1 [/math] [math]1 [/math] [math]1 [/math] [math]1 [/math] [math]1 [/math]
[math]2 [/math] [math]1 [/math] [math]2 [/math] [math]3 [/math] [math]4 [/math] [math]5 [/math] [math]6 [/math] [math]7 [/math] [math]8 [/math] [math]9 [/math] [math]10[/math]
[math]3[/math] [math]1[/math] [math]3[/math] [math]6[/math] [math]9[/math] [math]14[/math] [math]18[/math] [math]23[/math] [math]28[/math] [math]36[/math] [math][40, 42][/math]
[math]4[/math] [math]1[/math] [math]4[/math] [math]9[/math] [math]18[/math] [math]25[/math] [math][36, 41][/math] [math][49, 61][/math] [math][59, 84][/math] [math][73, 115][/math] [math][92, 149][/math]
[math]5[/math] [math]1[/math] [math]5[/math] [math]14[/math] [math]25[/math] [math][43, 48][/math] [math][58, 87][/math] [math][80, 143][/math] [math][101, 216][/math] [math][133, 316][/math] [math][149, 442][/math]
[math]6[/math] [math]1[/math] [math]6[/math] [math]18[/math] [math][36, 41][/math] [math][58, 87][/math] [math][102, 165][/math] [math][115, 298][/math] [math][134, 495][/math] [math][183, 780][/math] [math][204, 1171][/math]
[math]7[/math] [math]1[/math] [math]7[/math] [math]23[/math] [math][49, 61][/math] [math][80, 143][/math] [math][115, 298][/math] [math][205, 540][/math] [math][217, 1031][/math] [math][252, 1713][/math] [math][292, 2826][/math]
[math]8[/math] [math]1[/math] [math]8[/math] [math]28[/math] [math][56, 84][/math] [math][101, 216][/math] [math][127, 495][/math] [math][217, 1031][/math] [math][282, 1870][/math] [math][329, 3583][/math] [math][343, 6090][/math]
[math]9[/math] [math]1[/math] [math]9[/math] [math]36[/math] [math][73, 115][/math] [math][133, 316][/math] [math][183, 780][/math] [math][252, 1713][/math] [math][329, 3583][/math] [math][565, 6588][/math] [math][580, 12677][/math]
[math]10[/math] [math]1[/math] [math]10[/math] [math][40, 42][/math] [math][92, 149][/math] [math][149, 442][/math] [math][179, 1171][/math] [math][289, 2826][/math] [math][343, 6090][/math] [math][581, 12677][/math] [math][798, 23556][/math]

Числа Рамсея для раскрасок в несколько цветов[править]

Теперь обобщим числа Рамсея на произвольное количество цветов.

Определение:
Число Рамсея [math]r(n_1,\ldots,n_k)[/math] — это наименьшее из всех таких чисел [math]x \in \mathbb N[/math], что при любой раскраске рёбер полного графа на [math]x[/math] вершинах в [math]k[/math] цветов для некоторого [math]i \in [1 \ldots k][/math] обязательно найдётся клика на [math]n_i[/math] вершинах с рёбрами цвета [math]i[/math]. [math]k,n_1,\ldots,n_k \in \mathbb N[/math]


Теорема (3,Теорема Рамсея для нескольких цветов):
[math]\forall k, n_1, \ldots n_k \in \mathbb N [/math] существует число Рамсея [math]r(n_1,\ldots,n_k)[/math], при этом [math]r(n_1,\ldots,n_k)\leqslant r(n_1,\ldots, n_{k-2}, r(n_{k-1},\;n_k)).[/math]
Доказательство:
[math]\triangleright[/math]
Возьмем граф из [math]r(n_1,\ldots, n_{k-2}, r(n_{k-1}, n_k))[/math] вершин и окрасим его рёбра в [math]k[/math] цветов. Пока что будем считать цвета [math]k-1[/math] и [math]k[/math] одним цветом. Тогда граф будет [math](k-1)[/math]-цветным. Согласно определению числа Рамсея [math]r(n_1,\ldots,n_{k-2},r(n_{k-1},n_k))[/math], такой граф либо содержит [math]K_{n_i}[/math] для некоторого цвета [math]i[/math], такого что [math]1\leqslant i\leqslant k-2[/math], либо [math]K_{r(n_{k-1},n_k)}[/math], окрашенный общим цветом [math]k-1[/math] и [math]k[/math]. В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный [math]r(n_{k-1},n_k)[/math] — вершинный граф содержит либо [math]K_{n_{k-1}}[/math] цвета [math]k-1[/math], либо [math]K_{n_k}[/math] цвета [math]k[/math]. Таким образом любое число Рамсея для раскраски в [math]k[/math] цветов ограничено некоторым числом Рамсея для меньшего количества цветов, следовательно, [math]r(n_1,\ldots,n_k)[/math] существует для любых [math] k, n_1, \ldots n_k, \in \mathbb N [/math], и теорема доказана.
[math]\triangleleft[/math]

Числа Рамсея больших размерностей[править]

Определение:
Пусть [math]m,k,n_1,\ldots ,n_k \in \mathbb N[/math], причём [math]n_1,\ldots ,n_k \geqslant m[/math]. Число Рамсея [math]r_m(n_1,\ldots ,n_k)[/math] — наименьшее из всех таких чисел [math]x \in \mathbb N[/math], что при любой раскраске [math]m[/math]-элементных подмножеств [math]x[/math]-элементного множества [math]M[/math] в [math]k[/math] цветов для некоторого [math]i \in [1\ldots k][/math] обязательно найдётся такое множество [math]W_i[/math], что [math]|W_i|=n_i[/math] и все [math]m[/math]-элементные подмножества множества [math]W_i[/math] имеют цвет [math]i[/math]. Число [math]m[/math] называют размерностью числа Рамсея [math]r_m(n_1,\ldots ,n_k)[/math].

Заметим, что числа Рамсея размерности [math]2[/math] — это определённые ранее числа Рамсея для клик.

Теорема (4, Теорема Рамсея для чисел больших размерностей):
Пусть [math]m,k,n_1,\ldots,n_k[/math] — натуральные числа, причем [math]k \geqslant 2[/math], а [math]n_1,\ldots ,n_k \geqslant m[/math]. Тогда существует число Рамсея [math]r_m(n_1,\ldots n_k)[/math].
Доказательство:
[math]\triangleright[/math]
  1. Мы будем доказывать теорему по индукции. Начнем со случая [math]k=2[/math]. Приступая к доказательству для числа [math]r_m(n_1,n_2)[/math] мы будем считать доказанным утверждение теоремы для чисел Рамсея всех меньших размерностей и чисел Рамсея размерности [math]m[/math] с меньшей суммой [math]n_1+n_2[/math]. В качестве базы будем использовать случай чисел Рамсея размерности [math]2[/math] разобранный выше. Итак, мы докажем, что [math]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))[/math].
    Для каждого множества [math]M[/math] через [math]M^k[/math] обозначим множество всех [math]k[/math]-элементных подмножеств [math]M[/math].
    Рассмотрим [math](p+1)[/math]-элементное множество [math]M[/math] и выделим в нём элемент [math]a[/math]. Пусть [math]M_0=M \setminus \{ a \}[/math]. Пусть [math]\rho:M^m\rightarrow \{1, 2 \} [/math] — произвольная раскраска в два цвета. Рассмотрим раскраску [math]\rho': M_0^{m-1} \rightarrow \{1, 2\} [/math] , определённую следующим образом: для каждого множества [math]B \in M_0^{m-1}[/math] пусть [math]\rho'(B) = \rho(B \cup \{ a \})[/math].
    Так как [math]|M_0|=p[/math], либо существует [math]r_m(n_1 — 1,n_2)[/math]-элементное подмножество [math]M_i \subset M_0[/math], [math]\rho'(B)=1[/math] на всех [math]B \in M_1^{m-1}[/math], либо существует [math]r_m(n_1,n_2-1)[/math]-элементное подмножество [math]M_2 \subset M_0[/math], [math]\rho'(B)=2[/math] на всех [math]B \in M_2^{m-1}[/math]. Случаи аналогичны, рассмотрим первый случай и множество [math]M_1[/math].
    По индукционному предположен из [math]|M_1|=r_m(n_1-1,n_2)[/math] следует, что либо существует [math]n_1-1[/math]-элементное подмножество [math]N_1 \subset M_1[/math], [math]\rho(A)=1[/math] на всех [math]A \in N^m_1[/math], либо существует [math]n_2[/math]-элементное подмножество [math]N_2 \subset M_1[/math], [math]\rho(A)=2[/math] на всех [math]A \in N_2^m[/math]. Во втором случае искомое подмножество найдено (это [math]N_2[/math]), рассмотрим первый случай и множество [math]N=N_1 \cup \{a\}[/math]. Пусть [math]A \in N^m[/math]. Если [math]A \not\ni a[/math], то [math]A \in N_1^m[/math] и следовательно [math]\rho(A)=1[/math]. Если же [math]A \ni a[/math], то множество [math]A \setminus \{a\} \in N_1^{m-1} \subset M_1^{m-1}[/math] и поэтому [math]\rho(A)=\rho'(A \setminus \{a \})=1[/math]. Учитывая, что [math]|N|=n_1[/math], мы нашли искомое подмножество и в этом случае.
  2. При [math]k\gt 2[/math] будем вести индукцию по [math]k[/math] с доказанной выше базой [math]k=2[/math]. При [math]k\gt 2[/math] мы докажем неравенство [math]r_m(n_1,\ldots ,n_k) \leqslant q=r_m(r_m(n_1,\ldots ,n_{k-1}),n_k)[/math].
    Для этого мы рассмотрим множество [math]M[/math] на [math]q[/math] вершинах и произвольную раскраску [math]\rho:M^m \rightarrow [1 \ldots k][/math] в [math]k[/math]цветов. Рассмотрим раскраску [math]\rho':M^m \rightarrow \{0,k\}[/math], в которой цвета [math]1,\ldots,k-1[/math] раскраски [math]\rho[/math] склеены в цвет [math]0[/math]. Тогда существует либо такое подмножество [math]M_0 \subset M[/math], что [math]|M_0|=r_m(n_1,\ldots ,n_{k-1})[/math] и [math]\rho'(A)=0[/math] на всех [math]A \in M_0^m[/math], либо существует такое [math]n_k[/math]-элементное подмножество [math]M_k \subset M[/math], что [math]\rho(A)=\rho'(A)=k[/math] на всех [math]A \in M^m_k[/math]. Во втором случае [math]M_k[/math] — искомое подмножество, а в первом случае заметим, что на любом подмножестве [math]A \in M_0^m[/math] из [math]\rho'(A)=0[/math] следует [math]\rho(A) \in [1 \ldots k-1][/math]. Исходя из размера множества [math]M_0[/math] по индукционному предположению получаем, что найдется искомое подмножество множества [math]M[/math] для одного из цветов [math]1,\ldots ,k-1[/math], таким образом неравенство доказано, а из этого следует и существование числа Рамсея [math]r_m(n_1,\ldots ,n_k)[/math].
[math]\triangleleft[/math]

Числа Рамсея для произвольных графов[править]

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

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

Существует и другое определение чисел Рамсея для произвольных графов.

Определение:
Пусть [math]H_1,H_2[/math] — графы. Число Рамсея [math]r(H_1,H_2)[/math] — это наименьшее из всех таких чисел [math]x \in \mathbb N[/math], что для любого графа [math]G[/math] на [math]x[/math] вершинах либо в [math]G[/math] найдется подграф изоморфный [math]H_1[/math], либо в [math]\overline G[/math] найдется подграф изоморфный [math]H_2[/math].

Несложно показать, что эти определения эквивалентны (аналогично определениям для классических чисел Рамсея). Из результатов классической теории Рамсея становится понятно, что числа [math]r(H_1,H_2)[/math] существуют.

Лемма (1):
Пусть [math]m\gt 1[/math], а граф [math]H[/math] таков, что [math]v(H) \geqslant (m-1)(n-1)+1[/math] и [math]\alpha(H) \leqslant m-1[/math], где [math]v(H)[/math] — количество вершин в графе [math]H[/math]. Тогда граф [math]H[/math] содержит в качестве подграфа любое дерево на [math]n[/math] вершинах.
Доказательство:
[math]\triangleright[/math]

Зафиксируем [math]m[/math] и проведем индукцию по [math]n[/math].

База: для [math]n=1[/math] очевидно.

Индукционный переход: Пусть верно для [math]n-1[/math], докажем для [math]n[/math]. Рассмотрим произвольное дерево [math]T_n[/math] на [math]n[/math] вершинах, пусть дерево [math]T_{n-1}[/math] получено из [math]T_n[/math] удалением висячей вершины. Пусть [math]U[/math] — максимальное независимое множество вершин графа [math]H[/math]. Тогда [math]|U|=\alpha(H) \leqslant m-1[/math], следовательно [math]v(H-U) \geqslant (m-1)(n-2)+1[/math] и очевидно [math]\alpha(H-U) \leqslant m-1[/math].

По индукционному предположению, граф [math]H-U[/math] содержит в качестве подграфа дерево [math]T_{n-1}[/math]. Пусть [math]a[/math] — вершина этого дерева, присоединив к которой висячую вершину, мы получим дерево [math]T_n[/math]. Заметим, что множество [math]U \cup[/math] [math]\{a\}[/math] не является независимым ввиду максимальности [math]U[/math]. Следовательно, вершина [math]a[/math] смежна хотя бы с одной вершиной [math]x \in U[/math]. Отметим, что [math]x[/math] не принадлежит множеству вершин графа [math]T_{n-1}[/math] и, присоединив вершину [math]x[/math] к вершине [math]a[/math] дерева [math]T_{n-1}[/math], получим дерево [math]T_n[/math] в качестве подграфа графа [math]H[/math].
[math]\triangleleft[/math]
Теорема (5, Теорема Хватала):
[math]r(T_n,K_m)=(m-1)(n-1)+1[/math], где [math]T_n[/math] — дерево на [math]n[/math] вершинах.
Доказательство:
[math]\triangleright[/math]

Сперва докажем, что [math]r(T_n,K_m) \geqslant (m-1)(n-1)+1[/math]. Для этого предъявим раскраску рёбер графа [math]K_{(m-1)(n-1)}[/math], в которой нет ни одного связного подграфа на [math]n[/math] вершинах с рёбрами цвета [math]1[/math] и нет клики на [math]m[/math] вершинах с рёбрами цвета [math]2[/math]. Разобьём вершины графа на [math]m-1[/math] клику по [math]n-1[/math] вершине и покрасим все рёбра этих клик в цвет [math]1[/math]. Тогда любой связный подграф с рёбрами цвета [math]1[/math] содержит не более [math]n-1[/math] вершины, в частности, нет подграфа с рёбрами цвета [math]1[/math], изоморфного [math]T_n[/math]. Рёбра цвета [math]2[/math] (то есть, все оставшиеся рёбра) образуют [math](m-1)[/math]-дольный граф, в котором, очевидно, нет клики на [math]m[/math] вершинах.

Теперь воспользуемся вторым определением числа Рамсея [math]r(H_1, H_2)[/math]. Рассмотрим произвольный граф [math]G[/math] на [math]{(m-1)(n-1)+1}[/math] вершинах. Предположим, что в графе [math]G[/math] не существует клики на [math]m[/math] вершинах. Тогда [math]m\gt 1[/math] и [math]\alpha( \overline G) \leqslant m-1[/math]. По лемме [math]1[/math], граф [math] \overline G[/math] содержит в качестве подграфа любое дерево на [math]n[/math] вершинах, в частности, дерево, изоморфное [math]T_n[/math].
[math]\triangleleft[/math]

Индуцированная теорема Рамсея[править]

Определение:
Граф [math]H[/math] называется индуцированным подграфом (англ. induced subgraph) графа [math]G[/math] если две вершины в [math]H[/math] соединены ребром тогда и только тогда, когда они смежны в [math]G[/math].


Определение:
Пусть [math]H[/math] — граф. Граф [math]G[/math] будем называть рамсеевским графом (англ. Ramsey’s graph) для [math]H[/math], если при любой раскраске рёбер графа [math]G[/math] в два цвета существует одноцветный по рёбрам индуцированный подграф графа [math]G[/math] изоморфный [math]H[/math].


Определение:
Индуцированным числом Рамсея (англ. induced Ramsey’s number) [math]r_{ind}(H)[/math] для графа [math]H[/math] будем называть минимальное число [math]x \in \mathbb N[/math], такое что существует рамсеевский граф на [math]x[/math] вершинах для графа [math]H[/math].

Заметим, что при замене произвольного графа [math]H[/math] на клику мы получаем частный случай классической теоремы Рамсея.


Теорема (6, Индуцированная теорема Рамсея):
Для любого графа [math]H[/math] существует рамсеевский граф [math]G[/math].

Доказательство [2] данной теоремы было приведено независимо различными математиками, однако благодаря ему получилось предоставить только очень грубые оценки значений индуцированных чисел Рамсея. В данный момент проблема нахождения сколько-нибудь точных границ индуцированных чисел Рамсея является нерешенной задачей математики.

Особенности теории[править]

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

См. также[править]

Примечания[править]

Источники информации[править]