Задача
COM-B2-M06-P013 Рекурсия Рамсея
Докажите неравенство \(R(s,t)\le R(s-1,t)+R(s,t-1)\) для \(s,t\ge3\).
Выберите вершину и разделите остальные вершины на красных и синих соседей.
Пусть \(N=R(s-1,t)+R(s,t-1)\), и рёбра \(K_N\) покрашены в красный и синий цвета. Выберем вершину \(v\). Остальные \(N-1\) вершин делятся на красных соседей \(v\) и синих соседей \(v\).
Если красных соседей не меньше \(R(s-1,t)\), то внутри них есть либо красный \(K_{s-1}\), либо синий \(K_t\). В первом случае вместе с \(v\) получаем красный \(K_s\), во втором уже есть синий \(K_t\).
Если красных соседей меньше \(R(s-1,t)\), то синих соседей не меньше \(R(s,t-1)\). Тогда внутри них есть либо красный \(K_s\), либо синий \(K_{t-1}\), который вместе с \(v\) даёт синий \(K_t\).
Во всех случаях нужная структура существует.
Это центральная техническая задача модуля.