Изменения

{{Теорема|id=ter2|about=2, Теорема Эрдеша

<tex>g(n,k) \leqslant \dfrac{C^k_n\cdot 2^{C^2_n-C^2_k}}{2^{C^2_n}}=\dfrac{n!}{(n-k)!\cdot k! \cdot 2^{C^2_k}}=\dfrac{(n-k+1)\cdot(n-k+2)\cdot\ldots \cdot(n-1)\cdot n}{ k! \cdot 2^{C^2_k}}<\dfrac{n^k}{k!\cdot 2^{C^2_k}}</tex> <tex>(*)</tex>

<tex>1)</tex> # Мы будем доказывать теорему по индукции. Начнем со случая <tex>k=2</tex>. Приступая к доказательству для числа <tex>r_m(n_1,n_2)</tex> мы будем считать доказанным утверждение теоремы для чисел Рамсея всех меньших размерностей и чисел Рамсея размерности <tex>m</tex> с меньшей суммой <tex>n_1+n_2</tex>. В качестве базы будем использовать случай чисел Рамсея размерности <tex>2</tex> разобранный выше. Итак, мы докажем, что <tex>r_m(n_1,n_2)-1 \leqslant p=r_{m-1}(r_m(n_1-1,n_2),r_m(n_1,n_2-1))</tex>.<br> Для каждого множества <tex>M</tex> через <tex>M^k</tex> обозначим множество всех <tex>k</tex>-элементных подмножеств <tex>M</tex>.<br> Рассмотрим <tex>(p+1)</tex>-элементное множество <tex>M</tex> и выделим в нём элемент <tex>a</tex>. Пусть <tex>M_0=M \setminus \{ a \}</tex>. Пусть <tex>\rho:M^m\rightarrow \{1, 2 \} </tex> — произвольная раскраска в два цвета. Рассмотрим раскраску <tex>\rho': M_0^{m-1} \rightarrow \{1, 2\} </tex> , определённую следующим образом: для каждого множества <tex>B \in M_0^{m-1}</tex> пусть <tex>\rho'(B) = \rho(B \cup \{ a \})</tex>.<br> Так как <tex>|M_0|=p</tex>, либо существует <tex>r_m(n_1 — 1,n_2)</tex>-элементное подмножество <tex>M_i \subset M_0</tex>, <tex>\rho'(B)=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>.<br> По индукционному предположен из <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 \{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 \setminus \{a\} \in N_1^{m-1} \subset M_1^{m-1}</tex> и поэтому <tex>\rho(A)=\rho'(A \setminus \{a \})=1</tex>. Учитывая, что <tex>|N|=n_1</tex>, мы нашли искомое подмножество и в этом случае. <tex>2)</tex> # При <tex>k>2</tex> будем вести индукцию по <tex>k</tex> с доказанной выше базой <tex>k=2</tex>. При <tex>k>2</tex> мы докажем неравенство.<tex>r_m(n_1,\ldots ,n_k) \leqslant q=r_m(r_m(n_1,\ldots ,n_{k-1}),n_k)</tex> . <br> Для этого мы рассмотрим множество <tex>M</tex> на <tex>q</tex> вершинах и произвольную раскраску <tex>\rho:M^m \rightarrow [1 \ldots k]</tex> в <tex>k</tex>цветов. Рассмотрим раскраску <tex>\rho':M^m \rightarrow \{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(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>, таким образом неравенство доказано, а из этого следует и существование числа Рамсея <tex>r_m(n_1,\ldots ,n_k)</tex>.

|author=5, Теорема Хватала