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

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

Числа Рамсея

Основным объектов изучения будут полные графы, ребра которых покрашены в несколько цветов. В дальнейшем, для простоты, полный граф на [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 \ge 2[/math]-натуральные числа. Тогда [math]r(n,m) \le 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) Рассмотрим клику на [math]r(n, m-l)+r(n-1, m)-1[/math] вершинах с рёбрами цветов 1 и 2 и его произвольную вершину [math]a[/math]. Если вершине [math]a[/math] инцидентны хотя бы [math]r(n,m-1)[/math] рёбер цвета 2 или хотя бы [math]r(n-1,m)[/math] рёбер цвета 1, то мы найдём в графе клику на [math]n[/math] вершинах с рёбрами цвета 1 или клику на [math]m[/math] вершинах с рёбрами цвета 2. Остаётся лишь случай, когда вершине [math]a[/math] инцидентны ровно [math]r(n, m-1)-1[/math] рёбер цвета 2, то же самое для всех остальных вершин. Это означает, что в графе из рёбер цвета 2 всего [math]r(n, m-1)+r(n-1, m)-1[/math] вершин и степень каждой вершины равна [math]r(n, m-1)-1[/math]. Однако, тогда в графе нечётное количество вершин нечётной степени. Противоречие показывает нам, что в случае, когда [math]r(n, m-1)[/math] и [math]r(n-1,m)[/math] — чётные, выполняется неравенство [math](n, m)\lt r(n, m-1)+r(n-1, m)-1[/math].

[math]\triangleleft[/math]

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

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

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

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

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