Введение
В комбинаторике семейство Спернера (или система Спернера; названо в честь Эммануэля Спернера), или клатер, — это семейство F подмножеств конечного множества E, в котором ни одно из множеств не является подмножеством другого. Эквивалентно, семейство Спернера представляет собой антицепь в решетке инклюзии над булеаном (или набором мощностей) E. Семейство Спернера также иногда называют независимой системой или не избыточным множеством. Семейства Спернера пересчитываются числами Дедекинда, а их размер ограничен теоремой Спернера и неравенством Любелла — Ямамото — Мешалкина. Их также можно описать на языке гиперграфов, а не семейств множеств, где они называются клатерами.
Теорема Спернера
Подмножества k элементов множества из n элементов образуют семейство Спернера, размер которого достигается максимального значения при k = n/2 (или ближайшем к нему целом числе). Теорема Спернера утверждает, что эти семейства являются самыми большими возможными семействами Спернера над множеством из n элементов. Формально, теорема гласит, что для любого семейства Спернера S над множеством из n элементов,
Непорядок
Беспорядок — это семейство подмножеств конечного множества, такое что ни одно из них не содержится в другом; другими словами, это семейство Спернера. Отличие заключается в типах вопросов, которые обычно задаются. Беспорядки являются важной структурой при изучении комбинаторной оптимизации. (В более строгой формулировке, беспорядок — это гиперграф с дополнительным свойством, заключающимся в том, что для любых двух его ребер и ни одно из них не является подмножеством другого. Понятие, противоположное беспорядку, — абстрактный симплициальный комплекс, в котором каждое подмножество ребра содержится в гиперграфе; это идеальный порядок в частично упорядоченном множестве подмножеств V.)
Если — беспорядок, то блокировщик , обозначаемый , — это беспорядок с множеством вершин V и множеством ребер, состоящим из всех минимальных множеств таких, что для каждого . Можно показать, что , следовательно, блокировщики обеспечивают своего рода двойственность. Определим как размер наибольшего множества непересекающихся ребер в H, а — как размер наименьшего ребра в . Легко видеть, что .
Примеры
Если G – простой граф без петель, то это антисистема (если ребра рассматриваются как неупорядоченные пары вершин), а – множество всех минимальных вершинных покрытий. Здесь – размер наибольшего сопоставления, а – размер наименьшего вершинного покрытия. Теорема Кёнига утверждает, что для двудольных графов, однако для других графов эти две величины могут различаться. Пусть G – граф и пусть – множество всех наборов ребер s-t путей. Это антисистема, а – множество всех минимальных разрезов по ребрам, разделяющих s и t. В этом случае – максимальное количество непересекающихся по ребрам s-t путей, а – размер наименьшего разреза по ребрам, разделяющего s и t, поэтому теорема Менгера (версия связности по ребрам) утверждает, что . Пусть G – связный граф и пусть H – антисистема на , состоящая из всех наборов ребер остовных деревьев G. Тогда – множество всех минимальных разрезов по ребрам в G.
Несовершеннолетние
Существует минорное отношение на клаттерах, аналогичное минорному отношению на графах. Если H – клаттер и v ∈ V(H), то мы можем удалить вершину v, чтобы получить клаттер H\v с множеством вершин V(H)\{v} и множеством ребер, состоящим из всех ребер из E(H), не содержащих v. Мы стягиваем вершину v, чтобы получить клаттер H/v. Эти две операции коммутируют, и если J – другой клаттер, мы говорим, что J является минором H, если клаттер, изоморфный J, может быть получен из H последовательностью операций удаления и стягивания.