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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Числа Рамсея)
(Числа Рамсея)
Строка 14: Строка 14:
 
[[Файл:RamseyTheoryK5.png|200px|thumb|upright|Раскраска <tex>K_5</tex> без одноцветных треугольников]]
 
[[Файл:RamseyTheoryK5.png|200px|thumb|upright|Раскраска <tex>K_5</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>, представленное ранее.
 
Несложно доказать, что данные определения эквивалентны. К тому же, довольно часто определение для чисел Рамсея дается через задачу "о друзьях и незнакомцах"<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_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>r(3,3) = 6 </tex>, предъявим такую раскраску графа  <tex>K_5</tex>, где нет клики на трех вершинах ни синего, ни красного цвета. Такая раскраска представлена на рисунке справа.
 +
  
 
===Теорема Рамсея. Оценки сверху===
 
===Теорема Рамсея. Оценки сверху===

Версия 21:51, 6 декабря 2018

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

Числа Рамсея

Определение:
Клика (англ. 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] без одноцветных треугольников

Несложно доказать, что данные определения эквивалентны. К тому же, довольно часто определение для чисел Рамсея дается через задачу "о друзьях и незнакомцах"[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], где нет клики на трех вершинах ни синего, ни красного цвета. Такая раскраска представлена на рисунке справа.


Теорема Рамсея. Оценки сверху

Теорема (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]

[math]1)[/math] Докажем с помощью метода математической индукции по [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] рассматривается аналогично.

[math]2)[/math] Предположим, [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_{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_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]

Значения чисел Рамсея

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

Числа Рамсея
[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(k, 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] — это определённые ранее числа Рамсея для клик.


Определение:
Для каждого множества [math]M[/math] через [math]M^k[/math] мы будем обозначать множество всех [math]k[/math]-элементных подмножеств [math]M[/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]

[math]1)[/math] Мы будем доказывать теорему по индукции. Начнем со случая [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](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]