Теория Рамсея
Содержание
Числа Рамсея
Основным объектов изучения будут полные графы, ребра которых покрашены в несколько цветов. В дальнейшем, для простоты, полный граф на вершинах будем называть кликой.
| Определение: |
| Пусть . Число Рамсея — это наименьшее из таких чисел , что при любой раскраске ребер полного графа на вершинах в два цвета найдется клика на вершинах с ребром цвета 1 или клика на вершинах с ребром цвета 2. |
Существование. Оценки сверху
| Теорема (1): |
Пусть -натуральные числа. Тогда . Если оба числа и — четные, то неравенство строгое. |
| Доказательство: |
|
1) Рассмотрим клику на вершинах с рёбрами цветов 1 и 2 и ее произвольную вершину . Тогда либо от вершины отходит хотя бы рёбер цвета 2, либо от вершины отходит хотя бы рёбер цвета 1. Случаи аналогичны, рассмотрим первый случай и клику на вершинах, соединенных с рёбрами цвета 2. На этих вершинах есть либо клика на вершинах с ребрами цвета 1, либо клика на вершинах с рёбрами цвета 2. Во втором случае добавим вершину и получим клику на вершинах с рёбрами цвета 2. Теперь из определения следует неравенство из теоремы 1. 2) Рассмотрим клику на вершинах с рёбрами цветов 1 и 2 и его произвольную вершину . Если вершине инцидентны хотя бы рёбер цвета 2 или хотя бы рёбер цвета 1, то мы найдём в графе клику на вершинах с рёбрами цвета 1 или клику на вершинах с рёбрами цвета 2. Остаётся лишь случай, когда вершине инцидентны ровно рёбер цвета 2, то же самое для всех остальных вершин. Это означает, что в графе из рёбер цвета 2 всего вершин и степень каждой вершины равна . Однако, тогда в графе нечётное количество вершин нечётной степени. Противоречие показывает нам, что в случае, когда и — чётные, выполняется неравенство . |
| Утверждение (1): |
Для натуральных чисел выполняется равенство |
|
Очевидно, при или , как и соответствующие числа Рамсея. Индукцией по и при получаем |
С помощью неравенства из теоремы 1 можно получить несколько точных значений чисел Рамсея. Отметим что . Так как числа и четны, можно вывести неравенства . И, наконец, , а также
Экстремальные примеры и оценки снизу
Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, этих значении известно немногим больше, чем перечислено выше.
| Определение: |
| Графом Рамсея назовем такой граф на вершинах, не содержащий ни клики на вершинах ни независимого множества на вершинах(то есть, граф на ребрах цвета 1 из раскраски в два цвета ребер графа , не содержащей ни клики на вершинах с рёбрами цвета 1 ни клики на вершинах с рёбрами цвета 2). |
Граф — это цикл на пяти вершинах. Экстремальный граф — это цикл на 8 вершинах с проведёнными четырьмя главными диагоналями. Графы и имеют интересную числовую природу.
Так, если ассоциировать 13 вершин графа с элементами поля вычетов по модулю 13, то рёбра будут соединять вычеты разность которых — кубический вычет по модулю 13 (то есть, 1, 5, 8 или 12).
Если считать 17 вершин графа элементами поля вычетов по модулю 17, то рёбра будут соединять вычеты, разность которых — квадратичный вычет по модулю 17 (то есть, 1, 2, 4, 8, 9, 13, 15 или 16).
Существует гипотеза что любой граф изоморфен своему дополнению(или что в раскраске полного графа на вершинах в два цвета граф с рёбрами цвета 1 обязательно изоморфен графу с рёбрами цвета 2). Однако, это не белее чем красивое предположение, в обоснование которого можно положите лишь немногие известные примеры.
| Теорема (2): |
Для любого натурального числа выполняется неравенство |
| Доказательство: |
|
Так как , достаточно рассмотреть случай . Зафиксируем множество различных помеченных вершин . Пусть — деля среди всех графов на вершинах тех графов, что содержат клику на вершинах. Всего графов на наших вершинах, очевидно (каждое из возможных можно провести или не провести). Посчитаем графы с кликой на вершинах так: существует способов выбрать вершин для клики в нашем множестве, после чего все рёбра между ними будем считать проведенными, а остальные ребра выбираются произвольным образом. Таким образом, каждый граф с кликой на вершинах будет посчитан причём некоторые даже более одного раза. Количестве графов с кликой оказывается не более, чем . Следовательно, * Подставив в неравенство * мы получаем при Предположим, что и разобьём все графы на n вершинах на пары (граф и его дополнение) Так как , то существует пара, в которой ни , ни не содержат клики на вершинах. Рассмотрим раскраску рёбер в два цвета, в которой ребра цвета 1 образуют граф . В такой раскраске нет клики на вершинах ни цвета 1, ни цвета 2, противоречие. Следовательно . |
| Утверждение (2): |
Для любых таких, что , выполняется неравенство |
Числа Рамсея для раскрасок в несколько цветов
| Определение: |
| Пусть . Число Рамсея — это наименьшее из всех таких чисел , что при любой раскраске рёбер полного графа на вершинах в цветов для некоторого обязательно найдётся клика на вершинах с рёбрами цвета . |
| Утверждение (3): |
Отметим, что — это определённое ранее число Рамсея |
Обобщение оказывается настолько естественным что по сути не добавляет нам ничего нового: полностью аналогично теореме 1 и утверждению 1 можно доказать следующие факты.
| Теорема (3): |
Пусть — натуральные числа. Тогда выполняются следующие утверждения:
|
| Доказательство: |
|
1) Доказательстве полностью аналогично пункту 1 доказательства теоремы 1 2) Доказательство аналогично утверждению 1. Нужно лишь убедиться в очевидном неравенстве для случая, когда хотя бы одно из чисел равно 1 (левая часть в этом случае равна 1, а правая, очевидно не меньше 1) и заметить, что полиномиальные коэффициенты из очевидных комбинаторных соображений удовлетворяют соотношению: Следовательно, 2 неравенство из данной теоремы выводится из неравенства 1 по индукции. |
Числа Рамсея больших размерностей
| Определение: |
| Пусть , причём . Число Рамсея — наименьшее из всех таких чисел , что при любой раскраске -элементных подмножеств -элементного множества в цветов для некоторого обязательно найдётся такое множество , что и все -элементные подмножества множества имеют цвет . |
| Определение: |
| Число называется размерностью числа Рамсея . |
| Утверждение (4): |
1) Нетрудно понять что числа Рамсея размерности 2 — это определённые выше числа Рамсея для клик 2) При количестве цветов, равном 2, этот параметр мы будем опускать и писать вместо . |
| Определение: |
| Для каждою множества через мы будем обозначать множество всех -элементных подмножеств . |
| Теорема (4): |
Пусть — натуральные числа, причем , а . Тогда число Рамсея существует(то есть, конечно) |
| Доказательство: |
|
1)Мы будем доказывать теорему по индукции. Начнем со случая . Приступая к доказательству для числа мы будем считать доказанным утверждение теоремы для чисел Рамсея всех меньших размерностей и чисел Рамсея размерности с меньшей суммой . В качестве базы будем использовать случай чисел Рамсея размерности 2 разобранный выше. Итак, мы докажем, что
Рассмотрим -элементное множество и выделим в нём элемент . Пусть \{}. Пусть {1,2} — произвольная раскраска в два цвета. Рассмотрим раскраску {1,2}, определённую следующим образом: для каждого множества пусть {a}. Так как , либо существует -элементное подмножество , для которого на всех , либо существует -элементное подмножество , для которого на всех . Случаи аналогичны, рассмотрим первый случай и множество . По индукционному предположен из следует, что либо существует -элементное подмножество , для которого на всех , либо существует -элементное подмножество , для которого на всех . Во втором случае искомое подмножество найдено (это ), рассмотрим первый случай и множество {}. Пусть . Если , то и следовательно . Если же , то множество \{} и поэтому \{}. Учитывая, что , мы нашли искомое подмножество и в этом случае. 2)При будем вести индукцию по с доказанной выше базой . При мы докажем неравенство Для этого мы рассмотрим множество на вершинах и произвольную раскраску в цветов. Рассмотрим раскраску {}, в которой цвета раскраски склеены в цвет 0. Тогда существует либо таксе подмножество , что и на всех , либо существует такое -элементное подмножество , что на всех . Во втором случае — искомое подмножество, а в первом случае заметим, что на любом подмножестве из следует . Исходя из размера множества по индукционному предположению получаем, что найдется искомое подмножество множества для одного из цветов |
Числа Рамсея для произвольных графов
Еще один способ обобщения классической теории Рамсея — замена клик на произвольные графы-шаблоны.
| Определение: |
| Пусть — два данных графа. Число Рамсея — это наименьшее из всех таких чисел , что при любой раскраске рёбер полного графа на вершинах в два цвета обязательно найдется подграф, изоморфный с рёбрами цвета 1 или подграф изоморфный с рёбрами цвета 2 |
В принципе из результатов классической теории Рамсея понятие, что числа обязательно существуют (то есть, конечны).
| Лемма (1): |
Пусть , а граф таков, что и . Тогда граф содержит в качестве подграфа любое дерево на вершинах. |
| Доказательство: |
|
Зафиксируем и проведем индукцию по . База для очевидна. Докажем индукционный переход . Рассмотрим произвольное дерево на вершинах, пусть дерево получено из удалением висячей вершины. Пусть — максимальное независимое множестве вершин графа Тогда , следовательно и очевидно . По индукционному предположению, граф содержит в качестве подграфа дерево . Пусть — вершина этого дерева, присоединив к ксторой висячую вершину мы получим дерево . Заметим, что множество {} не является независимым ввиду максимальности . Следовательно, вершина смежна хотя с одной вершиной . Отметим, что и, присоединив вершину к вершине дерева , получим дерево в качестве подграфа графа . |
| Теорема (5): |
Пусть — дерево на вершинах. Тогда . |
| Доказательство: |
|
1) Докажем, что . Для этого предъявим раскраску рёбер графа K_{(m-1)(n-1)}, в которой нет ни одного связного подграфа на вершинах с рёбрами цвета 1 и нет клики на вершинах с рёбрами цвета 2. Разобьём вершины графа на клику по вершине и покрасим все рёбра этих клик в цвет 1. Тогда любой связный подграф с рёбрами цвета 1 содержит не более вершины, в частности, нет подграфа с рёбрами цвета 1, изоморфного . Рёбра цвета 2 (то есть, все оставшиеся рёбра) образуют -дольный граф, в котором, очевидно, нет клики на вершинах. 2) Рассмотрим произвольную раскраску рёбер полного графа в два цвета. Предположим, что не существует клики на вершинах с рёбрами цвета 2. Тогда и . По лемме 1, граф содержит в качестве подграфа любое дерево на вершинах в частности, дерево, изоморфное . |
Индуцированная теорема Рамсея
Докажем похожее на теорему Рамсея, но значительно более сложнее утверждение.
| Определение: |
| Пусть — граф. Граф называется рамсеееским графом для , если при любой раскраске рёбер графа в два цвета существует одноцветный по рёбрам индуцированный подграф графа изоморфный |
При замене произвольного графа на клику мы получаем частный случай классической теоремы Рамсея. Для клики добавленное слово "индуцированный" ничего не меняет. Но значительно усложняет ситуацию для произвольного графа .
| Теорема (6, Индуцированная теорема Рамсея): |
Для любого графа существует рамсеевский граф |
Случай двудольного графа
Здесь мы будем рассматривать двудольный граф , как
,
где и — разбиение множества вершин на две доли, а рёбра соединяют вершины из разных долей.
| Определение: |
| Пусть — двудольные графы. Инъективное отображение назовём погружением, если оно удовлетворяет двум условиям. 1) |
| Утверждение (5): |
Отметим, что если существует погружение двудольного графа в двудольный граф то индуцированный подграф графа изоморфен |
Напомним, что для множества через мы обозначаем множество всех -элементных подмножеств множества .
| Определение: |
| Назовем особым двудольный граф вида , где {} |
| Лемма (2): |
Любой двудольный граф может быть погружен в особый двудольный граф. |
| Доказательство: |
|
Рассмотрим произвольный двудольный граф , пусть . Положим Построим погружение в особый двудольный граф . Изначально положим . Попробуем построить такое множество , что . По определению погружения и множества , должно выполняться условие: |
| Лемма (3): | ||
Для любого двудольного графа существует такой двудольный граф , что для любой раскраски рёбер в два цвета обязательно существует погружение графа в граф в котором все рёбра одноцветны. | ||
| Доказательство: | ||
Ввиду леммы 2 достаточно доказать утверждение для особого двудольного графа . Пусть . Докажем что рамсеевским графом для будет особый двудольный граф , где Можно считать, что элементы упорядочены. Тогда элементы каждого множества будут упорядочены. Обозначим через множество номеров элементов множества в порядке элементов множества . Тогда может принимать ровно значений. Покрасим множество (то есть все -элементные подмножества ) в цветов: цветом подмножества будет пара . Из выбора размера множества (см. условие **) следует, что ceotcndetn такое подмножество , что и все подмножества имеют одинаковый цвет (не умаляя общности будем считать, что . Мы найдём погружение графа в , все рёбра в котором покрашены в исходной раскраске в цвет 1 и тем самым докажем лемму. Занумеруем элементы множества в порядке их следования в : пусть . Введем обозначения . Положим . Остаётся корректно определить для каждого множества . Прежде чем построить мы положим . Из определения погружения понятно, что тогда должно выполняться условие , а следовательно, нам нужно дополнить множество еще элементами, не входящими в множество . Мы сделаем это так, чтобы множество порядков номеров элементов множества среди элементов множества было : так как , не входящих в элементов хватит, чтобы обеспечить это. Так как по выбору множества мы имеем , множество выбрано корректно и, опять же в силу выбора , все рёбра особого двудольного графа между вершинами из и покрашены в цвет 1. В завершение остается лишь добавить, что при мы по построению имеем , поэтому . Таким образом искомое погружение построено. | ||
Случай произвольного графа
| Теорема (7): | |||||
Для произвольного графа существует рамсеевский граф. | |||||
| Доказательство: | |||||
|
Пусть . Пронумеруем вершины графа . Построим граф следующим образом: разместим его вершины в виде таблице . Таким образом в каждом столбце вершины окажутся пронумерованы числами от 1 до , как соответствующие строки таблицы. В каждом столбце одним из способов разместим граф (каждый столбец соответствует одному из возможных способов размещения). Все рёбра графа будут рёбрами указанных копий графа . Граф является -дольным, его естественное разбиение на доли задаётся таблицей: — это вершины, соответствующие ряду таблицы. Мы последовательно в несколько шагов будем перестраивать наш граф с помощью леммы 3, так, чтобы вершины последующих графов также разбивались на долей и записывались в виде таблицы. Каждый шаг будет соответствовать одной паре строк таблицы. Шаг перестройки графа. Итак, пусть мы имеем -дольный граф , доли которого (где ). Пусть с парой строк (и, соответственно, долей) мы еще не выполняли шаг. Очевидно, граф двудолен и для него по лемме 3 существует двудольный рамсеевский граф . Более того если вершины разбиты на две доли и , то для любой раскраски рёбер в два цвета существует одноцветное погружение графа в в котором и . Назовём таксе погружение одноцветным. Перейдём к построению . Заменим на и на , проведем между этими долями все рёбра графа . Наша цель в том, чтобы для любого погружения в была содержащая его копия (причем доли этой копии лежали в соответствующих строках таблицы графа Занумеруем всевозможные погружения в : пусть это . Каждому погружению мы поставим в соответствие отдельные копии всех отличных от и долей: . Положим и . На этих долях построим копию графа . В результате для каждого погружения графа в мы построили свою копию графа . Выделение одноцветного индуцированного подграфа. Итак, докажем, что и есть рамсеевский граф для . Пусть — именно такая нумерация пар строк в нашей таблице, в порядке которой совершались шаги перестройки графа. Рассмотрим произвольную раскраску рёбер графа в два цвета и докажем следующий факт.
| |||||
