Математика · объяснение и практика

Теорема Шпернера: сколько подмножеств могут не содержать друг друга

Доказываем взвешенную оценку через полные цепи и перестановки, получаем центральный биномиальный предел и отличаем необходимое неравенство от критерия несравнимости.

Синяя и оранжевая половины складываются в целый круг.

В теме Доказательства и комбинаторные модели · Учебная карта

Главная мысль

Семейство различных подмножеств n-элементного множества называется антицепью, если никакое из них не включено в другое. Его размер не превосходит C(n,⌊n/2⌋). Граница достигается всеми подмножествами одного среднего размера; доказательство использует то, что полная цепь содержит не больше одного элемента антицепи.

Несравнимость не означает непересечение

Множества {1,2} и {2,3} пересекаются, но ни одно не содержит другого. Они могут одновременно входить в антицепь. Пустое множество, наоборот, включено в каждое, поэтому антицепь с ним не может содержать другой объект. Аналогично полное исходное множество несовместимо в антицепи с любым другим его подмножеством.

Все разные подмножества одного размера образуют антицепь: строгое включение уменьшило бы число элементов. Выбрав средний размер, получаем C(n,⌊n/2⌋) объектов. Это доказывает достижимость предложенной границы, но ещё не её универсальность. Семейство может смешивать размеры, и простой подсчёт только одного слоя не запрещает ему оказаться больше. Для запрета нужна оценка, одновременно охватывающая все размеры.

Полная цепь соответствует порядку добавления элементов

Зафиксируем перестановку исходных n элементов. Последовательно добавляя их, получим цепь из пустого множества, одного элемента, двух и так далее до полного множества. Всего таких цепей n!, поскольку по цепи однозначно восстанавливается, какой элемент добавился на каждом шаге. В одной цепи все множества сравнимы, поэтому антицепь пересекает её не более чем в одном месте.

Посчитаем пары «множество A из семейства, полная цепь через A». Если |A|=k, первые k добавлений должны быть элементами A в любом порядке, а остальные — дополнением также в любом порядке. Поэтому через A проходят k!(n−k)! цепей. Суммирование по семейству не превосходит n!, так как ни одна цепь не может дать две пары. После деления получается сумма 1/C(n,|A|) по всем A не больше единицы.

Пример

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

Центральный коэффициент C(6,3)=20. По теореме антицепь больше 20 невозможна. Все двадцать трёхэлементных подмножеств подходят: разные множества одной мощности не могут включаться друг в друга. Поэтому 20 — точный максимум. Число всех подмножеств 64 не подходит, поскольку в полном семействе есть многочисленные включения, в том числе через пустое множество.

Центральный коэффициент превращает взвешенный бюджет в обычный

Биномиальные коэффициенты максимальны в середине строки: отношение C(n,k+1)/C(n,k)=(n−k)/(k+1) показывает рост до середины и убывание после неё. Пусть M — центральный максимум. Тогда каждое слагаемое 1/C(n,|A|) не меньше 1/M. Если элементов семейства больше M, взвешенная сумма превысит единицу. Значит, размер антицепи не больше M, как и требовалось.

Обратное заключение из взвешенного неравенства неверно. Семейство {1} и {1,2} при n=4 имеет бюджет 1/4+1/6≤1, но первое множество включено во второе. Неравенство необходимо для антицепи, а не проверяет каждую пару. Также семейство, которое нельзя расширить без нарушения, не обязательно самое большое: одинокое пустое множество уже нерасширяемо, но при n≥2 средний слой больше. В задаче важно различать максимальность по включению и наибольшую численность.

От чтения к действию

А теперь — вы

На множестве из шести элементов хотят выбрать восемь различных двухэлементных и десять различных трёхэлементных подмножеств без включений между любыми двумя. Может ли существовать такая антицепь?

Частые вопросы

Антицепь запрещает общие элементы?

Нет. Она запрещает включение одного множества в другое. Непустое пересечение само по себе не нарушает условие.

Бюджет не больше единицы доказывает антицепь?

Нет. Это необходимое следствие, а не обратный критерий. Нужно ещё проверить отсутствие включений между конкретными множествами.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться