Теория Рамсея — различия между версиями

Материал из Викиконспекты
Перейти к: навигация, поиск
(Числа Рамсея)
(Существование. Оценки сверху)
Строка 4: Строка 4:
 
{{Определение|definition=Пусть <tex>m, n \in \mathbb N</tex>. Число Рамсея <tex>r(m, n)</tex> — это наименьшее из таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске ребер полного графа на <tex>x</tex> вершинах в два цвета найдется граф на <tex>n</tex> вершинах с ребром цвета 1 или граф на <tex>m</tex> вершинах с ребром цвета 2.}}
 
{{Определение|definition=Пусть <tex>m, n \in \mathbb N</tex>. Число Рамсея <tex>r(m, n)</tex> — это наименьшее из таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске ребер полного графа на <tex>x</tex> вершинах в два цвета найдется граф на <tex>n</tex> вершинах с ребром цвета 1 или граф на <tex>m</tex> вершинах с ребром цвета 2.}}
 
===Существование. Оценки сверху===
 
===Существование. Оценки сверху===
 +
{{Теорема|id=t1|author=P. Erdos, G. Szekeres
 +
|statement=Пусть <tex>n,m>=2</tex>-натуральные числа. Тогда <tex>r(n,m)<=r(n,m-1)+r(n-1,m)</tex>. Если оба числа <tex>r(n,m-1)</tex> и <tex>r(n-1,m)</tex>-четные, то неравенство строгое.
 +
|proof=
 +
1) Рассмотрим  граф на <tex>r(n, m — 1) + r(n — 1, m)</tex> вершинах с рёбрами цветов 1 и 2 и ее произвольную вершину <tex>a</tex>. Тогда либо от вершины <tex>a</tex> отходит хотя бы <tex>r(n, m — 1)</tex> рёбер цвета 2, либо от вершины <tex>a</tex> отходит хотя бы <tex>r(n—1, m)</tex> рёбер цвета 1. Случаи аналогичны, рассмотрим первый случай и граф на <tex>r(n, m — 1)</tex> вершинах, соединенных с <tex>a</tex> рёбрами цвета 2. На этих вершинах есть либо граф на <tex>n</tex> вершинах с ребрами цвета 1, либо граф на <tex>m—1</tex> вершинах с рёбрами цвета 2. Во втором случае добавим вершину <tex>a</tex> и получим граф на <tex>m</tex> вершинах с рёбрами цвета 2. Теперь из определения <tex>r(n, m)</tex> следует [[#t1|неравенство]].
 +
2) Рассмотрим граф на r(n, m—l)+r(n—1, m) —1 вершинах с рёбрами цветов 1 и 2 и его произвольную вершину a. Если вершине a инцидентны хотя бы r(n,m — 1) рёбер цвета 2 или хотя бы r(n — 1,m) рёбер цвета 1, то мы найдём граф на n вершинах с рёбрами цвета 1 или граф на m вершинах с рёбрами цвета 2. Остаётся лишь случай, когда вершине а инцидентны ровно r(n, m — 1) — 1 рёбер цвета 2, то же самое для всех остальных вершин. Это означает, что в графе из рёбер цвета 2 всего r(n, m — 1) + r(n — 1, m) — 1 вершин и степень каждой вершины равна r(n, m — 1) — 1. Однако, тогда в графе нечётное количество вершин нечётной степени. Противоречие показывает нам, что в случае, когда r(n, m — 1) и r(n — 1,m) — чётные, выполняется неравенство r(n, m) < r(n, m— 1) + r(n — 1, m) — 1.
 +
}}
 +
 
===Экстремальные примеры и оценки снизу===
 
===Экстремальные примеры и оценки снизу===
 
===Числа Рамсея для раскрасок в несколько цветов===
 
===Числа Рамсея для раскрасок в несколько цветов===

Версия 22:25, 5 января 2014

Эта статья находится в разработке!

Числа Рамсея

Основным объектов изучения будут полные графы, ребра которых покрашены в несколько цветов. В дальнейшем, для простоты, под графом будем понимать полный граф на [math]n[/math] вершинах.

Определение:
Пусть [math]m, n \in \mathbb N[/math]. Число Рамсея [math]r(m, n)[/math] — это наименьшее из таких чисел [math]x \in \mathbb N[/math], что при любой раскраске ребер полного графа на [math]x[/math] вершинах в два цвета найдется граф на [math]n[/math] вершинах с ребром цвета 1 или граф на [math]m[/math] вершинах с ребром цвета 2.

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

Теорема (P. Erdos, G. Szekeres):
Пусть [math]n,m\gt =2[/math]-натуральные числа. Тогда [math]r(n,m)\lt =r(n,m-1)+r(n-1,m)[/math]. Если оба числа [math]r(n,m-1)[/math] и [math]r(n-1,m)[/math]-четные, то неравенство строгое.
Доказательство:
[math]\triangleright[/math]

1) Рассмотрим граф на [math]r(n, m — 1) + r(n — 1, m)[/math] вершинах с рёбрами цветов 1 и 2 и ее произвольную вершину [math]a[/math]. Тогда либо от вершины [math]a[/math] отходит хотя бы [math]r(n, m — 1)[/math] рёбер цвета 2, либо от вершины [math]a[/math] отходит хотя бы [math]r(n—1, m)[/math] рёбер цвета 1. Случаи аналогичны, рассмотрим первый случай и граф на [math]r(n, m — 1)[/math] вершинах, соединенных с [math]a[/math] рёбрами цвета 2. На этих вершинах есть либо граф на [math]n[/math] вершинах с ребрами цвета 1, либо граф на [math]m—1[/math] вершинах с рёбрами цвета 2. Во втором случае добавим вершину [math]a[/math] и получим граф на [math]m[/math] вершинах с рёбрами цвета 2. Теперь из определения [math]r(n, m)[/math] следует неравенство.

2) Рассмотрим граф на r(n, m—l)+r(n—1, m) —1 вершинах с рёбрами цветов 1 и 2 и его произвольную вершину a. Если вершине a инцидентны хотя бы r(n,m — 1) рёбер цвета 2 или хотя бы r(n — 1,m) рёбер цвета 1, то мы найдём граф на n вершинах с рёбрами цвета 1 или граф на m вершинах с рёбрами цвета 2. Остаётся лишь случай, когда вершине а инцидентны ровно r(n, m — 1) — 1 рёбер цвета 2, то же самое для всех остальных вершин. Это означает, что в графе из рёбер цвета 2 всего r(n, m — 1) + r(n — 1, m) — 1 вершин и степень каждой вершины равна r(n, m — 1) — 1. Однако, тогда в графе нечётное количество вершин нечётной степени. Противоречие показывает нам, что в случае, когда r(n, m — 1) и r(n — 1,m) — чётные, выполняется неравенство r(n, m) < r(n, m— 1) + r(n — 1, m) — 1.
[math]\triangleleft[/math]

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

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

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

Числа Рамсея для произвольных графов

Индуцированная теорема Рамсея

Случай двудольного графа

Случай произвольного графа