Семья Спернер
В комбинаторике семейство Спернера (или система Спернера ; названо в честь Эмануэля Спернера ), или клаттер , — это семейство F подмножеств конечного множества E, в котором ни одно из множеств не содержит другого. Эквивалентно, семейство Спернера представляет собой антицепь в решетке включения над множеством E степеней . Семейство Спернера иногда называют независимой системой или неизбыточным множеством .
Семейства Спернера подсчитываются числами Дедекинда , а их размер ограничен теоремой Спернера и неравенством Любелла–Ямамото–Мешалкина . Их также можно описать на языке гиперграфов, а не на языке семейств множеств, где их называют помехами .
Числа Дедекинда [ править ]
Число различных семейств Спернера на наборе из n элементов подсчитывается числами Дедекинда , первые несколько из которых равны
- 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (последовательность A000372 в OEIS ).
точные асимптотические известны Хотя для больших значений n оценки , неизвестно, существует ли точная формула, которую можно использовать для эффективного вычисления этих чисел.
Совокупность всех семейств Спернера на множестве из n элементов может быть организована как свободная дистрибутивная решетка , в которой соединение двух семейств Спернера получается в результате объединения двух семейств путем удаления множеств, которые являются надмножеством другого множества в союз.
размера Спернеров Границы семьи
Спернера editТеорема
Подмножества k из -элементов набора из n -элементов образуют семейство Спернера, размер которого максимизируется, когда k = n /2 (или ближайшее к нему целое число). Теорема Спернера утверждает, что эти семейства являются максимально возможными семействами Спернера в наборе из n -элементов. Формально теорема утверждает, что для каждого семейства Спернера S над набором из n -элементов
LYM-неравенство [ править ]
Неравенство Любелла -Ямамото-Мешалкина дает еще одну оценку размера семейства Спернера и может быть использовано для доказательства теоремы Спернера. нем говорится, что если k В обозначает количество наборов размера k в семействе Спернера над набором из n элементов, то
Беспорядок [ править ]
Беспорядок — это семейство подмножеств конечного множества, ни одно из которых не содержит другого; то есть это семья Спернеров. Разница заключается в обычно задаваемых вопросах. Беспорядки являются важной структурой при изучении комбинаторной оптимизации.
(Выражаясь более сложным языком, беспорядок – это гиперграф с добавленным свойством, которое в любое время и (т.е. ни одно ребро по существу не содержит другого. Противоположным понятием беспорядка является абстрактный симплициальный комплекс , где каждое подмножество ребра содержится в гиперграфе; это идеал порядка в частично упорядоченном множестве подмножеств V .)
Если является помехой, то H , блокировщик обозначаемый , — это помеха с множеством вершин V и множеством ребер, состоящим из всех минимальных множеств так что для каждого . Можно показать, что ( Эдмондс и Фулкерсон 1970 ), таким образом, блокаторы дают нам своего рода двойственность. Мы определяем быть размером наибольшего набора непересекающихся ребер в H и быть размером наименьшего ребра в . Это легко увидеть .
Примеры [ править ]
- Если G — простой граф без петель, то является беспорядком (если ребра рассматриваются как неупорядоченные пары вершин) и представляет собой совокупность всех минимальных вершинных покрытий . Здесь размер наибольшего совпадения и — размер наименьшего вершинного покрытия. Теорема Кенига утверждает, что для двудольных графов . Однако для других графиков эти две величины могут отличаться.
- Пусть G — граф и пусть . Коллекция H всех наборов ребер путей s - t представляет собой беспорядок и представляет собой совокупность всех минимальных реберных разрезов, разделяющих s и t . В этом случае - максимальное количество непересекающихся по ребрам путей s - t , и - это размер наименьшего разреза ребра, разделяющего s и t , поэтому теорема Менгера (версия связности ребер) утверждает, что .
- Пусть G — связный граф, а H — беспорядок на состоящее из всех рёбер остовных деревьев G . Затем представляет собой совокупность всех минимальных реберных разрезов в G .
Несовершеннолетние [ править ]
Существует второстепенное отношение к беспорядку, похожее на второстепенное отношение к графикам. Если это беспорядок и , тогда мы можем удалить v , чтобы навести беспорядок с набором вершин и множество ребер, состоящее из всех которые не содержат v . Мы заключаем контракт 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 .