Редактирование: Теория Рамсея

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

Внимание! Вы не авторизовались на сайте. Ваш IP-адрес будет публично видимым, если вы будете вносить любые правки. Если вы войдёте или создадите учётную запись, правки вместо этого будут связаны с вашим именем пользователя, а также у вас появятся другие преимущества.

Правка может быть отменена. Пожалуйста, просмотрите сравнение версий, чтобы убедиться, что это именно те изменения, которые вас интересуют, и нажмите «Записать страницу», чтобы изменения вступили в силу.
Текущая версия Ваш текст
Строка 211: Строка 211:
 
|statement=<tex>\forall k, n_1, \ldots n_k \in \mathbb N </tex> существует число Рамсея <tex>r(n_1,\ldots,n_k)</tex>, при этом <tex>r(n_1,\ldots,n_k)\leqslant r(n_1,\ldots, n_{k-2}, r(n_{k-1},\;n_k)).</tex>
 
|statement=<tex>\forall k, n_1, \ldots n_k \in \mathbb N </tex> существует число Рамсея <tex>r(n_1,\ldots,n_k)</tex>, при этом <tex>r(n_1,\ldots,n_k)\leqslant r(n_1,\ldots, n_{k-2}, r(n_{k-1},\;n_k)).</tex>
 
|proof=
 
|proof=
Возьмем граф из <tex>r(n_1,\ldots, n_{k-2}, r(n_{k-1}, n_k))</tex> вершин и окрасим его рёбра в <tex>k</tex> цветов. Пока что будем считать цвета <tex>k-1</tex> и <tex>k</tex> одним цветом. Тогда граф будет <tex>(k-1)</tex>-цветным. Согласно определению числа Рамсея <tex>r(n_1,\ldots,n_{k-2},r(n_{k-1},n_k))</tex>, такой граф либо содержит <tex>K_{n_i}</tex> для некоторого цвета <tex>i</tex>, такого что <tex>1\leqslant i\leqslant k-2</tex>, либо <tex>K_{r(n_{k-1},n_k)}</tex>, окрашенный общим цветом <tex>k-1</tex> и <tex>k</tex>. В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный <tex>r(n_{k-1},n_k)</tex> — вершинный граф содержит либо <tex>K_{n_{k-1}}</tex> цвета <tex>k-1</tex>, либо <tex>K_{n_k}</tex> цвета <tex>k</tex>. Таким образом любое число Рамсея для раскраски в <tex>k</tex> цветов ограничено некоторым числом Рамсея для меньшего количества цветов, следовательно, <tex>r(n_1,\ldots,n_k)</tex> существует для любых <tex> k, n_1, \ldots n_k, \in \mathbb N </tex>, и теорема доказана.
+
Возьмем граф из <tex>r(n_1,\ldots, n_{k-2}, r(n_{k-1}, n_k))</tex> вершин и окрасим его рёбра в <tex>k</tex> цветов. Пока что будем считать цвета <tex>k-1</tex> и <tex>k</tex> одним цветом. Тогда граф будет <tex>(k-1)</tex>-цветным. Согласно определению числа Рамсея <tex>r(n_1,\ldots,n_{k-2},r(n_{k-1},n_k))</tex>, такой граф либо содержит <tex>K_{n_i}</tex> для некоторого цвета <tex>i</tex>, такого что <tex>1\leqslant i\leqslant k-2</tex>, либо <tex>K_{r(k, n_{k-1},n_k)}</tex>, окрашенный общим цветом <tex>k-1</tex> и <tex>k</tex>. В первом случае доказательство завершено. Во втором случае вернём прежние цвета и заметим, что, по определению числа Рамсея, полный <tex>r(n_{k-1},n_k)</tex> — вершинный граф содержит либо <tex>K_{n_{k-1}}</tex> цвета <tex>k-1</tex>, либо <tex>K_{n_k}</tex> цвета <tex>k</tex>. Таким образом любое число Рамсея для раскраски в <tex>k</tex> цветов ограничено некоторым числом Рамсея для меньшего количества цветов, следовательно, <tex>r(n_1,\ldots,n_k)</tex> существует для любых <tex> k, n_1, \ldots n_k, \in \mathbb N </tex>, и теорема доказана.
 
}}
 
}}
  

Пожалуйста, учтите, что любой ваш вклад в проект «Викиконспекты» может быть отредактирован или удалён другими участниками. Если вы не хотите, чтобы кто-либо изменял ваши тексты, не помещайте их сюда.
Вы также подтверждаете, что являетесь автором вносимых дополнений, или скопировали их из источника, допускающего свободное распространение и изменение своего содержимого (см. Викиконспекты:Авторские права). НЕ РАЗМЕЩАЙТЕ БЕЗ РАЗРЕШЕНИЯ ОХРАНЯЕМЫЕ АВТОРСКИМ ПРАВОМ МАТЕРИАЛЫ!

Чтобы изменить эту страницу, пожалуйста, ответьте на приведённый ниже вопрос (подробнее):

Отменить | Справка по редактированию (в новом окне)