Изменения

Перейти к: навигация, поиск

Теория Рамсея

621 байт добавлено, 18:52, 30 ноября 2018
Индуцированная число Рамсея
<tex>2)</tex> Рассмотрим произвольную раскраску рёбер полного графа <tex>K_{(m-1)(n-1)+1}</tex> в два цвета. Предположим, что не существует клики на <tex>m</tex> вершинах с рёбрами цвета <tex>2</tex>. Тогда <tex>m>1</tex> и <tex>\alpha(G_1) \le m-1</tex>. По [[#l1|лемме <tex>1</tex>]], граф <tex>G_1</tex> содержит в качестве подграфа любое дерево на <tex>n</tex> вершинах, в частности, дерево, изоморфное <tex>T_n</tex>.
}}
==Индуцированная число теорема Рамсея==
{{Определение
|id=def9
|id=def11
|definition='''Индуцированным числом Рамсея'''(англ. ''induced Ramsey number'') <tex>r_{ind}(H)</tex> для графа <tex>H</tex> будем называть минимальное число <tex>x \in \mathbb N</tex>, такое что существует рамсеевский граф для графа <tex>H</tex> на <tex>x</tex> вершинах.}}
Заметим, что при замене произвольного графа <tex>H</tex> на клику мы получаем частный случай классической теоремы Рамсея.
При замене произвольного графа <tex>H</tex> на клику мы получаем частный случай классической теоремы Рамсея.
{{Теорема
|id=ter6
|statement=Для любого графа <tex>H</tex> существует индуцированное число Рамсея <tex>r(H)</tex>.
}}
ДоказатеДоказательство данной теоремы было приведено независимо различными математиками, однако благодаря нему получилось предоставить только очень грубые оценки значений индуцированных чисел Рамсея. В данный момент проблема нахождения сколько-нибудь точных границ индуцированных чисел Рамсея является нерешенной задачей математики.
==См. также==
442
правки

Навигация