1. Если собрались 6 человек, тройка найдется всегда

Представьте вечеринку, на которую пришли 6 человек. Кто-то знаком уже давно, а кто-то видит друг друга впервые. Не имеет значения, насколько сложной и запутанной может быть структура их знакомств. Тем не менее всегда гарантированно выполнено одно из двух условий:

• Найдутся 3 человека, любые двое из которых знают друг друга.
• Найдутся 3 человека, никакие двое из которых не знают друг друга.

Речь идет не о том, что такая тройка «скорее всего найдется». Как бы ни складывались отношения между людьми, исключений не бывает. Более того, 6 — это минимальное число: для 5 человек можно построить конфигурацию, в которой нет ни той, ни другой тройки.

Это удивительное наблюдение служит дверью в теорию Рамсея. Независимо от того, насколько сложно разбита большая система, при достаточных ее размерах невозможно полностью избежать появления регулярных упорядоченных подструктур. Теория Рамсея изучает именно такую «неизбежную закономерность».

Однако это не означает, что в хаосе спонтанно возникает абсолютно любая структура. Математическое утверждение появляется только тогда, когда четко определены объекты, количество категорий для классификации и искомый паттерн. Начнем с простого и наглядного примера, который можно нарисовать на листе бумаги с помощью 6 точек.

2. Представление отношений отрезками красного и синего цвета

Предположения модели

В рамках этой статьи мы считаем отношение «знакомства» симметричным: если A знает B, то и B знает A. Кроме того, любая пара однозначно относится либо к «знакомым», либо к «незнакомым».

Одностороннее знакомство (когда один человек лишь слышал имя другого) или неопределенные отношения в данной модели исключаются. Кроме того, «не знакомы» не означает «испытывают неприязнь» или «враждуют».

Представим людей точками, а отношения между ними — линиями (ребрами):

Поскольку мы соединяем ребрами каждую пару участников, получается полный граф. Полный граф с $n$ вершинами обозначается через $K_n$, а число его ребер равно:

Для 6 человек это 15 ребер. Тот факт, что «A знает B и C», еще не делает всех троих взаимно знакомыми: ребро между B и C также должно быть красным. Помните об условии: все три стороны треугольника должны быть одного цвета.

В дальнейшем треугольник, все ребра которого красные либо все ребра которого синие, мы будем называть одноцветным (монохроматическим) треугольником. Чтобы диаграммы оставались читаемыми независимо от цветопередачи, на рисунках красный цвет изображается сплошными линиями, а синий — пунктирными.

3. Доказательство: почему для 6 человек тройка найдется всегда

Единственный инструмент, необходимый для доказательства, — это принцип Дирихле. Мы используем предельно простой факт: «если разложить 5 предметов по 2 ящикам, то хотя бы в одном ящике окажется не менее 3 предметов».

Шаг 1: фиксируем одного человека

Выберем любого участника из 6 и назовем его A. Из вершины A к остальным 5 вершинам ведут 5 ребер. Каждое из них окрашено либо в красный, либо в синий цвет, а значит, ребер одного цвета найдется как минимум 3:

Здесь $\lceil x\rceil$ обозначает наименьшее целое число, не меньшее $x$ (округление вверх). Можно рассуждать и от противного: если бы и красных, и синих ребер было не более 2, то всего их набралось бы максимум 4, но у нас их 5.

Предположим, что красных ребер не менее 3, и назовем людей на их концах B, C и D. Тогда ребра A–B, A–C и A–D — красные. (Если бы красных ребер оказалось меньше 3, то нашлось бы не менее 3 синих ребер, и все дальнейшие рассуждения повторились бы с заменой красного цвета на синий).

Шаг 2: рассматриваем ребра между B, C и D

Для трех ребер B–C, B–D и C–D возможны только два случая:

Случай 1: среди них есть хотя бы одно красное ребро. Допустим, ребро B–C красное. Так как A–B и A–C тоже красные, вершины A, B и C образуют красный треугольник. Цвета остальных двух ребер при этом роли не играют.

Случай 2: среди них нет ни одного красного ребра. В этом случае все три ребра B–C, B–D и C–D синие. Тогда синий треугольник образуют вершины B, C и D.

Серые и опущенные на схеме ребра — это те связи, цвет которых не влияет на логику доказательства. В реальном полном графе каждое из них также окрашено в красный или синий цвет.

Таким образом, при любой раскраске одноцветный треугольник неизбежно существует. Нам не потребовалось перебирать все 15 ребер: анализа 5 ребер, выходящих из одной вершины, и связей между тремя ее соседями оказалось достаточно, чтобы охватить абсолютно все возможные варианты. Подробнее об этом см. в университетских учебных материалах.

4. Почему 5 человек недостаточно?

«6 человек достаточно» и «6 — это минимум» — два разных утверждения. Чтобы доказать минимальность, необходимо привести хотя бы один контрпример для 5 человек, в котором условие не выполняется.

Расположим 5 человек в вершинах правильного пятиугольника. Покрасим в красный цвет ребра, соединяющие соседние вершины (то есть 5 внешних сторон пятиугольника). Оставшиеся 5 ребер (диагонали) покрасим в синий цвет.

Если взглянуть только на красные ребра, мы увидим простой цикл длины 5. Какие бы 3 вершины мы ни выбрали, замкнуть треугольник только красными ребрами невозможно. Если взглянуть на синие ребра, получится пятиконечная звезда — однако если перенумеровать вершины по порядку их обхода, мы получим точно такой же цикл длины 5. В синем подграфе треугольников также нет.

Точки пересечения диагоналей в звезде не являются вершинами графа: людям соответствуют только 5 исходных вершин от A до E. Маленькие геометрические треугольники, возникающие при пересечении линий, не учитываются в этой задаче.

Поскольку удалось избежать как красной, так и синей тройки, для 5 человек существование одноцветного треугольника не гарантировано. В сочетании с доказательством для 6 человек это строго устанавливает, что минимальное число участников равно 6.

5. Это «минимальное число» называется числом Рамсея

Минимальное число вершин полного графа, ребра которого окрашены в два цвета (красный и синий), гарантирующее наличие красного подграфа $K_s$ или синего подграфа $K_t$, называется числом Рамсея и обозначается как $R(s,t)$.

Красный $K_s$ означает, что абсолютно все ребра между выбранными $s$ вершинами окрашены в красный цвет. Простого связного пути из красных ребер здесь недостаточно. Поскольку $K_3$ — это треугольник, полученный выше результат можно записать в одну строку:

Теорема Рамсея утверждает, что для любых фиксированных натуральных $s$ и $t$ такое конечное число существует. Однако утверждение «существует» отнюдь не означает «легко вычисляется». Доказательство для треугольников было коротким, но при увеличении размера искомых одноцветных клик сложность нахождения чисел Рамсея растет лавинообразно.

Для чисел Рамсея существует классическая рекуррентная верхняя оценка:

Обозначим правую часть неравенства через $N$ и зафиксируем одну вершину в полном графе на $N$ вершинах. Если из нее выходит не менее $R(s-1,t)$ красных ребер, то среди смежных с ней вершин по красному цвету обязательно найдется либо красный $K_{s-1}$, либо синий $K_t$. В первом случае, добавив к нему исходную вершину, мы получаем красный $K_s$. Во втором случае синий $K_t$ уже найден.

Если же красных ребер меньше этого количества, то синих ребер будет не менее $R(s,t-1)$. Тогда точно такое же рассуждение проводится для синего цвета. Этот вывод — прямое обобщение идеи «выбрать одну вершину и сгруппировать смежные с ней вершины по цвету ребра».

Отталкиваясь от граничных значений $R(2,t)=t$ и $R(s,2)=s$, с помощью данного неравенства можно последовательно строить конечные верхние оценки. Однако, поскольку это неравенство, полученные значения вовсе не обязательно являются точным минимумом. Важно различать «размер, гарантирующий результат» и «действительно необходимое минимальное число».

6. «Почти наверняка» и «без единого исключения» — не одно и то же

В качестве мысленного эксперимента представим, что каждое ребро окрашивается независимо от других в красный или синий цвет с вероятностью $1/2$. Для строгого доказательства вероятностная модель не требуется, но она помогает осознать качественную разницу между вероятностью и гарантией.

Если вершины помечены именами A, B, C…, общее количество возможных раскрасок графа выражается формулой:

При этом раскраски, переходящие друг в друга при повороте или перестановке вершин, считаются различными. Для 6 человек число вариантов составляет $2^{15}=32768$. Проанализировав все раскраски для графов от 3 до 6 вершин, получаем следующие данные:

Даже при 5 людях случайная раскраска порождает одноцветный треугольник примерно в 98,83% случаев. Проведя пару случайных испытаний, легко поддаться иллюзии, будто «для 5 человек треугольник есть всегда». Однако из 1024 возможных раскрасок ровно 12 являются строгими контрпримерами. Между очень высокой вероятностью и полным отсутствием контрпримеров лежит непреодолимая математическая грань.

В таблице приведены доли для независимой равновероятной раскраски ребер. Разумеется, в реальности знакомства между людьми не возникают случайно с вероятностью 50/50. Но прелесть теоремы для 6 человек состоит как раз в том, что она вообще не зависит от вероятностей и работает при любой, сколь угодно специфической структуре отношений.

Сколько треугольников находится в среднем?

Любые фиксированные 3 вершины соединены 3 ребрами, для которых существует $2^3 = 8$ способов раскраски. Из них ровно 2 варианта (все ребра красные или все ребра синие) дают одноцветный треугольник, то есть вероятность составляет $2/8 = 1/4$. Если обозначить общее число одноцветных треугольников через $T$, то в силу линейности математического ожидания получаем:

Для 6 человек математическое ожидание равно ровно 5 треугольникам. Хотя треугольники могут делить между собой ребра и их появления не являются независимыми событиями, для сложения математических ожиданий независимость не требуется.

Однако положительное среднее вовсе не гарантирует наличия хотя бы одного треугольника во всех случаях без исключения: для 5 человек среднее равно 2,5, но существуют контрпримеры с 0 треугольников. Разделение понятий «среднего» и «наихудшего случая» — еще один важный урок теории Рамсея.

7. Проверка всех 32 768 вариантов на Python

Следующий код работает исключительно на стандартной библиотеке Python. Мы кодируем красный цвет как 0, а синий как 1, сопоставляя цвет каждого ребра биту в двоичном числе. Затем мы перебираем все тройки вершин и проверяем, окрашены ли три соединяющих их ребра в один и тот же цвет.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

from itertools import combinations

def check_all(n):
    edges = list(combinations(range(n), 2))
    edge_index = {edge: i for i, edge in enumerate(edges)}
    triples = [
        [edge_index[e] for e in combinations(vertices, 2)]
        for vertices in combinations(range(n), 3)
    ]
    total = 1 << len(edges)
    without_triangle = 0
    minimum = len(triples)

    for coloring in range(total):
        count = 0
        for i, j, k in triples:
            if ((coloring >> i) & 1) == ((coloring >> j) & 1) == ((coloring >> k) & 1):
                count += 1
        without_triangle += (count == 0)
        minimum = min(minimum, count)

    return total, without_triangle, minimum

for n in range(3, 7):
    total, missing, minimum = check_all(n)
    print(f"{n} чел.: всего {total} раскрасок, без треугольников {missing}, минимум {minimum}")

1
2
3
4

3 чел.: всего 8 раскрасок, без треугольников 6, минимум 0
4 чел.: всего 64 раскраски, без треугольников 18, минимум 0
5 чел.: всего 1024 раскраски, без треугольников 12, минимум 0
6 чел.: всего 32768 раскрасок, без треугольников 0, минимум 2

Тот факт, что для 6 человек находится «как минимум 2» одноцветных треугольника, дает даже более сильное утверждение, чем наше начальное доказательство. Действительно, обозначим для каждой вершины $v$ число инцидентных ей красных ребер через $r_v$, а синих — через $b_v$. Тогда $r_v+b_v=5$, откуда следует $r_vb_v\leq6$ (максимум достигается при $2\times 3 = 6$).

В неодноцветном треугольнике есть ровно две вершины, в которых сходятся одно красное и одно синее ребро. Подсчитав по всем вершинам число пар «одно красное и одно синее ребро», мы учтем каждый неодноцветный треугольник ровно дважды. Поскольку всего треугольников $\binom{6}{3} = 20$, число одноцветных треугольников выражается формулой:

Более того, если разбить 6 вершин на две группы по 3 вершины, окрасить все ребра внутри групп в красный цвет, а все ребра между группами — в синий, мы получим ровно два красных треугольника и ни одного синего. Таким образом, минимальное значение 2 абсолютно точно.

Полный перебор эффективен для небольшого числа вершин, однако общее количество раскрасок растет как $2^{n(n-1)/2}$. С увеличением $n$ алгоритм мгновенно сталкивается с комбинаторным взрывом, поэтому вычисления ограничены диапазоном от 3 до 6. Исходный код графиков и подробные распределения доступны в скрипте воспроизведения и файле результатов в формате JSON.

8. Применение 1: Полная связность или полная изоляция в сетях

Заменим понятие «знакомство» понятием «прямое соединение между узлами». Представьте 6 сетевых устройств, где любая пара либо имеет прямое физическое соединение, либо не имеет. Если соединение ненаправленное (симметричное), наша теорема применима без каких-либо изменений.

Это означает, что среди них гарантированно найдется либо тройка устройств, где любые два соединены напрямую, либо тройка, где никакие два не имеют прямой связи между собой. В теории графов первое называется кликой размера 3, а второе — независимым множеством размера 3. Обратите внимание: «отсутствие прямого соединения» не означает невозможность передачи данных транзитом через другие узлы сети.

Такой взгляд применим и при планировании задач с попарной совместимостью или несовместимостью, а также при проверке архитектуры небольших сетей. Если проектировщик ставит условие «избежать как троек полностью совместимых задач, так и троек полностью несовместимых задач», то при наличии 6 задач математика заранее показывает, что выполнить такое требование невозможно — еще до начала какого-либо поиска.

Впрочем, теорема не позволяет выбрать, какая именно из двух структур появится. Вам может требоваться тройка совместимых задач, но конфигурация предоставит лишь тройку несовместимых. Кроме того, попарная совместимость не гарантирует одновременную совместимость всех трех элементов при дефиците общих ресурсов. Теорема гарантирует структуру исключительно на уровне заданных бинарных отношений.

9. Применение 2: Поиск монотонных подпоследовательностей в произвольном числовом ряду

Рассмотрим последовательность из 6 различных чисел. Для любых двух позиций $i$ и $j$, где $i < j$, соединим их красным ребром, если $a_i < a_j$, и синим ребром, если $a_i > a_j$.

Это в точности двухцветная раскраска полного графа с 6 вершинами. Следовательно, в ней обязательно существует одноцветный треугольник. Обозначим индексы его вершин в порядке возрастания: $i < j < k$. Если треугольник красный, то:

Если треугольник синий, то:

Другими словами, сохраняя исходный порядок следования элементов, всегда можно выделить либо возрастающую, либо убывающую подпоследовательность длины 3. Элементы не обязаны идти подряд: последовательность, полученная вычеркиванием части элементов без изменения порядка оставшихся, называется подпоследовательностью.

На приведенной диаграмме из последовательности $4,1,5,2,6,3$ при выборе 2-го, 4-го и 6-го элементов получается подпоследовательность $1,2,3$. Числа не сортировались по возрастанию — они взяты строго в том порядке, в котором встречались в исходном ряду.

Эта концепция тесно связана с поиском регулярных структур в потоках данных. Однако наличие возрастающей тройки не служит доказательством общего восходящего тренда во всем временном ряду: если локальная регулярность неизбежно возникает в абсолютно любых данных, сам факт ее наличия нельзя трактовать как содержательную статистическую аномалию.

Стоит отметить, что для задачи о монотонных подпоследовательностях 6 элементов — не минимальная граница: на самом деле монотонная подпоследовательность длины 3 гарантирована уже для любых 5 различных чисел. Это частный случай знаменитой теоремы Эрдёша — Секереша о монотонных подпоследовательностях. Поскольку раскраска, порожденная отношением порядка чисел, подчиняется свойству транзитивности, на таких графах достигаются более сильные оценки, чем на произвольных раскрасках (см. лекционные материалы по монотонным подпоследовательностям).

10. Заключение: даже в хаосе есть неизбежные закономерности

Сведя отношения 6 человек к красным и синим ребрам и рассмотрев всего лишь 5 ребер, выходящих из одной вершины, мы доказали, что одноцветный треугольник существует всегда. А поскольку пятиугольник дает контрпример для 5 человек, число Рамсея в точности равно $R(3,3)=6$.

Главные выводы, которые стоит запомнить:

• «Гарантировано» не тождественно «высокой вероятности при случайном выборе». При 5 участниках вероятность составляет 98,83%, но контрпримеры существуют; при 6 участниках не остается ни единого контрпримера.
• Существование локального порядка не объясняет поведение системы в целом. Наличие одноцветного треугольника или монотонной подпоследовательности само по себе не говорит об общих свойствах группы или о причинно-следственных связях.
• Математическая гарантия требует четких рамок. Необходимо точно формулировать условия: симметричны ли отношения, разделены ли все пары строго на два класса и какую именно структуру мы ищем.

Красота теории Рамсея заключается не в том, что сложная система упрощается. Система может оставаться сколь угодно хаотичной и запутанной, но полностью уничтожить в ней локальные островки идеального порядка невозможно. И эту глубокую математическую истину можно наглядно проверить всего несколькими линиями на листе бумаги.

Литература и источники

• Университет штата Огайо (Ohio State University), Ramsey Theory: разбор двухцветных раскрасок ребер и малых чисел Рамсея.
• Юваль Вигдерсон (Yuval Wigderson), PCMI 2025, Extremal graph theory and Ramsey theory: Lecture 10: лекционные заметки о методах теории Рамсея и монотонных подпоследовательностях.

Графики, сводные таблицы полного перебора, а также расчеты распределений вероятностей и количеств в этой статье получены с помощью прилагаемого скрипта на Python.