442
правки
Изменения
м
→Оценки снизу
|proof=
Так как <tex>r(2,2)=2</tex>, достаточно рассмотреть случай <tex>k \ge 3</tex>.
Зафиксируем множество различных помеченных вершин <tex>v_i,\ldots,v_n</tex>. Пусть <tex>g(n,k)</tex> — {{---}} доля среди всех графов на вершинах <tex>v_i,\ldots,v_n</tex> тех графов, что содержат клику на <tex>k</tex> вершинах. Всего графов на наших вершинах, очевидно <tex>2^{C^2_n}</tex> (каждое из возможных <tex>C^2_n</tex> можно провести или не провести).
Посчитаем графы с кликой на <tex>k</tex> вершинах такследующим образом: существует <tex>C^k_n</tex> способов выбрать <tex>k</tex> вершин для клики в нашем множестве, после чего все рёбра между ними будем считать проведенными, а остальные ребра выбираются произвольным образомпроизвольно. Таким образом, каждый граф с кликой на <tex>k</tex> вершинах будет посчитан , причём некоторые даже более одного раза. Количестве графов с кликой оказывается не более, чем <tex>C^k_n\cdot 2^{C^2_n-C^2_k}</tex>. Следовательно,
<tex>g(n,k) \le \dfrac{C^k_n}{2^{C^2_k}}<\dfrac{n^k}{k!\cdot 2^{C^2_k}}</tex> <tex>(*)</tex>
<tex>g(n,k)<\dfrac{2^{k^2/2}\cdot 2^{-C^2_k}}{k!}=\dfrac{2^{k/2}}{k!}<\dfrac12</tex> при <tex>k \ge 3</tex>
Предположим, что <tex>r(k,k)=n<2^{k/2}</tex> и разобьём все графы на <tex>n </tex> вершинах на пары <tex>G, \overline G</tex> (граф и его дополнение) Так как <tex>g(n,k)<\dfrac12</tex>, то существует пара, в которой ни <tex>G</tex>, ни <tex>\overline G</tex> не содержат клики на <tex>k</tex> вершинах. Рассмотрим раскраску рёбер <tex>K_n</tex> в два цвета, в которой ребра цвета <tex>1 </tex> образуют граф <tex>G</tex>. В такой раскраске нет клики на <tex>k</tex> вершинах ни цвета <tex>1</tex>, ни цвета 2<tex>1</tex>, получили противоречи противоречие. Следовательно Значит <tex>n</tex> было выбрано неверно. Из этого следует <tex>r(k,k) \ge 2^{k/2}</tex>.
}}
