Теорема Эрдёша-Ко-Радо: максимум пересекающихся множеств

Теорема Эрдёша-Ко-Радо отвечает на простой с виду вопрос: сколько $k$-элементных подмножеств $n$-элементного множества можно набрать так, чтобы любые два из них пересекались? Кажется, что таких семейств может быть очень много, но экстремальная комбинаторика даёт жёсткий потолок. Если множество достаточно большое ($n \ge 2k$), максимум равен $\binom{n-1}{k-1}$, и достигается он самым прямолинейным способом. Ниже разберём формулировку, идею доказательства и типовые задачи, а калькулятор сразу посчитает границу для ваших $n$ и $k$.

Что утверждает теорема Эрдёша-Ко-Радо

Зафиксируем множество $[n] = \{1, 2, \dots, n\}$ и рассмотрим все его подмножества ровно из $k$ элементов. Семейство $\mathcal{F}$ таких подмножеств называется пересекающимся (intersecting), если любые два множества $A, B \in \mathcal{F}$ имеют общий элемент: $A \cap B \ne \varnothing$.

Теорема Эрдёша-Ко-Радо (1961) гласит: если $n \ge 2k$, то

$$|\mathcal{F}| \le \binom{n-1}{k-1}.$$

То есть пересекающееся семейство $k$-подмножеств не может быть больше, чем число всех $k$-подмножеств, содержащих один фиксированный элемент. Условие $n \ge 2k$ существенно: при $n < 2k$ любые два $k$-подмножества пересекаются автоматически (им просто не хватает места разойтись), и тогда максимум - это вообще все $\binom{n}{k}$ подмножеств.

Рассчитать для своей задачи

Почему граница именно C(n-1, k-1)

Простейший способ построить большое пересекающееся семейство - взять звезду: зафиксировать элемент $x$ (например, $x = 1$) и собрать все $k$-подмножества, которые его содержат. Любые два таких множества заведомо пересекаются - в них обоих есть $x$.

Сколько их? Один элемент уже занят ($x$), остальные $k-1$ выбираются из оставшихся $n-1$ элементов:

$$\binom{n-1}{k-1}.$$

Теорема говорит, что лучше звезды ничего не придумать: при $n \ge 2k$ ни одно пересекающееся семейство не превзойдёт этот размер. Более того, при строгом неравенстве $n > 2k$ звезда - это единственная оптимальная конструкция (с точностью до выбора центра); этот факт называют теоремой о единственности экстремального семейства. Сравнить размер звезды с полным числом подмножеств удобно через биномиальные коэффициенты - отношение $\binom{n-1}{k-1} / \binom{n}{k}$ равно ровно $k/n$.

Граничный случай n = 2k

Отдельного внимания заслуживает ровно $n = 2k$. Здесь $k$-подмножества разбиваются на пары «множество и его дополнение»: для каждого $A$ ровно одно $k$-подмножество $[n] \setminus A$ с ним не пересекается. Всего пар - $\frac{1}{2}\binom{2k}{k}$, и из каждой пары в пересекающееся семейство можно взять не больше одного множества. Значит,

$$|\mathcal{F}| \le \frac{1}{2}\binom{2k}{k} = \binom{2k-1}{k-1} = \binom{n-1}{k-1},$$

и граница та же. Но при $n = 2k$ оптимальных семейств уже много: из каждой пары «множество-дополнение» свободно выбираем любого представителя. Поэтому единственность звезды теряется именно на границе.

Идея доказательства: метод сдвига

Классическое доказательство Эрдёша, Ко и Радо использует сдвиги (compression, shifting). Сдвиг $S_{ij}$ для $i < j$ работает так: в каждом множестве семейства, где есть $j$, но нет $i$, заменяем $j$ на $i$ - если получившееся множество ещё не занято. Ключевые свойства сдвига:

$$\begin{aligned} &|S_{ij}(\mathcal{F})| = |\mathcal{F}| \quad \text{(размер сохраняется),} \\ &S_{ij}(\mathcal{F}) \ \text{остаётся пересекающимся.} \end{aligned}$$

Применяя сдвиги $S_{ij}$ для всех пар, мы «прижимаем» семейство к началу множества, не меняя его мощности и не нарушая пересекаемость. После конечного числа сдвигов семейство становится компрессированным (стабильным), и на такой структуре граница $\binom{n-1}{k-1}$ доказывается прямой индукцией по $n$. Сдвиги не увеличивают размер, поэтому исходное семейство тоже не больше границы.

Рассчитать для своей задачи

Существует и короткое доказательство Катоны (1972) через циклические перестановки: элементы $[n]$ расставляют по кругу, считают, сколько множеств семейства образуют дугу из подряд идущих элементов, и усредняют по всем перестановкам. На каждом цикле таких «дуговых» множеств не больше $k$ при $n \ge 2k$, откуда после усреднения и выходит та же оценка $\binom{n-1}{k-1}$.

Связь с гипотезой и обобщения

Теорема Эрдёша-Ко-Радо - отправная точка для целого направления экстремальной теории множеств. Несколько важных ветвей:

• $t$-пересекающиеся семейства: требуем $|A \cap B| \ge t$. Гипотеза Франкла-Уилсона и теорема Алсведе-Хачатряна описывают точный максимум в этом случае.
• Теорема Хилтона-Милнера: даёт второй по величине размер пересекающегося семейства - наибольшего среди тех, что не являются звездой.
• Аналоги для других структур: подпространства векторных пространств над конечным полем ($q$-аналог), перестановки (пересекающиеся по значению), строки. Везде «звезда вокруг фиксированного объекта» оказывается оптимальной при достаточном размере.

Эти результаты показывают: интуиция «фиксируй общий элемент и набирай всё вокруг него» - не случайность, а глубокий принцип экстремальной комбинаторики.

Частые ошибки

• Забывают условие $n \ge 2k$. Без него формула $\binom{n-1}{k-1}$ не является максимумом: при $n < 2k$ ответ - все $\binom{n}{k}$ подмножеств, потому что они и так попарно пересекаются.
• Путают «пересекающееся» и «попарно непересекающееся». Теорема - про семейства, где любые два множества имеют общий элемент, а не про разбиения на непересекающиеся блоки.
• Считают, что звезда - единственный оптимум всегда. На границе $n = 2k$ оптимальных семейств много (по одному представителю из каждой пары «множество-дополнение»); единственность звезды есть только при $n > 2k$.
• Берут $\binom{n}{k-1}$ вместо $\binom{n-1}{k-1}$. Центр звезды уже зафиксирован, поэтому остальные $k-1$ элементов выбираются из $n-1$, а не из $n$.

FAQ

Чему равен максимум при $n < 2k$? Всем $\binom{n}{k}$ подмножествам. Когда $n < 2k$, два $k$-подмножества не могут быть непересекающимися: их суммарный размер $2k$ превышает $n$, поэтому общий элемент есть всегда. Семейство всех $k$-подмножеств уже пересекающееся, и теорема Эрдёша-Ко-Радо здесь не даёт нетривиального ограничения.

Чем звезда отличается от других оптимальных семейств? Звезда - это все $k$-подмножества, содержащие один фиксированный элемент. При $n > 2k$ только звезда достигает максимума $\binom{n-1}{k-1}$ - это утверждение о единственности. При $n = 2k$ появляются другие оптимальные семейства, не сводящиеся к звезде.

Какое доказательство проще для студента? Доказательство Катоны через циклические перестановки. Оно умещается на половине страницы: расставляем элементы по кругу, показываем, что на каждом цикле дуговых множеств не больше $k$, и усредняем по всем $(n-1)!$ перестановкам. Метод сдвига концептуально важнее, но требует аккуратной возни с операциями компрессии.

Коротко

Теорема Эрдёша-Ко-Радо ограничивает размер пересекающегося семейства $k$-подмножеств $n$-множества: при $n \ge 2k$ оно содержит не более $\binom{n-1}{k-1}$ множеств, и эта граница достигается звездой - всеми подмножествами вокруг одного фиксированного элемента. При $n > 2k$ звезда единственна, при $n = 2k$ оптимумов много, а при $n < 2k$ пересекаются вообще все подмножества. Доказывается сдвигами или коротким усреднением Катоны по циклическим перестановкам.