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=def2|definition=Графом Рамсея <tex>R(n,m)</tex> назовем такой граф на <tex>r(n,m)-1</tex> вершинах, не содержащий ни клики на <tex>n</tex> вершинах ни независимого множества на <tex>m</tex> вершинах(то есть, граф на ребрах цвета 1 из раскраски в два цвета ребер графа <tex>K_{r(m,n)-1}</tex>, не содержащей ни клики на <tex>n</tex> вершинах с рёбрами цвета 1 ни клики на <tex>m</tex> вершинах с рёбрами цвета 2).}}Граф <tex>R(3,3)</tex> — это цикл на пяти вершинах. Экстремальный граф <tex>R(3,4)</tex> — это цикл на 8 вершинах с проведёнными четырьмя главными диагоналями. Графы <tex>R(3,5)</tex> и <tex>R(4,4)</tex> имеют интересную числовую природу.
{{Теорема|id=ter2|about=2, Теорема Эрдеша|statement=Для любого натурального числа <tex>k \geqslant 2</tex> выполняется неравенство <tex>r(k,k) \geqslant 2^{k/2}</tex>|proof=Так, если ассоциировать 13 вершин графа как <tex>Rr(32,52)=2</tex> с элементами поля вычетов по модулю 13, то рёбра будут соединять вычеты разность которых — кубический вычет по модулю 13 достаточно рассмотреть случай <tex>k \geqslant 3</tex>.Пусть <tex>g(то естьn, 1k)</tex> доля среди помеченных графов на <tex>n</tex> вершинах тех, 5что содержат клику на <tex>k</tex> вершинах. Всего графов на наших вершинах, 8 очевидно <tex>2^{C^2_n}</tex> (каждое из возможных рёбер <tex>C^2_n</tex> можно провести или 12не провести).
Предположим, что <tex>r(k,k)=n<2^{k/2}</tex> и разобьём все графы на <tex>n</tex> вершинах на пары <tex>\langle G, \overline G \rangle</tex>. Так как <tex>g(n,k) <\dfrac12</tex>, то существует пара <tex>\langle G, \le overline G \rangle</tex>, в которой ни <tex>G</tex>, ни <tex>\frac{C^k_n}{overline G</tex> не содержат подграфа на <tex>k</tex> вершинах. Рассмотрим раскраску рёбер <tex>K_n</tex> в два цвета, в которой ребра цвета <tex>1</tex> образуют граф <tex>G</tex>. В такой раскраске нет клики на <tex>k</tex> вершинах ни цвета <tex>1</tex>, ни цвета <tex>2^{C^2_k}}<\frac{/tex>, получили противоречие. Значит <tex>n^</tex> было выбрано неверно. Из этого следует <tex>r(k}{,k!*) \geqslant 2^{C^2_k}k/2}</tex>.}}
===Значения чисел Рамсея===Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, их известно довольно мало. Далее приведена таблица Станислава Радзишевского, в которой присутствуют практически все известные числа Рамсея или же промежутки, в которых они находятся.<center>{| class="wikitable" align="center" style="color: blue; background-color:#ffffcc;" cellpadding="10"|+!colspan="11"|Числа Рамсея|-align="center"! width="6%" |<font color="black"><tex>g(n,k)\ m<\frac{2^{k^/tex></font>! width="6%" |<font color="black"><tex>1 </tex></font>! width="6%" |<font color="black"><tex>2</tex></font>! width="6%" |<font color="black"><tex>3 </tex></font>! width="6%" |<font color="black"><tex>4 </tex></font>! width="6%" |<font color="black"><tex>5 </tex></font>! width="6%" |<font color="black"><tex>6 </tex></font>! width="6%" |<font color="black"><tex>7 </tex></font>! width="6%" |<font color="black"><tex>8 </tex></font>! width="6%" |<font color="black"><tex>9 </tex></font>! width="6%" |<font color="black"><tex>10</tex></font>|-align="center"! <font color="black"><tex>1 </tex></font>| <tex>1 </tex>| <tex>1 </tex>| <tex>1 </tex>| <tex>1 </tex>| <tex>1 </tex>| <tex>1 </tex>| <tex>1 </tex>| <tex>1 </tex>| <tex>1 </tex>| <tex>1 </2}*2^{tex>|-C^2_k}}{kalign="center"!}<font color=\frac{"black"><tex>2^{k</tex></font>| <tex>1 </tex>| <tex>2}}{k</tex>| <tex>3 </tex>| <tex>4 </tex>| <tex>5 </tex>| <tex>6 </tex>| <tex>7 </tex>| <tex>8 </tex>| <tex>9 </tex>| <tex>10</tex>|-align="center"!}<\frac12font color="black"><tex>3</tex></font>| <tex>1</tex> при | <tex>k \ge 3</tex>| <tex>6</tex>| <tex>9</tex>| <tex>14</tex>| <tex>18</tex>| <tex>23</tex>| <tex>28</tex>| <tex>36</tex>| <tex>[40, 42]</tex>|-align="center"! <font color="black"><tex>4</tex></font>| <tex>1</tex>| <tex>4</tex>| <tex>9</tex>| <tex>18</tex>| <tex>25</tex>| <tex>[36, 41]</tex>| <tex>[49, 61]</tex>| <tex>[59, 84]</tex>| <tex>[73, 115]</tex>| <tex>[92, 149]</tex>|-align="center"! <font color="black"><tex>5</tex></font>| <tex>1</tex>| <tex>5</tex>| <tex>14</tex>| <tex>25</tex>| <tex>[43, 48]</tex>| <tex>[58, 87]</tex>| <tex>[80, 143]</tex>| <tex>[101, 216]</tex>| <tex>[133, 316]</tex>| <tex>[149, 442]</tex>|-align="center"! <font color="black"><tex>6</tex></font>| <tex>1</tex>| <tex>6</tex>| <tex>18</tex>| <tex>[36, 41]</tex>| <tex>[58, 87]</tex>| <tex>[102, 165]</tex>| <tex>[115, 298]</tex>| <tex>[134, 495]</tex>| <tex>[183, 780]</tex>| <tex>[204, 1171]</tex>|-align="center"! <font color="black"><tex>7</tex></font>| <tex>1</tex>| <tex>7</tex>| <tex>23</tex>| <tex>[49, 61]</tex>| <tex>[80, 143]</tex>| <tex>[115, 298]</tex>| <tex>[205, 540]</tex>| <tex>[217, 1031]</tex>| <tex>[252, 1713]</tex>| <tex>[292, 2826]</tex>|-align="center"! <font color="black"><tex>8</tex></font>| <tex>1</tex>| <tex>8</tex>| <tex>28</tex>| <tex>[56, 84]</tex>| <tex>[101, 216]</tex>| <tex>[127, 495]</tex>| <tex>[217, 1031]</tex>| <tex>[282, 1870]</tex>| <tex>[329, 3583]</tex>| <tex>[343, 6090]</tex>|-align="center"! <font color="black"><tex>9</tex></font>| <tex>1</tex>| <tex>9</tex>| <tex>36</tex>| <tex>[73, 115]</tex>| <tex>[133, 316]</tex>| <tex>[183, 780]</tex>| <tex>[252, 1713]</tex>| <tex>[329, 3583]</tex>| <tex>[565, 6588]</tex>| <tex>[580, 12677]</tex>|-align="center"! <font color="black"><tex>10</tex></font>| <tex>1</tex>| <tex>10</tex>| <tex>[40, 42]</tex>| <tex>[92, 149]</tex>| <tex>[149, 442]</tex>| <tex>[179, 1171]</tex>| <tex>[289, 2826]</tex>| <tex>[343, 6090]</tex>| <tex>[581, 12677]</tex>| <tex>[798, 23556]</tex>|}</center>
}}
==Числа Рамсея больших размерностей=={{УтверждениеОпределение|id=ts2def5|aboutdefinition=Следствие 2|statement=Для любых Пусть <tex>m,k,m n_1,\ldots ,n_k \in \mathbb N</tex> таких, что причём <tex>2 n_1,\le k ldots ,n_k \le geqslant m</tex>. '''Число Рамсея''' <tex>r_m(n_1,\ldots , выполняется неравенство n_k)</tex> — наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>r(k,что при любой раскраске <tex>m) </tex>-элементных подмножеств <tex>x</tex>-элементного множества <tex>M</tex> в <tex>k</tex> цветов для некоторого <tex>i \in [1\ge 2^{ldots k]</tex> обязательно найдётся такое множество <tex>W_i</tex>, что <tex>|W_i|=n_i</tex> и все <tex>m</tex>-элементные подмножества множества <tex>W_i</2}tex> имеют цвет <tex>i</tex>. Число <tex>m</tex> называют '''размерностью''' числа Рамсея <tex>r_m(n_1,\ldots ,n_k)</tex>.
}}
Заметим, что числа Рамсея размерности <tex>2</tex> — это определённые ранее числа Рамсея для клик.
{{Теорема|id=ter4|about=4, Теорема Рамсея для чисел больших размерностей|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=Числа # Мы будем доказывать теорему по индукции. Начнем со случая <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=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=def2 def16
|definition=
Пусть <tex>kH_1,n_1,...,n_k \in \mathbb NH_2</tex>— графы. '''Число Рамсея ''' <tex>r(k;n_1,...H_1,n_kH_2)</tex> — это наименьшее из всех таких чисел <tex>x \in \mathbb N</tex>, что при любой раскраске рёбер полного для любого графа <tex>G</tex> на <tex>x</tex> вершинах либо в <tex>kG</tex> цветов для некоторого найдется подграф изоморфный <tex>i \in [1..k]H_1</tex> обязательно найдётся клика на , либо в <tex>n_i\overline G</tex> вершинах с рёбрами цвета найдется подграф изоморфный <tex>iH_2</tex>.
}}
Несложно показать, что эти определения эквивалентны (аналогично определениям для классических чисел Рамсея). Из результатов классической теории Рамсея становится понятно, что числа <tex>r(H_1,H_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>.
'''База:''' для <tex>n=1</tex> очевидно.
'''Индукционный переход:''' Пусть верно для <tex>n-1</tex>, докажем для <tex>n</tex>. Рассмотрим произвольное дерево <tex>T_n</tex> на <tex>n</tex> вершинах, пусть дерево <tex>T_{{Утверждениеn-1}</tex> получено из <tex>T_n</tex> удалением висячей вершины. Пусть <tex>U</tex> — максимальное независимое множество вершин графа <tex>H</tex>. Тогда <tex>|id=u3U|statement=\alpha(H) \leqslant m-1</tex>, следовательно <tex>v(H-U) \geqslant (m-1)(n-2)+1</tex> и очевидно <tex>\alpha(H-U) \leqslant m-1</tex>.По индукционному предположению, граф <tex>H-U</tex> содержит в качестве подграфа дерево <tex>T_{n-1}</tex>. Пусть <tex>a</tex> — вершина этого дерева, присоединив к которой висячую вершину, мы получим дерево <tex>T_n</tex>. Заметим, что множество <tex>U \cup</tex> <tex>\{a\}</tex> не является независимым ввиду максимальности <tex>U</tex>. Следовательно, вершина <tex>a</tex> смежна хотя бы с одной вершиной <tex>x \in U</tex>. Отметим, что <tex>r(2;x</tex> не принадлежит множеству вершин графа <tex>T_{n-1}</tex> и,m)присоединив вершину <tex>x</tex> к вершине <tex>a</tex> — это определённое ранее число Рамсея дерева <tex>r(T_{n-1}</tex>,m)получим дерево <tex>T_n</tex> в качестве подграфа графа <tex>H</tex>.
}}
{{Теорема
|id=t3. ter5 |statementauthor=Пусть <tex>k5,n_1,...,n_k \ge 2</tex> - натуральные числа. Тогда выполняются следующие утверждения:Теорема Хватала|statement=<tex>1) r(k;n_1,...T_n,n_kK_m) \le r=(k;n_1m-1,n_2,...,n_k)+r(k;n_1,n_2n-1,...,n_k)++r(k;n_11</tex>,n_2,...,n_k-1)-k+2где <tex>T_n</tex>— дерево на <tex>2)r(k;n_1,...,n_k) \le \frac{(n_1+n_2+...+n_k)!}{n_1!*n_2!*...*n_k!}n</tex>вершинах.
|proof=
Сперва докажем, что <tex>r(T_n,K_m) \geqslant (m-1)(n-1)+1</tex>. Для этого предъявим раскраску рёбер графа <tex>K_{(m-1)(n-1)}</tex>, в которой нет ни одного связного подграфа на <tex>n</tex> вершинах с рёбрами цвета <tex>1</tex> и нет клики на <tex>m</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</tex> (то есть, все оставшиеся рёбра) Доказательстве полностью аналогично пункту образуют <tex>(m-1 доказательства )</tex>-дольный граф, в котором, очевидно, нет клики на <tex>m</tex> вершинах.Теперь воспользуемся вторым [[#t1def16|теоремыопределением]]числа Рамсея <tex>r(H_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) \leqslant m-1</tex>. По [[#l1|лемме <tex>1</tex>]], граф <tex> \overline G</tex> содержит в качестве подграфа любое дерево на <tex>n</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>.}}
}}
Доказательство <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][[Категория:Дискретная математика и алгоритмы]][[Категория:Дискретная математика]][[Категория:Теория графов]][[Категория: Раскраски графов]]