442
правки
Изменения
Нет описания правки
|id=def4
|definition=
'''Число Рамсея''' <tex>r(k;n_1,...\ldots,n_k)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в <tex>k</tex> цветов для некоторого <tex>i \in [1..\ldots k]</tex> обязательно найдётся клика на <tex>n_i</tex> вершинах с рёбрами цвета <tex>i</tex>. <tex>k,n_1,...\ldots,n_k \in \mathbb N</tex>
}}
{{Теорема
|id=ter3|about=3
|statement=Пусть <tex>k,n_1,...\ldots,n_k \ge 2</tex> {{---}} натуральные числа. Тогда выполняются следующие утверждения:<tex>1) r(k;n_1,...\ldots,n_k) \le r(k;n_1-1,n_2,...\ldots,n_k)+r(k;n_1,n_2-1,...\ldots,n_k)++r(k;n_1,n_2,...\ldots,n_k-1)-k+2</tex><tex dpi="150">2)r(k;n_1,...\ldots,n_k) \le \frac{(n_1+n_2+...\ldots+n_k)!}{n_1!\cdot n_2!\cdot ...\ldots\cdot n_k!}</tex>
|proof=
1) Доказательстве полностью аналогично пункту 1 доказательства [[#ter1|теоремы 1]]
2) Доказательство аналогично [[#u1|утверждению 1]]. Нужно лишь убедиться в очевидном неравенстве для случая, когда хотя бы одно из чисел <tex>n_1,...\ldots ,n_k</tex> равно 1 (левая часть в этом случае равна 1, а правая, очевидно не меньше 1) и заметить, что полиномиальные коэффициенты из очевидных комбинаторных соображений удовлетворяют соотношению:
<tex dpi="150">\frac{(n_1+n_2+...\ldots +n_k)!}{n_1!\cdot n_2!\cdot ...\ldots \cdot n_k!}=\sum\limits_{i = 1}^k\frac{(n_1+...\ldots+(n_i-1)+...\ldots +n_k)!}{n_1!\cdot ...\ldots \cdot (n_i-1)!\cdot ...\ldots \cdot n_k!}</tex>
Следовательно, 2 неравенство из данной [[#ter3|теоремы]] выводится из неравенства 1 по индукции.
|id=def5
|definition=
Пусть <tex>m,k,n_1,...\ldots ,n_k \in \mathbb N</tex>, причём <tex>n_1,...\ldots ,n_k \ge m</tex>. Число Рамсея <tex>r_m(k; n_1,...\ldots ,n_k)</tex> — наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске <tex>m</tex>-элементных подмножеств <tex>x</tex>-элементного множества <tex>M</tex> в <tex>k</tex> цветов для некоторого <tex>i \in [1..\ldots k]</tex> обязательно найдётся такое множество <tex>W_i</tex>, что <tex>|W_i|=n_i</tex> и все <tex>m</tex>-элементные подмножества множества <tex>W_i</tex> имеют цвет <tex>i</tex>. Число <tex>m</tex> называют размерностью числа Рамсея <tex>r_m(k;n_1,...\ldots ,n_k)</tex>.
}}
}}
{{Теорема
|id=ter4|about=4|statement=Пусть <tex>m,k,n_1,...\ldots,n_k</tex> {{---}} натуральные числа, причем <tex>k \ge 2</tex>, а <tex>n_1,...\ldots ,n_k \ge m</tex>. Тогда число Рамсея <tex>r_m(k;n_1,...\ldots n_k)</tex> существует(то есть, конечно)
|proof=
1)Мы будем доказывать теорему по индукции. Начнем со случая <tex>k=2</tex>. Приступая к доказательству для числа <tex>r_m(n_1,n_2)</tex> мы будем считать доказанным утверждение теоремы для чисел Рамсея всех меньших размерностей и чисел Рамсея размерности <tex>m</tex> с меньшей суммой <tex>n_1+n_2</tex>. В качестве базы будем использовать случай чисел Рамсея размерности 2 разобранный выше. Итак, мы докажем, что
2)При <tex>k>2</tex> будем вести индукцию по <tex>k</tex> с доказанной выше базой <tex>k=2</tex>. При <tex>k>2</tex> мы докажем неравенство
<tex>r_m(k;n_1,...\ldots ,n_k) \le q=r_m(r_m(k-1;n_1,...\ldots ,n_{k-1}),n_k)</tex>
Для этого мы рассмотрим множество <tex>M</tex> на <tex>q</tex> вершинах и произвольную раскраску <tex>\rho:M^m \rightarrow [1..\ldots k]</tex> в <tex>k</tex>цветов. Рассмотрим раскраску <tex>\rho':M^m \rightarrow </tex>{<tex>0,k</tex>}, в которой цвета <tex>1,...\ldots,k-1</tex> раскраски <tex>\rho</tex> склеены в цвет 0. Тогда существует либо таксе подмножество <tex>M_0 \subset M</tex>, что <tex>|M_0|=r_m(k-1;n_1,...\ldots ,n_{k-1})</tex> и <tex>\rho'(A)=0</tex> на всех <tex>A \in M_0^m</tex>, либо существует такое <tex>n_k</tex>-элементное подмножество <tex>M_k \subset M</tex>, что <tex>\rho(A)=\rho'(A)=k</tex> на всех <tex>A \in M^m_k</tex>. Во втором случае <tex>M_k</tex> — искомое подмножество, а в первом случае заметим, что на любом подмножестве <tex>A \in M_0^m</tex> из <tex>\rho'(A)=0</tex> следует <tex>\rho(A) \in [1..\ldots k-1]</tex>. Исходя из размера множества <tex>M_0</tex> по индукционному предположению получаем, что найдется искомое подмножество множества <tex>M</tex> для одного из цветов <tex>1,...\ldots ,k-1</tex>
}}
