Jump to content

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

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

Примеры [ править ]

  1. Если G — простой граф без петель, то является беспорядком (если ребра рассматриваются как неупорядоченные пары вершин) и представляет собой совокупность всех минимальных вершинных покрытий . Здесь размер наибольшего совпадения и — размер наименьшего вершинного покрытия. Теорема Кенига утверждает, что для двудольных графов . Однако для других графиков эти две величины могут отличаться.
  2. Пусть G — граф и пусть . Коллекция H всех наборов ребер путей s - t представляет собой беспорядок и представляет собой совокупность всех минимальных реберных разрезов, разделяющих s и t . В этом случае - максимальное количество непересекающихся по ребрам путей s - t , и - это размер наименьшего разреза ребра, разделяющего s и t , поэтому теорема Менгера (версия связности ребер) утверждает, что .
  3. Пусть 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 .
Arc.Ask3.Ru: конец переведенного документа.
Arc.Ask3.Ru
Номер скриншота №: 76544773d6b419c2550e8e465083d22e__1661568540
URL1:https://arc.ask3.ru/arc/aa/76/2e/76544773d6b419c2550e8e465083d22e.html
Заголовок, (Title) документа по адресу, URL1:
Sperner family - Wikipedia
Данный printscreen веб страницы (снимок веб страницы, скриншот веб страницы), визуально-программная копия документа расположенного по адресу URL1 и сохраненная в файл, имеет: квалифицированную, усовершенствованную (подтверждены: метки времени, валидность сертификата), открепленную ЭЦП (приложена к данному файлу), что может быть использовано для подтверждения содержания и факта существования документа в этот момент времени. Права на данный скриншот принадлежат администрации Ask3.ru, использование в качестве доказательства только с письменного разрешения правообладателя скриншота. Администрация Ask3.ru не несет ответственности за информацию размещенную на данном скриншоте. Права на прочие зарегистрированные элементы любого права, изображенные на снимках принадлежат их владельцам. Качество перевода предоставляется как есть. Любые претензии, иски не могут быть предъявлены. Если вы не согласны с любым пунктом перечисленным выше, вы не можете использовать данный сайт и информация размещенную на нем (сайте/странице), немедленно покиньте данный сайт. В случае нарушения любого пункта перечисленного выше, штраф 55! (Пятьдесят пять факториал, Денежную единицу (имеющую самостоятельную стоимость) можете выбрать самостоятельно, выплаичвается товарами в течение 7 дней с момента нарушения.)