В комбинаторике , семейство шпернеровых (или система шпернеровых , названная в честь Эммануила шпернеровых ), или беспорядок , это семейство F подмножеств конечного множества Е , в котором ни один из наборов не содержит другой. Эквивалентно, семейство шпернеровых является антицепью в включении решетки над набором мощности в E . Семейство Спернеров также иногда называют независимой системой или неизбыточным множеством .
Семьи Спернера подсчитываются по числам Дедекинда , а их размер ограничен теоремой Спернера и неравенством Любелла – Ямамото – Мешалкина . Они также могут быть описаны на языке гиперграфов, а не семейств множеств, где они называются беспорядками .
Числа Дедекинда
Количество различных семейств Спернера на множестве из n элементов подсчитывается числами Дедекинда , первые несколько из которых равны
- 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (последовательность A000372 в OEIS ).
Хотя точные асимптотические оценки известны для больших значений n , неизвестно, существует ли точная формула, которая может использоваться для эффективного вычисления этих чисел.
Совокупность всех семейств Спернера на множестве из n элементов может быть организована как свободная дистрибутивная решетка , в которой соединение двух семейств Спернера получается из объединения двух семейств путем удаления множеств, которые являются надмножеством другого множества в союз.
Границы размера семьи Спернер
Теорема Спернера
В K -элементные подмножества в п - элементного множества образуют семейство шпернеровых, размер которого достигает максимума , когда к = п / 2 (или ближайшее целое с ним). Теорема Спернера утверждает, что эти семейства являются наибольшими возможными семействами Спернера над n -элементным множеством. Формально теорема утверждает, что для любого семейства Спернера S над n -элементным множеством
LYM неравенство
Неравенство Lubell-Ямамото-Мешалкин обеспечивает другое ограничение на размере семьи шпернеровых, и может быть использовано для доказательства теоремы Шпернера. Она утверждает , что, если к обозначает число наборов размера к в семье шпернеровых на множестве п элементов, то
Беспорядок
Загромождали представляет собой семейство подмножеств конечного множества таким образом, что ни один не содержит какой - либо другой; то есть это семья Спернер. Разница в типичных вопросах. Беспорядки - важная структура при изучении комбинаторной оптимизации.
(На более сложном языке беспорядок - это гиперграф с добавленным свойством, которое в любое время а также (т.е. никакое ребро не содержит другого. Понятие, противоположное беспорядку, - это абстрактный симплициальный комплекс , где каждое подмножество ребра содержится в гиперграфе; это идеал порядка в ч.у. подмножеств V. )
Если является помехой, то блокирующим элементом H , обозначаемым, - беспорядок с множеством вершин V и множеством ребер, состоящим из всех минимальных множеств чтобы для каждого . Можно показать, что( Edmonds & Fulkerson 1970 ), поэтому блокаторы дают нам вид двойственности. Мы определяембыть размером наибольшего набора непересекающихся ребер в H и быть размером наименьшего края в . Легко увидеть, что.
Примеры
- Если G - простой граф без петель, то беспорядок (если ребра рассматриваются как неупорядоченные пары вершин) и - это совокупность всех минимальных покрытий вершин . Здесь это размер наибольшего совпадения и - размер наименьшего вершинного покрытия. Кёнига теорема утверждает , что для двудольных графов ,. Однако для других графиков эти две величины могут отличаться.
- Пусть G - граф и пусть. Совокупность H всех наборов ребер s - t путей является беспорядком и- это совокупность всех минимальных краевых разрезов, разделяющих s и t . В таком случае- максимальное количество непересекающихся ребер s - t путей, и- это размер наименьшего края, разделяющего s и t , поэтому теорема Менгера (версия связности ребер) утверждает, что.
- Пусть G - связный граф, а H - беспорядок насостоящее из всех наборов края остовных деревьев G . потомэто совокупность всех минимальных краевых сечений в G .
Несовершеннолетние
Есть второстепенное отношение к беспорядкам, которое похоже на второстепенное отношение на графах. Если беспорядок и , тогда мы можем удалить v, чтобы убрать беспорядок с множеством вершин и набор ребер, состоящий из всех которые не содержат v . Мы заключаем контракт с v, чтобы убрать беспорядок. Эти две операции коммутируют, и если J еще один беспорядок, мы говорим , что J является минор из Н , если загромождали изоморфно J может быть получен из Н последовательностью удалений и сокращений.
Рекомендации
- Андерсон, Ян (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 етек endlichen Менг" (PDF) , Mathematische Zeitschrift (на немецком языке ), 27 (1): 544-548, DOI : 10.1007 / BF01171114 , JFM 54.0090.06.