442
правки
Изменения
→Оценки снизу
Посчитаем графы с кликой на <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 \frac{C^k_n}{2^{C^2_k}}<\frac{n^k}{k!\cdot 2^{C^2_k}}</tex> '''<tex>(*''')</tex>
Подставив <tex>n<2^{k/2}</tex> в неравенство '''<tex>(*''' )</tex> мы получаем
<tex>g(n,k)<\frac{2^{k^2/2}\cdot 2^{-C^2_k}}{k!}=\frac{2^{k/2}}{k!}<\frac12</tex> при <tex>k \ge 3</tex>
