7. Графы. Числа Рамсея. Верхняя и нижняя оценки чисел Рамсея (Лекции)

Лекция 7. Графы. Числа Рамсея. Верхняя инижняя оценки чисел Рамсея.Лектор — д.ф.-м.н. Селезнева Светлана НиколаевнаЛекции по «Дискретным моделям».Магистратура, 1-й курс,факультет ВМК МГУ имени М.В. ЛомоносоваЛекции на сайте http://mk.cs.msu.suЧисла РамсеяВерхняя оценкаНижняя оценкаЧисла РамсеяГраф Ḡ = (V , Ē ) — дополнительный к графу G = (V , E ),если Ē состоит из всех тех ребер, которых нет в E , т.е.Ē = {(v , w ) | v , w ∈ V , v 6= w , (v , w ) ∈/ E }.Число R(m, n) — такое наименьшее число x, что для любогографа G с x вершинами:либо в G есть подграф Km ,либо в Ḡ есть подграф Kn .ЗадачиЧисла РамсеяВерхняя оценкаНижняя оценкаЧисла РамсеяРаскраска ребер графа G = (V , E ) в два цвета —отображение ρ : E → {1, 2}.Число R(m, n) — такое наименьшее число x, что при любойраскраске ребер полного графа Kx в два цветалибо в нем найдется подграф Km с ребрами цвета 1,либо в нем найдется подграф Kn с ребрами цвета 2.ЗадачиЧисла РамсеяВерхняя оценкаНижняя оценкаЗадачиВерхняя оценка числа РамсеяВерны равенства: R(1, n) = R(m, 1) = 1 и R(m, n) = R(n, m).Теорема 1.

При m, n ≥ 2 справедливо неравенствоR(m, n) ≤ R(m − 1, n) + R(m, n − 1).Доказательство.Положим x = R(m − 1, n) + R(m, n − 1).Рассмотрим произвольную раскраску ребер полного графа Kx вцвета 1 и 2.Из произвольной вершины v графа Kx исходитлибо R(m − 1, n) ребер цвета 1,либо R(m, n − 1) ребер цвета 2.Случаи аналогичны, рассмотрим один из них.Числа РамсеяВерхняя оценкаНижняя оценкаЗадачиВерхняя оценка числа РамсеяДоказательство.1. Пусть из вершины v графа Kx исходит R(m − 1, n) реберцвета 1.Положим V — множество из y = R(m − 1, n) концов этих ребер.Множество V вместе с соединяющими их ребрами образуютполный подграф Ky графа Kx .По определению числа R(m − 1, n) в графе Ky найдется либополный подграф Kn с ребрами цвета 2, либо полный подграфKm−1 с ребрами цвета 1.В первом случае этот полный подграф Kn с ребрами цвета 2есть и в графе Kx .Во втором случае добавим к этому полному подграфу Km−1вершину v и получим полный подграф Km с ребрами цвета 1 вграфе Kx .Числа РамсеяВерхняя оценкаНижняя оценкаЗадачиВерхняя оценка числа РамсеяСледствие 1.

При m, n ≥ 1 справедливо неравенствоm−1R(m, n) ≤ Cm+n−1.Доказательство: индукция по m.Базис индукции m = 1 верен.Индуктивный переход: по теореме 1 получаемR(m − 1, n) ≤ R(m − 1, n) + R(m, n − 1) ≤m−2m−1m−1≤ Cm+n−2+ Cm+n−2= Cm+n−1.Числа РамсеяВерхняя оценкаНижняя оценкаЗадачиНижняя оценка числа РамсеяТеорема 2 (Эрдеша). При k ≥ 2 справедливо неравенствоR(k, k) ≥ 2k/2 .Доказательство. Рассмотрим k ≥ 3, т.к. R(2, 2) = 2.Оценим долю γ(p, k) графов с p помеченными вершинами, вкоторых найдется полный подграф с k вершинами.Возможных ребер в графах с p вершинами ровно Cp2 , откуда2графов с p вершинами в точности 2Cp .Выбрать k вершин, образующих полный подграф, из p вершинможно Cpk способами.Оставшиеся Cp2 − Ck2 ребра могут быть проведены произвольно.Поэтому число графов с p вершинами, содержащих полный22подграф с k вершинами, не более Cpk · 2Cp −Ck .Числа РамсеяВерхняя оценкаНижняя оценкаНижняя оценка числа РамсеяДоказательство.

Значит,2γ(p, k) ≤2Cpk · 2Cp −CkCp22=pk2k!2Ck.При p < 2k/2 получаем2γ(p, k) <2k/212k /2=<.2k!2k!2k /2−k/2ЗадачиЧисла РамсеяВерхняя оценкаНижняя оценкаЗадачиНижняя оценка числа РамсеяДоказательство.Разобьем все графы с p вершинами на пары (G , Ḡ ).Тогда по доказанному выше при p < 2k/2 в этом разбиениинайдется такая пара графов (G , Ḡ ), что ни G , ни Ḡ несодержат полный подграф с k вершинами.Отсюда R(k, k) ≥ 2k/2 .Числа РамсеяВерхняя оценкаНижняя оценкаНижняя оценка числа РамсеяСледствие 2. При m, n ≥ 2 справедливо неравенствоR(m, n) ≥ 2min(m,n)/2 .ЗадачиЧисла РамсеяВерхняя оценкаЗадачи1. Найти значение числа Рамсея:1)2)3)4)R(2, 2);R(2, 3);R(2, 4);R(2, 5).Ответ обосновать.2. Обосновать, что:1) R(3, 3) > 5;2) R(3, 4) > 8.Нижняя оценкаЗадачиЧисла РамсеяВерхняя оценкаНижняя оценкаКонец лекции 7Задачи.