Изменения

Перейти к: навигация, поиск

Теория Рамсея

11 байт добавлено, 02:46, 7 января 2014
Экстремальные примеры и оценки снизу
Посчитаем графы с кликой на <tex>k</tex> вершинах так: существует <tex>C^k_n</tex> способов выбрать <tex>k</tex> вершин для клики в нашем множестве, после чего все рёбра между ними будем считать проведенными, а остальные ребра выбираются произвольным образом. Таким образом, каждый граф с кликой на <tex>k</tex> вершинах будет посчитан причём некоторые даже более одного раза. Количестве графов с кликой оказывается не более, чем <tex>C^k_n*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!*2^{C^2_k}}</tex> '''*'''
Подставив <tex>n<2^{k/2}</tex> в неравенство '''* ''' мы получаем
<tex>g(n,k)<\frac{2^{k^2/2}*2^{-C^2_k}}{k!}=\frac{2^{k/2}}{k!}<\frac12</tex> при <tex>k \ge 3</tex>
Предположим, что <tex>r(k,k)=n<2^{k/2}</tex> и разобьём все графы на n вершинах на пары <tex>G, \overline G</tex> (граф и его дополнение) Так как <tex>g(n,k)<\frac12</tex>, то существует пара, в которой ни <tex>G</tex>, ни <tex>\overline G</tex> не содержат клики на <tex>k</tex> вершинах. Рассмотрим раскраску рёбер <tex>K_n</tex> в два цвета, в которой ребра цвета 1 образуют граф <tex>G</tex>. В такой раскраске нет клики на <tex>k</tex> вершинах ни цвета 1, ни цвета 2, противоречие. Следовательно <tex>r(k,k) \ge 2^{k/2}</tex>.
}}
{{Утверждение|id=ts2u2
|about=2
|statement=Для любых <tex>k,m \in \mathbb N</tex> таких, что <tex>2 \le k \le m</tex>, выполняется неравенство <tex>r(k,m) \ge 2^{k/2}</tex>
299
правок

Навигация