299
правок
Изменения
→Экстремальные примеры и оценки снизу
===Экстремальные примеры и оценки снизу===
Задача нахождения точных значений чисел Рамсея чрезвычайно трудна, этих значении известно немногим больше, чем перечислено выше.
{{Определение|id=def1
|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).
}}
Граф /2(3,3) — зто никл на пяти вершинах Экстремальный граф /2(3,4) — это никл на 8 ьершинах с проведёнными четырьмя главными диагоналями Графы /2(3,5) и /2(4,4) имеют интересную числовую природу,
Так, если асссниирсвать 13 Еершнн графа /2(3,5) с элементами поля вычетоЕ по модулю 13 тс рёбра будут соединять вычеты разнссть которых — кубический Еычет не модулю 13 (то есть, 1. 5, 8 или 11]
Если считать 17 Еершнн графа /2(4,4) элементами поля ЕычетсЕ по модулю 17. то рёбра будут соединять Еычеты, разнссть которых — квадратичный ьычет пс модулю 17 (то есть, 1.2,48,9.13,15 или 11).
Существует гипотеза что любой граф R(k,k) изоморфен своему дополнению (или что е раскраске полного графа на г(к,к) — 1 вершинах
в два цвета граф с рёбрами тега 1 обязательно изсмсрфен графу с рёбрами цЕета 1]. Однако, зто не белее чем краснЕсе предположение, е обоснование которого межно положите лишь нем неги е известные примеры.
Теорема 10.2. (P. Eidos. 1947.) Для любого натурального числа к>2 выполняется неравенство г(к,к) > 2к/2
Доказательство. Так как г(2,2) = 2, достаточно рассмотреть случай к > 3.
зафиксируем множестес различных помеченных вершин vi,...,vn. Пусть д(п,к) — деля среди всех графсЕ на Еершинах vi,...,vn тех графов, что содержат клику на к вершинах Есегс графсЕ на наших Еершинах счеЕндно 2С« (каждое из возможных С2 можно провести или не провести).
Посчитаем графы с кликой на к Еершинах так: сушествует Ск способов Еыбрать к вершин для клики в нашем множестве, после чегс все рёбра между ними будем считать проведенными, а остальные ребра выбираются произвольным сбразом. Таким сбразом, каждый граф с кликой на к Еершинах будет посчитан причём некоторые даже более одного раза. Количестве графов с кликой сказывается не более, чем С£-2с"_сю Следовательнс,
Ск пк
д(п,к) < -£ < —(1С.2s 2С1 к\ -2С1
ПсдстаЕИЕ п < 2fe/2 е неравенстве (1С.2) мы получаем
2fc2/2 . 2-с| 2fc/2 i
д(п, к) < = — < - при к > 3.
Предположим, что r(k,k) = п < 2к12 и разобьём Есе графы на п вершинах на пары G, G (граф и егс дополнение) Так как д(п,к) < \. то существует пара, е которой ни G. ни G не содержат клики на к Еершинах. Рассмотрим раскраску рёбер Кп е два цвета, в которой ребра цвета 1 образуют граф G. В такой раскраске нет клики на к вершинах ни цвета 1, ни нвета 2, прстиЕоречне Следовательнс, г(к,к) > 2к12. □
Следствие 1С.2. Для, любых к,т G N таких, что 2 < к < т. выполняется неравенстве г(к,т) > 2к12
Удивительно, не изЕсетные конструкции не могут ни дать более точную оценку на г(к,к). чем в теореме 10 2, ни дать более точную опенку на г(к,т), чем в следствии 10 2,
===Числа Рамсея для раскрасок в несколько цветов===
