Изменения

Перейти к: навигация, поиск

Теория Рамсея

Нет изменений в размере, 00:18, 28 ноября 2018
м
Существование. Оценки сверху
<tex>2)</tex> Предположим, <tex>p=r(n-1,\;m)</tex> и <tex>q=r(n,\;m-1)</tex> оба чётны. Положим <tex>t=p+q-1</tex> и рассмотрим чёрно-белый граф из <tex>t</tex> вершин. Если <tex>d_i</tex> степень <tex>i</tex>-й вершины в чёрном подграфе, то, согласно [[Лемма о рукопожатиях|лемме о рукопожатиях]], <tex>\sum_{i=1}^t d_i</tex> — чётно. Поскольку <tex>t</tex> нечётно, должно существовать чётное <tex>d_i</tex>. Для определённости положим, что <tex>d_1</tex> чётно. Обозначим через <tex>M</tex> и <tex>N</tex> вершины инцидентные вершине 1 в чёрном и белом подграфах соответственно. Тогда <tex>|M|=d_1</tex> и <tex>|N|=t-1-d_1</tex> оба чётны. Согласно принципу Дирихле, либо <tex>|M|\geqslant p-1</tex>, либо <tex>N\geqslant q</tex>. Так как <tex>|M|</tex> чётно, а <tex>p-1</tex> нечётно, первое неравенство можно усилить, так что либо <tex>|M|\geqslant p</tex>, либо <tex>|N|\geqslant q</tex>.
Предположим <tex>|M|\geqslant p=r(n-1,\;m)</tex>. Тогда либо подграф, порождённый множеством <tex>M</tex>, содержит белый <tex>K_sK_m</tex> и доказательство завершено, либо он содержит чёрный <tex>K_{n-1}</tex>, который вместе с вершиной 1 образует чёрный <tex>K_n</tex>. Случай <tex>|N|\geqslant q=r(n,\;m-1)</tex> рассматривается аналогично.
}}
{{Утверждение|id=u1|about=1|statement=Для натуральных чисел <tex>m,n</tex> выполняется равенство <tex>r(n,m) \le C_{n+m-2}^{n-1}</tex>
442
правки

Навигация