Изменения

'''Теория Рамсея''' — раздел математики, названный в честь Фрэнка Рамсея, изучающий условия, при которых в произвольно формируемых математических объектах обязан появиться некоторый порядок.

==Числа Рамсея==

{{Определение

|definition='''Числом Рамсея''' <tex>r(m, n)</tex>, где <tex>m, n \in \mathbb N </tex> называют наименьшее из таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске ребер полного графа на <tex>x</tex> вершинах в два цвета найдется клика на <tex>n</tex> вершинах с ребром цвета <tex>1</tex> или клика на <tex>m</tex> вершинах с ребром цвета <tex>2</tex>. }}

===Существование. Оценки сверху===

===Экстремальные примеры и оценки снизу===

Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, этих значении известно немногим больше, чем перечислено выше.

|definition=Графом Рамсея <tex>R(n,m)</tex> назовем такой граф на <tex>r(n,m)-1</tex> вершинах, не содержащий ни клики на <tex>n</tex> вершинах ни независимого множества на <tex>m</tex> вершинах(то есть, граф на ребрах цвета 1 из раскраски в два цвета ребер графа <tex>K_{r(m,n)-1}</tex>, не содержащей ни клики на <tex>n</tex> вершинах с рёбрами цвета 1 ни клики на <tex>m</tex> вершинах с рёбрами цвета 2).

}}

===Числа Рамсея для раскрасок в несколько цветов===

{{Определение

|definition=

Пусть <tex>k,n_1,...,n_k \in \mathbb N</tex>. Число Рамсея <tex>r(k;n_1,...,n_k)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в <tex>k</tex> цветов для некоторого <tex>i \in [1..k]</tex> обязательно найдётся клика на <tex>n_i</tex> вершинах с рёбрами цвета <tex>i</tex>.

==Числа Рамсея больших размерностей==

{{Определение

|definition=

Пусть <tex>m,k,n_1,...,n_k \in \mathbb N</tex>, причём <tex>n_1,...,n_k \ge m</tex>. Число Рамсея <tex>r_m(k; n_1,...,n_k)</tex> — наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске <tex>m</tex>-элементных подмножеств <tex>x</tex>-элементного множества <tex>M</tex> в <tex>k</tex> цветов для некоторого <tex>i \in [1..k]</tex> обязательно найдётся такое множество <tex>W_i</tex>, что <tex>|W_i|=n_i</tex> и все <tex>m</tex>-элементные подмножества множества <tex>W_i</tex> имеют цвет <tex>i</tex>.

}}

{{Определение

|definition=

Число <tex>m</tex> называется размерностью числа Рамсея <tex>r_m(k;n_1,...,n_k)</tex>.

}}

{{Определение

Для каждою множества <tex>M</tex> через <tex>M^k</tex> мы будем обозначать множество всех <tex>k</tex>-элементных подмножеств <tex>M</tex>.

}}

Еще один способ обобщения классической теории Рамсея — замена клик на произвольные графы-шаблоны.

{{Определение

|definition=

Пусть <tex>H_1,h_2</tex> — два данных графа. Число Рамсея <tex>r(H_1,H_2)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в два цвета обязательно найдется подграф, изоморфный <tex>H_1</tex> с рёбрами цвета 1 или подграф изоморфный <tex>H_2</tex> с рёбрами цвета 2

Докажем похожее на теорему Рамсея, но значительно более сложнее утверждение.

{{Определение

|definition=Пусть <tex>H</tex> — граф. Граф <tex>G</tex> называется рамсеееским графом для <tex>H</tex>, если при любой раскраске рёбер графа <tex>G</tex> в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G</tex> изоморфный <tex>H</tex>}}

При замене произвольного графа <tex>H</tex> на клику мы получаем частный случай классической теоремы Рамсея. Для клики добавленное слово "индуцированный" ничего не меняет. Но значительно усложняет ситуацию для произвольного графа <tex>H</tex>.

где <tex>V_1(G)</tex> и <tex>V_2(G)</tex> — разбиение множества вершин <tex>V(G)</tex> на две доли, а рёбра соединяют вершины из разных долей.

{{Определение

|definition=

Пусть <tex>H,G</tex> — двудольные графы. Инъективное отображение <tex>\phi:V(H)\rightarrow V(G)</tex> назовём погружением, если оно удовлетворяет двум условиям.<br>

Напомним, что для множества <tex>X</tex> через <tex>X^k</tex> мы обозначаем множество всех <tex>k</tex>-элементных подмножеств множества <tex>X</tex>.

{{Определение

|definition=Назовем особым двудольный граф вида

<tex>H=(V,V^k,E(H))</tex>, где <tex>E(H)=</tex>{<tex>xY|x\in V,Y\in V^k, x\in Y</tex>}