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