Задача
COM-B2-M06-P011 Значение \(R(2,t)\)
#11
★★★☆☆ Уровень 3 из 5
Докажите, что \(R(2,t)=t\) для любого \(t\ge2\).
Красный \(K_2\) — это просто красное ребро.
Покажем, что \(t\) вершин достаточно. В красно-синей раскраске \(K_t\), если есть красное ребро, то есть красный \(K_2\). Если красных рёбер нет, то все рёбра синие, и все \(t\) вершин образуют синий \(K_t\).
Меньше \(t\) вершин недостаточно: покрасим все рёбра в синий цвет. Тогда красного \(K_2\) нет, а синего \(K_t\) тоже нет, потому что вершин меньше \(t\). Значит, \(R(2,t)=t\).
Нужная маленькая база для рекурсии Рамсея.