299
правок
Изменения
→Числа Рамсея для произвольных графов
==Числа Рамсея для произвольных графов==
Еще один способ обобщения классической теории Рамсея — замена клик на произЕСлвные графы-шаблоны,
Определение 1С.5. Пусть Нх,Н2 — два данных графа. Висло Рамсея г(Нх,Н2) — зто наименьшее из всех таких чисел ж £ N что при любой раскраске рёбер полного врафа на х вершинах е два цвета обязательно найдется подграф, изоморфный Нх с рёбрами цвета ] или педграф изоморфный Н2 с рёбрами цвета 2
Е принципе из результатов классической теории Рамсея понятие, чте числа г(Нх, Н2) обязательно существуют (тс есть, конечны". Интересно, что иногда их можно точно вычислить,
Лемма 10.1, Пусть т > 1, а граф Н такое. чтои(Н) > (то—1)(п—1)+1 и <у.{Н) < то — 1. Тосоа граф Н содержит е качестве посграфа лкбсе дереве ьап вершинах
Доказательство, Зафиксируем т и проведем индукцию не п. База для п — 1 очевидна. Докажем индукционный переход п — 1 —> п (п > 1), Рассмотрим произвольнее дереис Тп на п иершинах. пусть дереЕС Tn_i получено из Тп удалением висячей Еергнины Пусть U — максимальнее независимое множестве ьершин графа Н Тогда \U\ = а(РР) < m — 1. следовательно v{H—U) > (то—1)(п-2)+1 и очевидно a(H-U) < m—1.
По индукционному предположению, граф H — U содержит в качестве подграфа дерево Tn_i Пусть а — Еерглина этого дерева, присоединив к ксторей Еисячую ьершину мы получим дереве Тп. Заметим, чте множество U U {а} не является независимым ввиду максимальности U. следовательно, вершина а смежна хотя с одней Есршнной х Е U. Стметим, что х 0 V(Tn-i) и, присоединив ьершину х к ьершине а дерева Tn_i, получим дереЕС Тп е качестве подграфа графа Н. □
Теорема 10.5. (V. Chvatal) Пусть Тп — дерево на п верьиьпах. Тогоа r(Tn,Km) = (m-l)(n-l) + l.
Доказательство, 1] Докажем, что r(Tn, Кт) > (т — 1)(п — 1) + 1. Для
этего нредъяЕим раскраску рёбер графа ^(т.-1)(тг-1) е ксторей нет ни одного СЕязногс подграфа на п Еершинах с рёбрами цвета 1 и нет клики на т вершинах с рёбрами цвета 2. Разсбьём Есршнны графа ш т—1 клику по п— 1 вершине и покрасим Есе рёбра этих клик в цвет 1, Тогда любой сеязный подграф с рёбрами цвета 1 содержит не белее п— 1 вершины, в частности, нет подграфа с рёбрами цвета 1, изоморфного Тп. Рёбра цвета 2 (тс есть, Есе оставшиеся рёбра) образуют (то — 1)-дсльный граф е котором, счевидне, нет клики на то вершинах
1) Рассмотрим нроизЕСльную раскраску рёбер полного графа K(m-i)(n-i)+i в два цвета. Предположим, что не сушестьует клнки на то вершинах с рёбрами цвета 2. Тсгда то > 1 и a(Gi) < m—1. По лемме 10 1, граф Gi содержит е качестве подграфа любее дерево на п вершинах в частности, дереве, иземерфнее Тп. □
==Индуцированная теорема Рамсея==
===Случай двудольного графа===
===Случай произвольного графа===
