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