Antichain

редактировать

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

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

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

Содержание

1 Определения
2 Высота и ширина
3 семейства Спернеров
4 Соединение и выполнять операции
5 Вычислительная сложность
6 Ссылки
7 Внешние ссылки

Определения

Пусть S - частично упорядоченное множество. Два элемента a и b частично упорядоченного набора называются сопоставимым, если a ≤ b или b ≤ a. Если два элемента не сопоставимы, они называются несравнимыми; то есть x и y несравнимы, если ни x ≤ y, ни y ≤ x.

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

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

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

Семейства Спернера

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

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

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

Join и выполнить операции

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

LA = {x ∣ ∃ y ∈ A st x ≤ y}. {\ displaystyle L_ {A} = \ {x \ mid \ exists y \ in A {\ t_dv {st}} x \ leq y \}.}

L_A = \ {x \ mid \ существует y \ в A \ t_dv {s.t. } x \ le y \}.

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

A ∨ B = {x ∈ A ∪ B ∣ ∄ y ∈ A ∪ B st x < y }. {\displaystyle A\vee B=\{x\in A\cup B\mid \nexists y\in A\cup B{\t_dv{ s.t. }}x

{\ displaystyle A \ vee B = \ {x \ in A \ cup B \ mid \ nexists y \ in A \ cup B {\ t_dv {s.t. }} x <y \}.}

Аналогично, мы можем определить операцию meet на антицепях, соответствующую пересечение нижних множеств:

A ∧ B = {x ∈ L A ∩ L B ∣ ∄ y ∈ L A ∩ L B s.t. x < y }. {\displaystyle A\wedge B=\{x\in L_{A}\cap L_{B}\mid \nexists y\in L_{A}\cap L_{B}{\t_dv{ s.t. }}x

{\ displaystyle A \ wedge B = \ {x \ in L_ {A} \ cap L_ {B} \ mid \ nexists y \ in L_ {A} \ cap L_ {B} {\ t_dv {st }} x <y \}.}

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

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

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

Ссылки

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