442
правки
Изменения
→Оценки снизу
|proof=
Так как <tex>r(2,2)=2</tex>, достаточно рассмотреть случай <tex>k \geqslant 3</tex>.
Зафиксируем множество различных помеченных вершин <tex>v_iv_1,\ldots,v_n</tex>. Пусть <tex>g(n,k)</tex> {{---}} доля среди всех графов на вершинах <tex>v_1,\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>. Следовательно,
