442
правки
Изменения
→Источники информации
{{Определение
|id=def1
|definition='''Клика''' (англ. ''clique'') в [[Основные определения теории графов#Неориентированные графы|неориентированном графе ]] <tex>G(V, E)</tex> {{---}} подмножество [[Основные определения теории графов#Неориентированные графы|вершин ]] <tex>C \subseteq V</tex>, такое что для любых двух различных вершин в <tex>C</tex> существует [[Основные определения теории графов#def_edge_und|ребро]], их соединяющее. Другими словами, клика графа <tex>G(V, E)</tex> {{---}} [[Основные определения теории графов#defFullGraph|полный ]] подграф графа <tex>G(V, E)</tex>. }}
{{Определение
|id=def2
|proof=
}}
{{Утверждение|id=u1|about=1|statement=Для натуральных чисел <tex>m,n</tex> выполняется равенство <tex>r(n,m) \leqslant C_{n+m-2}^{n-1}</tex>
===Оценки снизу===
{{Теорема|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> мы получаем
}}
Заметим, что числа Рамсея размерности <tex>2</tex> — это определённые ранее числа Рамсея для клик.
{{Теорема
|statement=Пусть <tex>m,k,n_1,\ldots,n_k</tex> {{---}} натуральные числа, причем <tex>k \geqslant 2</tex>, а <tex>n_1,\ldots ,n_k \geqslant m</tex>. Тогда существует число Рамсея <tex>r_m(n_1,\ldots n_k)</tex>.
|proof=
}}
|id=def8
|definition=
Пусть <tex>H_1,H_2</tex> — графы. '''Число Рамсея''' <tex>r(H_1,H_2)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в два цвета обязательно найдется подграф, [[Основные определения теории графов#isomorphic_graphs|изоморфный ]] <tex>H_1</tex> с рёбрами цвета <tex>1</tex> или подграф изоморфный <tex>H_2</tex> с рёбрами цвета <tex>2</tex>.
}}
Существует и другое определение чисел Рамсея для произвольных графов.
{{Лемма
|id=l1|about=1|statement=Пусть <tex>m>1</tex>, а граф <tex>H</tex> таков, что <tex>v(H) \geqslant (m-1)(n-1)+1</tex> и <tex>\alpha(H) \leqslant m-1</tex>, где <tex>v(H)</tex> {{---}} количество вершин в графе <tex>H</tex>. Тогда граф <tex>H</tex> содержит в качестве подграфа любое [[Основные определения теории графов#defTree|дерево ]] на <tex>n</tex> вершинах.
|proof=
Зафиксируем <tex>m</tex> и проведем индукцию по <tex>n</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://www.combinatorics.org/ojs/index.php/eljc/article/view/DS1| Small Ramsey Numbers by Stanisław Radziszowski]
[[Категория:Дискретная математика и алгоритмы]]