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

В комбинаторике семейство Спернера (или система Спернера ; названо в честь Эмануэля Спернера ), или клаттер , — это семейство 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 -элементов

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

LYM-неравенство

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

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

Беспорядок

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

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

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

Примеры

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

Несовершеннолетние

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

Ссылки

Андерсон, Ян (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), «Теорема о подмножествах конечного множества» (PDF) , Mathematical Journal (на немецком языке), 27 (1): 544–548, doi : 10.1007/BF01171114 , JFM 54.0090.06 .