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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Особенности теории)
(Индуцированная теорема Рамсея)
Строка 283: Строка 283:
 
{{Определение
 
{{Определение
 
|id=def9
 
|id=def9
|definition=Граф <tex>H</tex> называется '''индуцированным подграфом''' (англ. ''induced subraph'') графа <tex>G</tex> если две вершины в <tex>H</tex> соединены ребром тогда и только тогда, когда они смежны в <tex>G</tex>. }}
+
|definition=Граф <tex>H</tex> называется '''индуцированным подграфом''' (англ. ''induced subgraph'') графа <tex>G</tex> если две вершины в <tex>H</tex> соединены ребром тогда и только тогда, когда они смежны в <tex>G</tex>. }}
  
 
{{Определение
 
{{Определение
 
|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> будем называть '''рамсеевским графом''' для <tex>H</tex>, если при любой раскраске рёбер графа <tex>G</tex> в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G</tex> изоморфный <tex>H</tex>.}}
  
 
{{Определение
 
{{Определение
Строка 302: Строка 302:
  
 
Доказательство данной теоремы было приведено независимо различными математиками, однако благодаря нему получилось предоставить только очень грубые оценки значений индуцированных чисел Рамсея. В данный момент проблема нахождения сколько-нибудь точных границ индуцированных чисел Рамсея является нерешенной задачей математики.
 
Доказательство данной теоремы было приведено независимо различными математиками, однако благодаря нему получилось предоставить только очень грубые оценки значений индуцированных чисел Рамсея. В данный момент проблема нахождения сколько-нибудь точных границ индуцированных чисел Рамсея является нерешенной задачей математики.
 +
 
==Особенности теории==
 
==Особенности теории==
 
Результаты, полученные в теории Рамсея, обладают двумя главными характеристиками. Во-первых, они не позволяют получить сами структуры: теоремы лишь доказывают, что они существуют, но алгоритма для их нахождения не предлагают. Единственным способ найти нужную конструкцию зачастую является перебор. Во-вторых, чтобы искомые структуры существовали, обычно требуется, чтобы объекты, их содержащие, состояли из очень большого числа элементов. Зависимость числа элементов объекта от размера конструкции обычно, как минимум, экспоненциальная.
 
Результаты, полученные в теории Рамсея, обладают двумя главными характеристиками. Во-первых, они не позволяют получить сами структуры: теоремы лишь доказывают, что они существуют, но алгоритма для их нахождения не предлагают. Единственным способ найти нужную конструкцию зачастую является перебор. Во-вторых, чтобы искомые структуры существовали, обычно требуется, чтобы объекты, их содержащие, состояли из очень большого числа элементов. Зависимость числа элементов объекта от размера конструкции обычно, как минимум, экспоненциальная.

Версия 19:12, 30 ноября 2018

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

Числа Рамсея

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


Определение:
Число Рамсея [math]r(m, n)[/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]K_5[/math] без одноцветных треугольников

Часто определение для чисел Рамсея дается через задачу "о друзьях и незнакомцах"[1]. Пусть на вечеринке каждые два человека могут быть либо друзьями, либо незнакомцами, в общем виде задачи требуется найти, какое минимальное количество людей нужно взять, чтобы хотя бы [math]m[/math] человек были попарно знакомы, или хотя бы [math]n[/math] человек были попарно незнакомы. Если мы переформулируем данную задачу в терминах графов, то как раз получим определение числа Рамсея [math]r(m, n)[/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) \le 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) \le 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) \le 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]|M|\geqslant p=r(n-1,\;m)[/math]. Тогда либо подграф, порождённый множеством [math]M[/math], содержит белый [math]K_m[/math] и доказательство завершено, либо он содержит чёрный [math]K_{n-1}[/math], который вместе с вершиной [math]1[/math] образует чёрный [math]K_n[/math]. Случай [math]|N|\geqslant q=r(n,\;m-1)[/math] рассматривается аналогично.
[math]\triangleleft[/math]
Утверждение (1):
Для натуральных чисел [math]m,n[/math] выполняется равенство [math]r(n,m) \le 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 \ge 2[/math] получаем

[math]r(n,m) \le r(n,m-1)+r(n-1,m) \le 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 \ge 2[/math] выполняется неравенство [math]r(k,k) \ge k^{k/2}[/math]
Доказательство:
[math]\triangleright[/math]

Так как [math]r(2,2)=2[/math], достаточно рассмотреть случай [math]k \ge 3[/math]. Зафиксируем множество различных помеченных вершин [math]v_i,\ldots,v_n[/math]. Пусть [math]g(n,k)[/math] — доля среди всех графов на вершинах [math]v_i,\ldots,v_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) \le \dfrac{C^k_n}{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 \ge 3[/math]

Предположим, что [math]r(k,k)=n\lt 2^{k/2}[/math] и разобьём все графы на [math]n[/math] вершинах на пары [math]G, \overline G[/math] (граф и его дополнение) Так как [math]g(n,k)\lt \dfrac12[/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]1[/math], получили противоречи противоречие. Значит [math]n[/math] было выбрано неверно. Из этого следует [math]r(k,k) \ge 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 \ge m[/math]. Число Рамсея [math]r_m(k; 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(k;n_1,\ldots ,n_k)[/math].


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

При количестве цветов, равном [math]2[/math], этот параметр в записи обычно опускают и пишут [math]r_m(n_1,n_2)[/math] вместо [math]r_m(2;n_1,n_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 \ge 2[/math], а [math]n_1,\ldots ,n_k \ge m[/math]. Тогда число Рамсея [math]r_m(k;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]. В качестве базы будем использовать случай чисел Рамсея размерности 2 разобранный выше. Итак, мы докажем, что

[math]r_m(n_1,n_2)-1 \le 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[/math]\{[math]a[/math]}. Пусть [math]\rho:M^m\rightarrow[/math] {1,2} — произвольная раскраска в два цвета. Рассмотрим раскраску [math]\rho': M_0^{m-1}\rightarrow[/math] {1,2}, определённую следующим образом: для каждого множества [math]B \in M_0^{m-1}[/math] пусть [math]\rho'(В) = \rho(B U[/math]{a}[math])[/math]. Так как [math]|M_0|=p[/math], либо существует [math]r_m(n_1 — 1,n_2)[/math]-элементное подмножество [math]M_i \subset M_0[/math], для которого [math]\rho'(В)=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 [/math]{[math]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[/math]\{[math]a[/math]}[math]\in N_1^{m-1} \subset M_1^{m-1}[/math] и поэтому [math]\rho(A)=\rho'(A[/math]\{[math]a[/math]}[math])=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(k;n_1,\ldots ,n_k) \le q=r_m(r_m(k-1;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 [/math]{[math]0,k[/math]}, в которой цвета [math]1,\ldots,k-1[/math] раскраски [math]\rho[/math] склеены в цвет 0. Тогда существует либо таксе подмножество [math]M_0 \subset M[/math], что [math]|M_0|=r_m(k-1;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]\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]r(H_1,H_2)[/math] существуют.

Лемма (1):
Пусть [math]m\gt 1[/math], а граф [math]H[/math] таков, что [math]v(H) \ge (m-1)(n-1)+1[/math] и [math]\alpha(H) \le m-1[/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) \le m-1[/math], следовательно [math]v(H-U) \ge (m-1)(n-2)+1[/math] и очевидно [math]\alpha(H-U) \le 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 \not\in V(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]1)[/math] Докажем, что [math]r(T_n,K_m) \ge (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]2)[/math] Рассмотрим произвольную раскраску рёбер полного графа [math]K_{(m-1)(n-1)+1}[/math] в два цвета. Предположим, что не существует клики на [math]m[/math] вершинах с рёбрами цвета [math]2[/math]. Тогда [math]m\gt 1[/math] и [math]\alpha(G_1) \le m-1[/math]. По лемме [math]1[/math], граф [math]G_1[/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] будем называть рамсеевским графом для [math]H[/math], если при любой раскраске рёбер графа [math]G[/math] в два цвета существует одноцветный по рёбрам индуцированный подграф графа [math]G[/math] изоморфный [math]H[/math].


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

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


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

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

Особенности теории

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

См. также

Примечания

Источники информации