442
правки
Изменения
→Оценки снизу
<tex>g(n,k)<\dfrac{2^{k^2/2}\cdot 2^{-C^2_k}}{k!}=\dfrac{2^{k/2}}{k!}<\dfrac12</tex> при <tex>k \geqslant 3</tex>
Предположим, что <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, \overline G \rangle</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>, ни цвета <tex>2</tex>, получили противоречие. Значит <tex>n</tex> было выбрано неверно. Из этого следует <tex>r(k,k) \geqslant 2^{k/2}</tex>.
}}
