442
правки
Изменения
→Числа Рамсея для произвольных графов
|id=def16
|definition=
Пусть <tex>H_1,H_2</tex> — графы. Число Рамсея <tex>r(H_1,H_2)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что для любого графа <tex>G</tex> на <tex>x</tex> вершинах либо в <tex><tex>G</tex> найдется подграф изоморфный <tex>H_1</tex>, либо в <tex>\overline G</tex> найдется подграф изоморфный <tex>H_2</tex>.
}}
Несложно показать, что эти определения эквивалентны(аналогично определениям для классических чисел Рамсея). Из результатов классической теории Рамсея становится понятно, что числа <tex>r(H_1,H_2)</tex> существуют.
{{Лемма
<tex>1)</tex> Докажем, что <tex>r(T_n,K_m) \geqslant (m-1)(n-1)+1</tex>. Для этого предъявим раскраску рёбер графа <tex>K_{(m-1)(n-1)}</tex>, в которой нет ни одного связного подграфа на <tex>n</tex> вершинах с рёбрами цвета <tex>1</tex> и нет клики на <tex>m</tex> вершинах с рёбрами цвета <tex>2</tex>. Разобьём вершины графа на <tex>m-1</tex> клику по <tex>n-1</tex> вершине и покрасим все рёбра этих клик в цвет <tex>1</tex>. Тогда любой связный подграф с рёбрами цвета <tex>1</tex> содержит не более <tex>n-1</tex> вершины, в частности, нет подграфа с рёбрами цвета <tex>1</tex>, изоморфного <tex>T_n</tex>. Рёбра цвета <tex>2</tex> (то есть, все оставшиеся рёбра) образуют <tex>(m-1)</tex>-дольный граф, в котором, очевидно, нет клики на <tex>m</tex> вершинах.
<tex>2)</tex> Воспользуемся вторым [[#def16|определением]] числа Рамсея <tex>r(H_1, H_2)</tex> Рассмотрим произвольную раскраску рёбер полного графа произвольный граф <tex>G</tex> на <tex>K_{(m-1)(n-1)+1}</tex> в два цветавершинах. Предположим, что не существует клики на в графе <tex>mG</tex> вершинах с рёбрами цвета не существует клики на <tex>2m</tex>вершинах. Тогда <tex>m>1</tex> и <tex>\alpha(G_1\overline G) \leqslant m-1</tex>. По [[#l1|лемме <tex>1</tex>]], граф <tex>G_1\overline G</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах, в частности, дерево, изоморфное <tex>T_n</tex>.
}}
