Теория Рамсея — различия между версиями
(→Существование. Оценки сверху) |
(→Числа Рамсея) |
||
Строка 1: | Строка 1: | ||
{{В разработке}} | {{В разработке}} | ||
==Числа Рамсея== | ==Числа Рамсея== | ||
− | Основным объектов изучения будут полные графы, ребра которых покрашены в несколько цветов. В дальнейшем, для простоты, | + | Основным объектов изучения будут полные графы, ребра которых покрашены в несколько цветов. В дальнейшем, для простоты, полный граф на <tex>n</tex> вершинах будем называть кликой. |
− | {{Определение|definition=Пусть <tex>m, n \in \mathbb N</tex>. Число Рамсея <tex>r(m, n)</tex> — это наименьшее из таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске ребер полного графа на <tex>x</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.}} |
===Существование. Оценки сверху=== | ===Существование. Оценки сверху=== | ||
{{Теорема|id=t1|author=P. Erdos, G. Szekeres | {{Теорема|id=t1|author=P. Erdos, G. Szekeres | ||
|statement=Пусть <tex>n,m \ge 2</tex>-натуральные числа. Тогда <tex>r(n,m) \le r(n,m-1)+r(n-1,m)</tex>. Если оба числа <tex>r(n,m-1)</tex> и <tex>r(n-1,m)</tex>-четные, то неравенство строгое. | |statement=Пусть <tex>n,m \ge 2</tex>-натуральные числа. Тогда <tex>r(n,m) \le r(n,m-1)+r(n-1,m)</tex>. Если оба числа <tex>r(n,m-1)</tex> и <tex>r(n-1,m)</tex>-четные, то неравенство строгое. | ||
|proof= | |proof= | ||
− | 1) Рассмотрим | + | 1) Рассмотрим клику на <tex>r(n, m - 1) + r(n - 1, m)</tex> вершинах с рёбрами цветов 1 и 2 и ее произвольную вершину <tex>a</tex>. Тогда либо от вершины <tex>a</tex> отходит хотя бы <tex>r(n, m - 1)</tex> рёбер цвета 2, либо от вершины <tex>a</tex> отходит хотя бы <tex>r(n—1, m)</tex> рёбер цвета 1. Случаи аналогичны, рассмотрим первый случай и клику на <tex>r(n, m — 1)</tex> вершинах, соединенных с <tex>a</tex> рёбрами цвета 2. На этих вершинах есть либо клика на <tex>n</tex> вершинах с ребрами цвета 1, либо клика на <tex>m—1</tex> вершинах с рёбрами цвета 2. Во втором случае добавим вершину <tex>a</tex> и получим клику на <tex>m</tex> вершинах с рёбрами цвета 2. Теперь из определения <tex>r(n, m)</tex> следует [[#t1|неравенство]]. |
− | 2) Рассмотрим | + | 2) Рассмотрим клику на <tex>r(n, m-l)+r(n-1, m)-1</tex> вершинах с рёбрами цветов 1 и 2 и его произвольную вершину <tex>a</tex>. Если вершине <tex>a</tex> инцидентны хотя бы <tex>r(n,m-1)</tex> рёбер цвета 2 или хотя бы <tex>r(n-1,m)</tex> рёбер цвета 1, то мы найдём в графе клику на <tex>n</tex> вершинах с рёбрами цвета 1 или клику на <tex>m</tex> вершинах с рёбрами цвета 2. Остаётся лишь случай, когда вершине <tex>a</tex> инцидентны ровно <tex>r(n, m-1)-1</tex> рёбер цвета 2, то же самое для всех остальных вершин. Это означает, что в графе из рёбер цвета 2 всего <tex>r(n, m-1)+r(n-1, m)-1</tex> вершин и степень каждой вершины равна <tex>r(n, m-1)-1</tex>. Однако, тогда в графе нечётное количество вершин нечётной степени. Противоречие показывает нам, что в случае, когда <tex>r(n, m-1)</tex> и <tex>r(n-1,m)</tex> — чётные, выполняется неравенство <tex>(n, m)<r(n, m-1)+r(n-1, m)-1</tex>. |
}} | }} | ||
Версия 22:58, 5 января 2014
Эта статья находится в разработке!
Содержание
Числа Рамсея
Основным объектов изучения будут полные графы, ребра которых покрашены в несколько цветов. В дальнейшем, для простоты, полный граф на
вершинах будем называть кликой.Определение: |
Пусть | . Число Рамсея — это наименьшее из таких чисел , что при любой раскраске ребер полного графа на вершинах в два цвета найдется клика на вершинах с ребром цвета 1 или клика на вершинах с ребром цвета 2.
Существование. Оценки сверху
Теорема (P. Erdos, G. Szekeres): |
Пусть -натуральные числа. Тогда . Если оба числа и -четные, то неравенство строгое. |
Доказательство: |
1) Рассмотрим клику на неравенство. 2) Рассмотрим клику на вершинах с рёбрами цветов 1 и 2 и ее произвольную вершину . Тогда либо от вершины отходит хотя бы рёбер цвета 2, либо от вершины отходит хотя бы рёбер цвета 1. Случаи аналогичны, рассмотрим первый случай и клику на вершинах, соединенных с рёбрами цвета 2. На этих вершинах есть либо клика на вершинах с ребрами цвета 1, либо клика на вершинах с рёбрами цвета 2. Во втором случае добавим вершину и получим клику на вершинах с рёбрами цвета 2. Теперь из определения следует вершинах с рёбрами цветов 1 и 2 и его произвольную вершину . Если вершине инцидентны хотя бы рёбер цвета 2 или хотя бы рёбер цвета 1, то мы найдём в графе клику на вершинах с рёбрами цвета 1 или клику на вершинах с рёбрами цвета 2. Остаётся лишь случай, когда вершине инцидентны ровно рёбер цвета 2, то же самое для всех остальных вершин. Это означает, что в графе из рёбер цвета 2 всего вершин и степень каждой вершины равна . Однако, тогда в графе нечётное количество вершин нечётной степени. Противоречие показывает нам, что в случае, когда и — чётные, выполняется неравенство . |