442
правки
Изменения
м
→Существование. Оценки сверху
|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=
<tex>1) Рассмотрим клику на </tex> Докажем с помощью метода математической индукции по <tex>r+s</tex>. '''База:''' <tex>R(n, m \;1) = R(1,\;n) = 1</tex>, так как 1-вершинный граф можно считать полным графом любого цвета. '''Индукционный переход:'''. Пусть <tex>r>1</tex> и <tex>s>1</tex>. Рассмотрим полный чёрно-белый граф из <tex>R(r- 1,\;s) + R(r(n ,\;s- 1, m)</tex> вершинах с рёбрами цветов 1 вершин. Возьмём произвольную вершину <tex>v</tex> и 2 обозначим через <tex>M</tex> и ее произвольную вершину <tex>aN</tex>. Тогда либо от вершины множества инцидентные <tex>av</tex> отходит хотя бы в чёрном и белом подграфе соответственно. Так как в графе <tex>R(r-1,\;s)+R(nr, m \;s- 1)=|M|+|N|+1</tex> рёбер цвета 2вершин, согласно принципу Дирихле, либо от вершины <tex>a|M|\geqslant R(r-1,\;s)</tex> отходит хотя бы , либо <tex>|N|\geqslant R(r(n—1, m\;s-1)</tex> рёбер цвета 1. Случаи аналогичны, рассмотрим первый случай и клику на Пусть <tex>|M|\geqslant R(r(n-1, m — 1\;s)</tex> вершинах, соединенных с . Тогда либо в <tex>aM</tex> рёбрами цвета 2. На этих вершинах (и следовательно во всём графе) есть либо клика на белый <tex>nK_s</tex> вершинах с ребрами цвета 1, что завершает доказательство, либо клика на в <tex>M</tex> есть чёрный <tex>m—1K_{r-1}</tex> вершинах , который вместе с рёбрами цвета 2. Во втором случае добавим вершину <tex>av</tex> и получим клику на образует чёрный <tex>mK_r</tex> вершинах с рёбрами цвета 2. Теперь из определения Случай <tex>|N|\geqslant R(r(n, m\;s-1)</tex> следует неравенство [[#ter1|из теоремы 1]]рассматривается аналогично.
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>.
}}
