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

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

Числа Рамсея

Основным объектов изучения будут полные графы, ребра которых покрашены в несколько цветов. В дальнейшем, для простоты, под графом будем понимать полный граф на [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.

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

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

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

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

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

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