299
правок
Изменения
→Числа Рамсея для произвольных графов
В принципе из результатов классической теории Рамсея понятие, что числа <tex>r(H_1,H_2)</tex> обязательно существуют (то есть, конечны).
{{Лемма 10.1, |id=lemma1 |statement=Пусть т <tex>m> 1</tex>, а граф Н такое. чтои<tex>H</tex> таков, что <tex>v(НH) > \ge (то—1m-1)(п—1n-1)+1 </tex> и <у.{Нtex>\alpha(H) \le m-1< то — 1/tex>. Тосоа Тогда граф Н <tex>H</tex> содержит е в качестве посграфа лкбсе дереве ьап подграфа любое дерево на <tex>n</tex> вершинах.|proof=Доказательство, Зафиксируем т и проведем индукцию не п. База для п — 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. (|id=th10 |author=V. Chvatal) |statement=Пусть Тп — дерево на п верьиьпах. Тогоа r(Tn,Km) = (m-l)(n-l) + l.|proof=доказательство (необязательно)
Доказательство, 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 содержит е качестве подграфа любее дерево на п вершинах в частности, дереве, иземерфнее Тп. □
}}
==Индуцированная теорема Рамсея==
===Случай двудольного графа===
===Случай произвольного графа===
