442
правки
Изменения
→Источники информации
==Числа Рамсея==
|proof=
# Докажем с помощью метода математической индукции по <tex>n+m</tex>. <br>'''База:''' <tex>r(n,\;1) = r(1,\;n) = 1</tex>, так как граф, состоящий из одной вершины, можно считать полным графом любого цвета. <br>'''Индукционный переход:''' Пусть <tex>n>1</tex> и <tex>m>1</tex>. Рассмотрим клику на полный чёрно-белый граф из <tex>r(n-1, \;m - 1) + r(n ,\;m- 1, m)</tex> вершинах с рёбрами цветов 1 вершин. Возьмём произвольную вершину <tex>v</tex> и 2 обозначим через <tex>M</tex> и ее произвольную вершину <tex>aN</tex>. Тогда либо от вершины множества вершин, инцидентных <tex>av</tex> отходит хотя бы в чёрном и белом подграфе соответственно. Так как в графе <tex>r(n-1, \;m)+r(n,\;m - 1)=|M|+|N|+1 </tex> рёбер цвета 2 вершин, согласно принципу Дирихле, либо от вершины <tex>a|M|\geqslant r(n-1,\;m)</tex> отходит хотя бы , либо <tex>|N|\geqslant r(n—1n, \;m-1)</tex> рёбер цвета 1. Случаи аналогичны, рассмотрим первый случай и клику на Пусть <tex>|M|\geqslant r(n-1, \;m — 1)</tex> вершинах, соединенных с . Тогда либо в <tex>aM</tex> рёбрами цвета 2. На этих вершинах есть либо клика на существует белый <tex>nK_m</tex> вершинах с ребрами цвета 1, что доказывает теорему, либо клика на в <tex>M</tex> есть чёрный <tex>m—1K_{n-1}</tex> вершинах , который вместе с рёбрами цвета 2. Во втором случае добавим вершину <tex>av</tex> и получим клику на образует чёрный <tex>mK_n</tex> вершинах с рёбрами цвета 2, в этом случае теорема также доказана. Теперь из определения Случай <tex>|N|\geqslant r(n, \;m-1)</tex> следует [[#t1|неравенство]]рассматривается аналогично.2) Рассмотрим клику на # Предположим, <tex>p=r(n-1, \;m-l)+</tex> и <tex>q=r(n,\;m-1, m)</tex> оба чётны. Положим <tex>s=p+q-1</tex> вершинах с рёбрами цветов 1 и 2 и его произвольную вершину рассмотрим чёрно-белый граф из <tex>as</tex>вершин. Если вершине <tex>ad_i</tex> инцидентны хотя бы степень <tex>i</tex>r(n-й вершины в чёрном подграфе, то, согласно [[Лемма о рукопожатиях|лемме о рукопожатиях]],m-<tex> \sum\limits_{i=1)}^s d_i</tex> рёбер цвета 2 или хотя бы — чётно. Поскольку <tex>r(n-1s</tex> нечётно,m)должно существовать чётное <tex>d_i</tex> рёбер цвета 1. Не умаляя общности, положим, то мы найдём в графе клику на что <tex>d_1</tex> чётно. Обозначим через <tex>nM</tex> вершинах с рёбрами цвета 1 или клику на и <tex>mN</tex> вершинах с рёбрами цвета 2. Остаётся лишь случайвершины, когда инцидентные вершине <tex>a1</tex> инцидентны ровно в чёрном и белом подграфах соответственно. Тогда <tex>r(n, m|M|=d_1</tex> и <tex>|N|=s-1)-1d_1</tex> рёбер цвета 2, то же самое для всех остальных вершиноба чётны. Это означаетСогласно принципу Дирихле, что в графе из рёбер цвета 2 всего либо <tex>r(n, m-1)+r(n|M|\geqslant p-1</tex>, m)-1либо <tex>|N|\geqslant q</tex> вершин и степень каждой вершины равна . Так как <tex>|M|</tex>r(nчётно, m-1)а <tex>p-1</tex>. Однаконечётно, тогда в графе нечётное количество вершин нечётной степени. Противоречие показывает нампервое неравенство можно усилить, так что в случае, когда либо <tex>r(n, m-1)|M|\geqslant p</tex> и , либо <tex>r(n-1,m)|N|\geqslant q</tex> — чётные. <br> Далее проводим рассуждения, выполняется неравенство аналогичные тем, что присутствуют в первом пункте теоремы. Таким образом, <tex>r(n, m)<\leqslant r(n, m-1)+r(n-1, m)-1</tex>.
}}
{{Утверждение|id=ts1u1|about=Следствие 1|statement=Для натуральных чисел <tex>m,n</tex> выполняется равенство <tex>r(n,m) \le leqslant C_{n+m-2}^{n-1}</tex>
|proof=
Очевидно, <tex>C^{n-1}_{n+m-2}=1</tex> при <tex>n=1</tex> или <tex>m=1</tex>, как и соответствующие числа Рамсея. Индукцией по <tex>n</tex> и <tex>m</tex> при <tex>n,m \ge geqslant 2</tex> получаем <tex>r(n,m) \le leqslant r(n,m-1)+r(n-1,m) \le leqslant C^{n-1}_{n+m-3}+C^{n-2}_{n+m-3}=C^{n-1}_{n+m-2}</tex>
}}
===Экстремальные примеры и оценки Оценки снизу===Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, этих значении известно немногим больше, чем перечислено выше.{{ОпределениеТеорема|id=def2ter2|about=2, Теорема Эрдеша|definitionstatement=Графом Рамсея Для любого натурального числа <tex>Rk \geqslant 2</tex> выполняется неравенство <tex>r(nk,mk)\geqslant 2^{k/2}</tex> назовем такой граф на |proof=Так как <tex>r(2,2)=2</tex>, достаточно рассмотреть случай <tex>k \geqslant 3</tex>.Пусть <tex>g(n,mk)-1</tex> доля среди помеченных графов на <tex>n</tex> вершинах тех, что содержат клику на <tex>k</tex> вершинах. Всего графов на наших вершинах, очевидно <tex>2^{C^2_n}</tex> (каждое из возможных рёбер <tex>C^2_n</tex> можно провести или не содержащий ни клики провести). Посчитаем графы с кликой на <tex>nk</tex> вершинах ни независимого множества следующим образом: существует <tex>C^k_n</tex> способов выбрать <tex>k</tex> вершин для клики в нашем множестве, после чего все рёбра между ними будем считать проведенными, а остальные ребра выбираются произвольно. Таким образом, каждый граф с кликой на <tex>mk</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>K_g(n,k)<\dfrac{2^{k^2/2}\cdot 2^{-C^2_k}}{k!}=\dfrac{2^{k/2}}{k!}<\dfrac12</tex> при <tex>k \geqslant 3</tex> Предположим, что <tex>r(mk,k)=n<2^{k/2}</tex> и разобьём все графы на <tex>n</tex> вершинах на пары <tex>\langle G, \overline G \rangle</tex>. Так как <tex>g(n,k)-1}<\dfrac12</tex>, то существует пара <tex>\langle G, \overline G \rangle</tex>, в которой ни <tex>G</tex>, ни <tex>\overline G</tex> не содержащей ни клики содержат подграфа на <tex>nk</tex> вершинах с рёбрами . Рассмотрим раскраску рёбер <tex>K_n</tex> в два цвета, в которой ребра цвета <tex>1 ни </tex> образуют граф <tex>G</tex>. В такой раскраске нет клики на <tex>mk</tex> вершинах с рёбрами ни цвета <tex>1</tex>, ни цвета <tex>2</tex>, получили противоречие. Значит <tex>n</tex> было выбрано неверно. Из этого следует <tex>r(k,k)\geqslant 2^{k/2}</tex>.
}}
{{Теорема|id=t2ter3|authorabout=P. Erdos3,Теорема Рамсея для нескольких цветов|statement=Для любого натурального числа <tex>\forall k , n_1, \ldots n_k \ge 2in \mathbb N </tex> существует число Рамсея <tex>r(n_1,\ldots,n_k)</tex> выполняется неравенство , при этом <tex>r(kn_1,\ldots,kn_k) \ge leqslant r(n_1,\ldots, n_{k^-2}, r(n_{k/2-1},\;n_k)).</tex>
|proof=
==Числа Рамсея для произвольных графов==Еще один способ обобщения классической теории Рамсея — замена клик на произвольные графы-шаблоны.{{Определение|id=def8|definition=Пусть <tex>H_1,H_2</tex>g— графы. '''Число Рамсея''' <tex>r(nH_1,kH_2) </tex> — это наименьшее из всех таких чисел <tex>x \le in \frac{C^k_nmathbb N</tex>, что при любой раскраске рёбер полного графа на <tex>x</tex> вершинах в два цвета обязательно найдется подграф, [[Основные определения теории графов#isomorphic_graphs|изоморфный]] <tex>H_1</tex> с рёбрами цвета <tex>1</tex> или подграф изоморфный <tex>H_2</tex> с рёбрами цвета <tex>2</tex>. }}Существует и другое определение чисел Рамсея для произвольных графов.{2^{C^2_k}}Определение|id=def16|definition=Пусть <tex>H_1,H_2</tex> — графы. '''Число Рамсея''' <tex>r(H_1,H_2)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что для любого графа <tex>G</tex> на <tex>x</tex> вершинах либо в <tex>G</tex> найдется подграф изоморфный <tex>H_1</tex>, либо в <tex>\frac{n^k}{k!*2^{C^2_koverline G</tex> найдется подграф изоморфный <tex>H_2</tex>. }}Несложно показать, что эти определения эквивалентны (аналогично определениям для классических чисел Рамсея). Из результатов классической теории Рамсея становится понятно, что числа <tex>r(H_1,H_2)</tex>существуют.
'''База:''' для <tex>g(n,k)<\frac{2^{k^2/2}*2^{-C^2_k}}{k!}=\frac{2^{k/2}}{k!}<\frac12</tex> при <tex>k \ge 31</tex>очевидно.
}}
{{УтверждениеТеорема|id=ts2ter5 |aboutauthor=Следствие 25, Теорема Хватала|statement=<tex>r(T_n,K_m)=(m-1)(n-1)+1</tex>, где <tex>T_n</tex> — дерево на <tex>n</tex> вершинах.|proof=Сперва докажем, что <tex>r(T_n,K_m) \geqslant (m-1)(n-1)+1</tex>. Для любых этого предъявим раскраску рёбер графа <tex>kK_{(m-1)(n-1)}</tex>,в которой нет ни одного связного подграфа на <tex>n</tex> вершинах с рёбрами цвета <tex>1</tex> и нет клики на <tex>m \in N</tex> такихвершинах с рёбрами цвета <tex>2</tex>. Разобьём вершины графа на <tex>m-1</tex> клику по <tex>n-1</tex> вершине и покрасим все рёбра этих клик в цвет <tex>1</tex>. Тогда любой связный подграф с рёбрами цвета <tex>1</tex> содержит не более <tex>n-1</tex> вершины, в частности, нет подграфа с рёбрами цвета <tex>1</tex>, что изоморфного <tex>T_n</tex>. Рёбра цвета <tex>2 \le k \le </tex> (то есть, все оставшиеся рёбра) образуют <tex>(m-1)</tex>-дольный граф, в котором, очевидно, выполняется неравенство нет клики на <tex>m</tex> вершинах.Теперь воспользуемся вторым [[#def16|определением]] числа Рамсея <tex>r(kH_1,H_2)</tex>. Рассмотрим произвольный граф <tex>G</tex> на <tex>{(m-1)(n-1)+1}</tex> вершинах. Предположим, что в графе <tex>G</tex> не существует клики на <tex>m</tex> вершинах. Тогда <tex>m>1</tex> и <tex>\alpha( \overline G) \ge 2^{kleqslant m-1</tex>. По [[#l1|лемме <tex>1</tex>]], граф <tex> \overline G</tex> содержит в качестве подграфа любое дерево на <tex>n</2}tex> вершинах, в частности, дерево, изоморфное <tex>T_n</tex>.
}}
==Индуцированная теорема Рамсея=={{Определение|id=def9|definition=Граф <tex>H</tex> называется '''индуцированным подграфом''' (англ. ''induced subgraph'') графа <tex>G</tex> если две вершины в <tex>H</tex> соединены ребром тогда и только тогда, когда они смежны в <tex>G</tex>. }} {{Определение|id=def10|definition=Пусть <tex>H</tex> — граф. Граф <tex>G</tex> будем называть '''рамсеевским графом''' (англ. ''Ramsey’s graph'') для <tex>H</tex>, если при любой раскраске рёбер графа <tex>G</tex> в два цвета существует одноцветный по рёбрам индуцированный подграф графа <tex>G</tex> изоморфный <tex>H</tex>.}} {{Определение|id=def11|definition='''Индуцированным числом Рамсея''' (англ. ''induced Ramsey’s number'') <tex>r_{ind}(H)</tex> для графа <tex>H</tex> будем называть минимальное число <tex>x \in \mathbb N</tex>, такое что существует рамсеевский граф на <tex>x</tex> вершинах для графа <tex>H</tex>.}}Заметим, что при замене произвольного графа <tex>H</tex> на клику мы получаем частный случай классической теоремы Рамсея. {{Теорема|id=ter6 |about=6, Индуцированная теорема Рамсея|statement=Для любого графа <tex>H</tex> существует рамсеевский граф <tex>G</tex>. }} Доказательство <ref>[https://math.la.asu.edu/~andrzej/teach/mat598/lec8.pdf Induced Ramsey Theorem Proof]</ref> данной теоремы было приведено независимо различными математиками, однако благодаря ему получилось предоставить только очень грубые оценки значений индуцированных чисел Рамсея. В данный момент проблема нахождения сколько-нибудь точных границ индуцированных чисел Рамсея является нерешенной задачей математики. ==Особенности теории==Числа Результаты, полученные в теории Рамсея , обладают двумя главными характеристиками. Во-первых, они не позволяют получить сами структуры: теоремы лишь доказывают, что они существуют, но алгоритма для раскрасок их нахождения не предлагают. Единственным способ найти нужную конструкцию зачастую является перебор. Во-вторых, чтобы искомые структуры существовали, обычно требуется, чтобы объекты, их содержащие, состояли из очень большого числа элементов. Зависимость числа элементов объекта от размера конструкции обычно, как минимум, экспоненциальная. ==См. также==*[[Раскраска графа]]*[[Раскраска двудольного графа в несколько цветовдва цвета]]*[[Теорема Турана об экстремальном графе]] ==Примечания==<references />
==Числа Рамсея больших размерностейИсточники информации ==* [[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][[Категория:Дискретная математика и алгоритмы]]==Индуцированная теорема Рамсея==[[Категория:Дискретная математика]]===Случай двудольного графа===[[Категория:Теория графов]]===Случай произвольного графа===[[Категория: Раскраски графов]]