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

Материал из Викиконспекты
Версия от 21:43, 5 января 2014; Kamigan4eg (обсуждение | вклад) (Числа Рамсея)
Перейти к: навигация, поиск
Эта статья находится в разработке!

Числа Рамсея

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

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

</wikitex>

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

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

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

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

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

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

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

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