Теория Рамсея — различия между версиями
(→Числа Рамсея) |
(→Числа Рамсея) |
||
| Строка 1: | Строка 1: | ||
{{В разработке}} | {{В разработке}} | ||
==Числа Рамсея== | ==Числа Рамсея== | ||
| − | + | Основным объектов изучения будут полные графы, ребра которых покрашены в несколько цветов. В дальнейшем, для простоты, под графом будем понимать полный граф на n вершинах. | |
| − | {{Определение|definition=Пусть | + | {{Определение|definition=Пусть <tex>m, n \in N</tex>. Число Рамсея $r(m,n)$ — это наименьшее из таких чисел $x \in N$, что при любой раскраске ребер полного графа на $x$ вершинах в два цвета найдется граф на $n$ вершинах с ребром цвета 1 или граф на $m$ вершинах с ребром цвета 2.}} |
===Существование. Оценки сверху=== | ===Существование. Оценки сверху=== | ||
===Экстремальные примеры и оценки снизу=== | ===Экстремальные примеры и оценки снизу=== | ||
Версия 21:44, 5 января 2014
Эта статья находится в разработке!
Содержание
Числа Рамсея
Основным объектов изучения будут полные графы, ребра которых покрашены в несколько цветов. В дальнейшем, для простоты, под графом будем понимать полный граф на n вершинах.
| Определение: |
| Пусть . Число Рамсея $r(m,n)$ — это наименьшее из таких чисел $x \in N$, что при любой раскраске ребер полного графа на $x$ вершинах в два цвета найдется граф на $n$ вершинах с ребром цвета 1 или граф на $m$ вершинах с ребром цвета 2. |
