Антицепь - Antichain

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

Размер самой большой антицепи в частично упорядоченном наборе известен как ее ширина . По теореме Дилворта это также равно минимальному количеству цепочек (полностью упорядоченных подмножеств), на которые можно разбить множество. Соответственно, высота частично упорядоченного множества (длина его самой длинной цепи) равна по теореме Мирского минимальному количеству антицепей, на которые это множество может быть разбито.

Семейство всех антицепей в конечном частично упорядоченном множестве может быть снабжено операциями соединения и соединения , превращая их в дистрибутивную решетку . Для частично упорядоченной системы всех подмножеств конечного множества, упорядоченной по включению множества, антицепи называются семействами Спернера, а их решетка представляет собой свободную дистрибутивную решетку с дедекиндовым числом элементов. В более общем смысле подсчет количества антицепей конечного частично упорядоченного множества является # P-полным .

Определения

Позвольте быть частично упорядоченным набором. Два элемента и частично упорядоченного множества называются сопоставимыми, если если два элемента не сопоставимы, они называются несравнимыми; то есть и несравнимы, если ни

Цепочка в - это подмножество, в котором каждая пара элементов сопоставима; то есть, это вполне упорядочено . Антицепь в это подмножество из , в котором каждая пара различных элементов несравнима; то есть нет отношения порядка между любыми двумя разными элементами в (Однако некоторые авторы используют термин "антицепь" для обозначения сильной антицепи , подмножества, такого, что нет элемента посета, меньшего, чем два отдельных элемента антицепи. )

Высота и ширина

Максимальный антицепь является антицепью , который не является собственным подмножеством любого другого антицепи. Максимум антицепь является антицепью , что имеет мощность по меньшей мере столь же велико , как и любую другую антицепи. Шириной частично упорядоченное множество является мощностью максимальной антицепи. Любой антицепь может пересекать любую цепь в более чем один элемент, поэтому, если мы можем разделить элементы на заказ в цепи , то ширина порядка должна быть не более (если антицепь имеет более элементов, по принципу Дирихле , есть было бы 2 его элемента, принадлежащих одной цепи, противоречие). Теорема Дилворта утверждает, что эта граница всегда может быть достигнута: всегда существует антицепь и разделение элементов на цепочки, так что количество цепочек равно количеству элементов в антицепи, которое, следовательно, также должно быть равно ширине. Точно так же можно определить высоту частичного порядка как максимальную мощность цепи. Теорема Мирского утверждает, что в любом частичном порядке конечной высоты высота равна наименьшему количеству антицепей, на которые может быть разделен порядок.

Семьи Спернер

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

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

Даже у пустого набора есть две антицепи в своем наборе мощности: одна содержит единственный набор (собственно пустой набор), а другая не содержит наборов.

Присоединяйтесь и знакомьтесь с операциями

Любая антицепь соответствует нижнему набору

В конечном частичном порядке (или, в более общем смысле, частичном порядке, удовлетворяющем условию возрастающей цепи ) все нижние множества имеют эту форму. Объединение любых двух нижних множеств является еще одним нижним множеством, и операция объединения соответствует, таким образом, операции соединения антицепей:
Точно так же мы можем определить операцию встречи на антицепях, соответствующую пересечению нижних множеств:
Операции соединения и пересечения на всех конечных антицепях конечных подмножеств множества определяют дистрибутивную решетку , а свободная дистрибутивная решетка, порожденная теоремой Биркгофа о представлении дистрибутивных решеток, утверждает, что каждая конечная дистрибутивная решетка может быть представлена ​​через операции соединения и встречи на антицепях некоторого множества. конечный частичный порядок, или, что то же самое, операции объединения и пересечения нижних множеств частичного порядка.

Вычислительная сложность

Максимальную антицепь (и ее размер, ширину данного частично упорядоченного набора) можно найти за полиномиальное время . Подсчет количества антицепей в данном частично упорядоченном наборе является # P-полным .

использованная литература

внешние ссылки