Изменения

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

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

108 байт добавлено, 24 июнь
Источники информации
===Оценки снизу===
{{Теорема|id=ter2|about=2, Теорема Эрдеша
|statement=Для любого натурального числа <tex>k \geqslant 2</tex> выполняется неравенство <tex>r(k,k) \geqslant 2^{k/2}</tex>
|proof=
Посчитаем графы с кликой на <tex>k</tex> вершинах следующим образом: существует <tex>C^k_n</tex> способов выбрать <tex>k</tex> вершин для клики в нашем множестве, после чего все рёбра между ними будем считать проведенными, а остальные ребра выбираются произвольно. Таким образом, каждый граф с кликой на <tex>k</tex> вершинах будет посчитан, причём некоторые даже более одного раза. Количестве графов с кликой оказывается не более, чем <tex>C^k_n\cdot 2^{C^2_n-C^2_k}</tex>. Следовательно,
<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>n<2^{k/2}</tex> в неравенство <tex>(*)</tex> мы получаем
|proof=
# Мы будем доказывать теорему по индукции. Начнем со случая <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>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>.
}}
{{Теорема
|id=ter5
|author=5, Теорема Хватала
|statement=<tex>r(T_n,K_m)=(m-1)(n-1)+1</tex>, где <tex>T_n</tex> — дерево на <tex>n</tex> вершинах.
|proof=
* [[wikipedia:Ramsey's theorem|Wikipedia — Ramsey's theorem]]
* [[wikipedia:Ramsey theory|Wikipedia — Ramsey theory]]
* [http://people.maths.ox.ac.uk/~gouldm/ramsey.pdf Ramsey Theory]
*[https://vtechworks.lib.vt.edu/bitstream/handle/10919/32873/Dickson_JO_T_2011.pdf?sequence=1&isAllowed=y An Introduction to Ramsey Theory on Graphs]
* [http://people.maths.ox.ac.uk/~gouldm/ramsey.pdf Ramsey Theory]
*[http://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1| Small Ramsey Numbers by Stanisław Radziszowski]
[[Категория:Дискретная математика и алгоритмы]]
295
правок

Навигация