Семья Шпернер

В комбинаторике семейство Шпернера (или система Шпернера ; названо в честь Эммануэля Шпернера ), или беспорядок , — это семейство F подмножеств конечного множества E, в котором ни одно из множеств не содержит другого. Эквивалентно, семейство Шпернера — это антицепь в решётке включения над множеством мощности E. Семейство Шпернера также иногда называют независимой системой или неизбыточным множеством .

Семейства Шпернера подсчитываются по числам Дедекинда , а их размер ограничен теоремой Шпернера и неравенством Любелла–Ямамото–Мешалкина . Их также можно описать на языке гиперграфов , а не семейств множеств, где они называются клаттерами .

Число различных семейств Шпернера на множестве из n элементов подсчитывается с помощью чисел Дедекинда , первые несколько из которых равны

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (последовательность A000372 в OEIS ).

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

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

Подмножества из k -элементов множества из n -элементов образуют семейство Шпернера, размер которого максимизируется при k = n /2 (или ближайшем к нему целом числе). Теорема Шпернера утверждает, что эти семейства являются наибольшими возможными семействами Шпернера над множеством из n -элементов. Формально теорема утверждает, что для любого семейства Шпернера S над множеством из n -элементов

${\displaystyle |S|\leq {\binom {n}{\lfloor n/2\rfloor }}.}$

Неравенство Любелла –Ямамото–Мешалкина дает еще одну границу размера семейства Шпернера и может быть использовано для доказательства теоремы Шпернера. Оно утверждает, что если a _k обозначает число множеств размера k в семействе Шпернера над множеством из n элементов, то

${\displaystyle \sum _{k=0}^{n}{\frac {a_{k}}{n \choose k}}\leq 1.}$

Загромождение — это семейство подмножеств конечного множества, ни одно из которых не содержит другого; то есть это семейство Шпернера. Разница в вопросах, которые обычно задаются. Загромождения — важная структура в изучении комбинаторной оптимизации.

На более сложном языке, беспорядок — это гиперграф с добавленным свойством, что всякий раз, когда и (т.е. ни одно ребро не содержит другое). Противоположное понятие беспорядок — это абстрактный симплициальный комплекс , где каждое подмножество ребра содержится в гиперграфе; это идеал порядка в частично упорядоченном множестве подмножеств V .${\displaystyle (V,E)}$${\displaystyle A\not \subseteq B}$${\displaystyle A,B\in E}$${\displaystyle A\neq B}$

Если — это перекрытие, то блокировщик H , обозначаемый как , — это перекрытие с множеством вершин V и множеством ребер, состоящим из всех минимальных множеств, так что для каждого . Можно показать, что (Эдмондс и Фулкерсон, 1970 г.), поэтому блокировщики дают нам тип двойственности. Мы определяем как размер наибольшего набора непересекающихся ребер в H и как размер наименьшего ребра в . Легко видеть, что .${\displaystyle H=(V,E)}$${\displaystyle b(H)}$${\displaystyle B\subseteq V}$${\displaystyle B\cap A\neq \varnothing }$${\displaystyle A\in E}$${\displaystyle b(b(H))=H}$${\displaystyle \nu (H)}$${\displaystyle \тау (Н)}$${\displaystyle b(H)}$${\displaystyle \nu (H) \leq \tau (H)}$

1. Если G — простой граф без петель, то — загромождение (если ребра рассматриваются как неупорядоченные пары вершин), а — совокупность всех минимальных вершинных покрытий . Здесь — размер наибольшего паросочетания, а — размер наименьшего вершинного покрытия. Теорема Кёнига утверждает, что для двудольных графов , . Однако для других графов эти две величины могут отличаться.${\displaystyle H=(V(G),E(G))}$${\displaystyle b(H)}$${\displaystyle \nu (H)}$${\displaystyle \тау (Н)}$${\ displaystyle \ nu (H) = \ tau (H)}$
2. Пусть G — граф и пусть . Совокупность H всех наборов ребер путей s - t является беспорядком и представляет собой совокупность всех минимальных разрезов ребер, которые разделяют s и t . В этом случае — максимальное число непересекающихся по ребрам путей s - t , а — размер наименьшего разреза ребер, разделяющего s и t , поэтому теорема Менгера (версия связности ребер) утверждает, что .${\displaystyle s,t\in V(G)}$${\displaystyle b(H)}$${\displaystyle \nu (H)}$${\displaystyle \тау (Н)}$${\ displaystyle \ nu (H) = \ tau (H)}$
3. Пусть G — связный граф, а H — загромождение на, состоящее из всех множеств ребер остовных деревьев графа G. Тогда — это совокупность всех минимальных множеств ребер в графе G.${\displaystyle E(G)}$${\displaystyle b(H)}$

Существует второстепенное отношение на загромождениях, которое похоже на второстепенное отношение на графах. Если — загромождение и , то мы можем удалить v, чтобы получить загромождение с множеством вершин и множеством ребер, состоящих из всех , которые не содержат v . Мы сокращаем v , чтобы получить загромождение . Эти две операции коммутируют, и если J — другой загромождение, мы говорим, что J — минор H , если загромождение, изоморфное J, может быть получено из H последовательностью удалений и сокращений.${\displaystyle H=(V,E)}$${\displaystyle v\in V}$ ${\displaystyle H\setminus v}$${\displaystyle V\setminus \{v\}}$${\displaystyle A\in E}$ ${\displaystyle H/v=b(b(H)\setminus v)}$

• Андерсон, Ян (1987), « Теорема Шпернера», Комбинаторика конечных множеств , Oxford University Press, стр.  2–4.
• Эдмондс, Дж .; Фулкерсон, Д.Р. (1970), «Экстремумы узкого места», Журнал комбинаторной теории , 8 (3): 299–306 , doi : 10.1016/S0021-9800(70)80083-7.
• Кнут, Дональд Э. (2005), «Черновик раздела 7.2.1.6: Генерация всех деревьев», Искусство программирования , т. IV, стр.  17–19.
• Спернер, Эмануэль (1928), «Ein Satz über Untermengen einer endlichen Menge» (PDF) , Mathematische Zeitschrift (на немецком языке), 27 (1): 544–548 , doi : 10.1007/BF01171114, JFM  54.0090.06.