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

Sperner family

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

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

Числа Дедекинда

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

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

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

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

Границы размера семьи Спернер

Теорема Спернера

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

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

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

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

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

Беспорядок

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

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

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

Примеры

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

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

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

Navigation