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

Материал из Викиконспекты
Перейти к: навигация, поиск
(Числа Рамсея)
(Числа Рамсея)
Строка 1: Строка 1:
 
{{В разработке}}
 
{{В разработке}}
 
==Числа Рамсея==
 
==Числа Рамсея==
Основным объектов изучения будут полные графы, ребра которых покрашены в несколько цветов. В дальнейшем, для простоты, под графом будем понимать полный граф на n вершинах.
+
Основным объектов изучения будут полные графы, ребра которых покрашены в несколько цветов. В дальнейшем, для простоты, под графом будем понимать полный граф на <tex>n</tex> вершинах.
{{Определение|definition=Пусть <tex>m, n \in N</tex>. Число Рамсея $r(m,n)$ — это наименьшее из таких чисел $x \in N$, что при любой раскраске ребер полного графа на $x$ вершинах в два цвета найдется граф на $n$ вершинах с ребром цвета 1 или граф на $m$ вершинах с ребром цвета 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.}}
 
===Существование. Оценки сверху===
 
===Существование. Оценки сверху===
 
===Экстремальные примеры и оценки снизу===
 
===Экстремальные примеры и оценки снизу===

Версия 21:55, 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.

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

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

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

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

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

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

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

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