Математика · объяснение и практика
Числа Рамсея: как соседи одной вершины дают рекурсию
Доказываем R(r,s)≤R(r−1,s)+R(r,s−1), разделяя соседей по цвету ребра; отличаем найденную верхнюю оценку от точного числа.

В теме Доказательства и комбинаторные модели · Учебная карта
Главная мысль
Число R(r,s) — наименьшее N, при котором любая красно-синяя раскраска всех рёбер полного графа на N вершинах содержит красный полный подграф на r вершинах или синий на s. Для r,s≥2 выполняется R(r,s)≤R(r−1,s)+R(r,s−1). Это оценка неизбежной структуры при любой раскраске.
Цвет рёбер не является цветом самих вершин
Полный подграф требует наличия всех рёбер между выбранными вершинами; одноцветный означает одинаковый цвет каждого из этих рёбер. Красные связи от одной центральной вершины к трём соседям ещё не делают самих трёх соседей красным треугольником. Их взаимные рёбра нужно исследовать отдельно.
Для r=1 или s=1 достаточно одной вершины, поэтому R(1,s)=R(r,1)=1. Также R(2,s)=s: если красного ребра нет, все рёбра синие; на s вершинах это синий полный подграф. На s−1 вершинах полностью синяя раскраска ещё не содержит ни красного ребра, ни синего набора размера s.
Существование общего порога не следует из нескольких рисунков. Его устанавливает индукция, сводящая задачу к меньшим размерам требуемых одноцветных подграфов. Именно здесь принцип ящиков работает вместе с информацией о внутренних рёбрах, а не вместо неё.
Разделяем соседей и сохраняем цвет при добавлении
Положим A=R(r−1,s), B=R(r,s−1) и рассмотрим полный граф на A+B вершинах. У выбранной вершины v имеется A+B−1 соседей. Каждого относим в красную или синюю группу по цвету ребра к v. Если обе группы имели бы меньше A и B соответственно, соседей было бы не больше A+B−2. Значит, один порог достигается.
Пусть красных соседей не меньше A. По определению A среди них есть красный подграф размера r−1 или синий размера s. В первом случае добавляем v: все нужные новые рёбра красные. Во втором случае синий подграф уже достаточен, добавлять v к нему не требуется. Для синей группы рассуждение симметрично.
Сведение уменьшает один из параметров, поэтому вместе с граничными случаями доказывает существование конечных R(r,s). Не нужно заранее знать их точные значения: любые уже доказанные достаточные пороги позволяют получить очередную верхнюю оценку.
Пример
Используя R(3,3)≤6 и R(2,4)=4, получите достаточное число вершин для красного треугольника или синего полного подграфа на четырёх вершинах.
Рекурсия даёт R(3,4)≤4+6=10. У вершины графа на десяти вершинах девять соседей: либо хотя бы четыре красных, либо хотя бы шесть синих. Четыре красных соседа содержат красное ребро, которое с центром даёт треугольник, или все их рёбра синие. Среди шести синих соседей есть красный треугольник либо синий треугольник, к которому центр добавляет четвёртую вершину. Это достаточная оценка, а не заявление о точном R(3,4).
Рекурсия даёт гарантию, но не всегда лучший порог
Для треугольников получается R(3,3)≤R(2,3)+R(3,2)=6. Это означает наличие хотя бы одного из двух цветов треугольника при любой раскраске шести вершин. Не утверждается, что каждый участник входит в такой треугольник или что обязательно возникают оба цвета.
Повторяя рекурсию и правило Паскаля, можно получить R(r,s)≤C(r+s−2,r−1). Индукция использует сумму двух соседних коэффициентов, а не тождество самих чисел Рамсея. Если сумма верхних оценок равна десяти, из этого не следует, что меньшие графы никогда не обладают нужным свойством.
Для точного значения нужна ещё нижняя граница: раскраска меньшего графа, избегающая обоих запрещённых подграфов. Доказательство неизбежности и доказательство существования исключения направлены в разные стороны. Подмена одного другим приводит к неверному утверждению о минимальности найденного числа.
От чтения к действию
А теперь — вы
Частые вопросы
Можно ли красить только некоторые рёбра?
В этой формулировке окрашены все пары вершин полного графа. Для неполного графа такая гарантия требует другой задачи.
Почему к готовому синему подграфу среди красных соседей не добавляют центр?
Рёбра к центру красные. Синий подграф уже имеет нужный размер и используется без расширения.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Когда принцип ящиков гарантирует совпадение
Доказываем неизбежное совпадение при распределении объектов по группам, отличаем гарантированный минимум от вероятности и проверяем достаточное количество.
Открыть темуПочему соседние числа треугольника Паскаля складываются
Доказываем правило сложения соседних чисел через разбиение выборок на две непересекающиеся группы и проверяем нумерацию строк треугольника.
Открыть тему