442
правки
Изменения
→Числа Рамсея больших размерностей
|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>.
}}
Заметим, что числа Рамсея размерности <tex>2</tex> — это определённые ранее числа Рамсея для клик.
{{Определение
|id=def7|definition=
Для каждою каждого множества <tex>M</tex> через <tex>M^k</tex> мы будем обозначать множество всех <tex>k</tex>-элементных подмножеств <tex>M</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=
<tex>1)</tex>Мы будем доказывать теорему по индукции. Начнем со случая <tex>k=2</tex>. Приступая к доказательству для числа <tex>r_m(n_1,n_2)</tex> мы будем считать доказанным утверждение теоремы для чисел Рамсея всех меньших размерностей и чисел Рамсея размерности <tex>m</tex> с меньшей суммой <tex>n_1+n_2</tex>. В качестве базы будем использовать случай чисел Рамсея размерности 2 разобранный выше. Итак, мы докажем, что <tex>r_m(n_1,n_2)-1 \le p=r_{m-1}(r_m(n_1-1,n_2),r_m(n_1,n_2-1))</tex>.
Рассмотрим <tex>(p+1)</tex>-элементное множество <tex>M</tex> и выделим в нём элемент <tex>a</tex>. Пусть <tex>M_0=M</tex>\{<tex>a</tex>}. Пусть <tex>\rho:M^m\rightarrow</tex> {1,2} — произвольная раскраска в два цвета. Рассмотрим раскраску <tex>\rho': M_0^{m-1}\rightarrow</tex> \{1,2\}</tex> , определённую следующим образом: для каждого множества <tex>B \in M_0^{m-1}</tex> пусть <tex>\rho'(В) = \rho(B U</tex>{a}<tex>)</tex>.
Так как <tex>|M_0|=p</tex>, либо существует <tex>r_m(n_1 — 1,n_2)</tex>-элементное подмножество <tex>M_i \subset M_0</tex>, для которого <tex>\rho'(В)=1</tex> на всех <tex>B \in M_1^{m-1}</tex>, либо существует <tex>r_m(n_1,n_2-1)</tex>-элементное подмножество <tex>M_2 \subset M_0</tex>, для которого <tex>\rho'(B)=2</tex> на всех <tex>B \in M_2^{m-1}</tex>. Случаи аналогичны, рассмотрим первый случай и множество <tex>M_1</tex>.
По индукционному предположен из <tex>|M_1|=r_m(n_1-1,n_2)</tex> следует, что либо существует <tex>n_1-1</tex>-элементное подмножество <tex>N_1 \subset M_1</tex>, для которого <tex>\rho(A)=1</tex> на всех <tex>A \in N^m_1</tex>, либо существует <tex>n_2</tex>-элементное подмножество <tex>N_2 \subset M_1</tex>, для которого <tex>\rho(A)=2</tex> на всех <tex>A \in N_2^m</tex>. Во втором случае искомое подмножество найдено (это <tex>N_2</tex>), рассмотрим первый случай и множество <tex>N=N_1 \cup </tex>{<tex>a</tex>}. Пусть <tex>A \in N^m</tex>. Если <tex>A \not\ni a</tex>, то <tex>A \in N_1^m</tex> и следовательно <tex>\rho(A)=1</tex>. Если же <tex>A \ni a</tex>, то множество <tex>A</tex>\{<tex>a</tex>}<tex>\in N_1^{m-1} \subset M_1^{m-1}</tex> и поэтому <tex>\rho(A)=\rho'(A</tex>\{<tex>a</tex>}<tex>)=1</tex>. Учитывая, что <tex>|N|=n_1</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> склеены в цвет <tex>0</tex>. Тогда существует либо таксе такое подмножество <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>
}}
