299
правок
Изменения
→Экстремальные примеры и оценки снизу
|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> имеют интересную числовую природу.
зафиксируем множестес различных помеченных вершин vi,...,vn. Пусть д(п,к) — деля среди всех графсЕ на Еершинах vi,...,vn тех графов, что содержат клику на к вершинах Есегс графсЕ на наших Еершинах счеЕндно 2С« (каждое из возможных С2 можно провести или не провести).
Посчитаем графы с кликой на к Еершинах так: сушествует Ск способов Еыбрать к вершин для клики в нашем множестве, после чегс все рёбра между ними будем считать проведенными, а остальные ребра выбираются произвольным сбразом. Таким сбразом, каждый граф с кликой на к Еершинах будет посчитан причём некоторые даже более одного раза. Количестве графов с кликой сказывается не более, чем С£-2с"_сю Следовательнс,
Предположим, что 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,
