Математика · объяснение и практика
Вероятностный метод: раскраска без одноцветной клики
Считаем ожидаемое число запрещённых полных подграфов и из среднего меньше единицы доказываем существование раскраски без них; не путаем нижнюю границу Рамсея с верхней.

В теме Доказательства и комбинаторные модели · Учебная карта
Главная мысль
Если C(n,k)·2^(1−C(k,2))<1 при k≥2, существует красно-синяя раскраска полного графа на n вершинах без одноцветного полного подграфа размера k. Доказательство выбирает случайные цвета только как средство усреднения: существование конкретной хорошей раскраски следует из целочисленного числа запрещённых подграфов.
Ищем исключение из всеобщего утверждения
Пусть каждая пара разных вершин независимо получает красный или синий цвет с равными вероятностями. Все раскраски образуют конечное пространство. В каждой посчитаем X — число k-элементных наборов, внутри которых все рёбра одного цвета. Хорошая раскраска означает X=0, а не просто малое число красных рёбер.
Для фиксированного набора имеется C(k,2) внутренних рёбер. Вероятность того, что они все красные, равна 2^(−C(k,2)); для синего цвета столько же. Эти два события несовместимы при k≥2, поэтому вероятность одноцветности равна 2^(1−C(k,2)). Рёбра к внешним вершинам на это событие не влияют.
Различные k-наборы могут пересекаться и иметь общие рёбра. Их одноцветность не нужно объявлять независимой. Независимость отдельных рёбер нужна для вероятности одного набора, тогда как суммирование ожиданий работает и для зависимых индикаторов.
Среднее меньше единицы заставляет один результат быть нулём
Запишем X как сумму индикаторов всех C(n,k) наборов. По линейности E[X]=C(n,k)·2^(1−C(k,2)). Если бы каждая раскраска содержала хотя бы один запрещённый подграф, целочисленная X была бы не меньше единицы во всех исходах, а значит, и её среднее было бы не меньше единицы.
Противоречие при E[X]<1 доказывает существование исхода с X=0. Не утверждается, что у каждой или у большинства раскрасок результат нулевой. Можно дополнительно получить P(X=0)≥1−E[X] через неравенство для объединения, но самого положительного шанса уже достаточно для существования.
Целочисленность существенна: положительная величина, всегда равная половине, тоже имеет среднее меньше единицы, но нигде не равна нулю. Здесь X действительно считает конечное число наборов, поэтому между нулём и первым положительным значением нет промежуточных результатов.
Пример
Покажите вероятностным методом, что на одиннадцати вершинах можно избежать одноцветного полного подграфа на пяти вершинах.
У пяти вершин десять внутренних рёбер. Вероятность одноцветности равна 2/1024=1/512. Наборов из пяти среди одиннадцати C(11,5)=462. Поэтому E[X]=462/512=231/256<1. Существует раскраска без одноцветного K₅, откуда R(5,5)>11. Это учебная доказанная граница данного метода, а не претензия на лучший известный результат.
Как направлен вывод и что значит неудача оценки
Найденная раскраска на n вершинах показывает R(k,k)>n: порога, при котором одноцветная клика неизбежна для любой раскраски, ещё не достигли. Это нижняя граница числа Рамсея. Доказательство не выписывает цвета всех рёбер и потому не является явной конструкцией, хотя логически устанавливает существование.
Если вычисленное среднее оказалось не меньше единицы, этот довод молчит о наличии нулевого результата. Возможны распределения счётчика с нулём и без него при одинаковом большом среднем. Нельзя превращать неуспех достаточного условия в доказательство невозможности хорошей раскраски.
При q равновероятных цветах тот же расчёт даёт вероятность q^(1−C(k,2)) для одного набора. Сначала выбирается общий цвет, затем все рёбра должны получить его. Не следует умножать число наборов на вероятность одного заранее названного цвета, забывая остальные разрешённые цвета.
От чтения к действию
А теперь — вы
Частые вопросы
Нужно ли независимо выбирать одноцветность разных наборов?
Нет. Эти события определяются общими рёбрами и могут зависеть. Для сложения их индикаторов достаточно линейности ожидания.
Среднее меньше единицы означает нулевое X в каждом опыте?
Нет. Оно гарантирует хотя бы одну раскраску с нулём; другие раскраски могут содержать запрещённые подграфы.
Источники и работа с материалом
Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.
Продолжить разбираться
Почему математические ожидания складываются даже без независимости
Складываем ожидаемые значения зависимых величин, используем индикаторы для подсчёта событий и отделяем линейность суммы от правил для произведений и дисперсий.
Открыть темуКогда принцип ящиков гарантирует совпадение
Доказываем неизбежное совпадение при распределении объектов по группам, отличаем гарантированный минимум от вероятности и проверяем достаточное количество.
Открыть тему