Антицепь

Подмножество несравнимых элементов

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

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

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

Определения

Пусть будет частично упорядоченным множеством. Два элемента и частично упорядоченного множества называются сравнимыми , если Если два элемента несравнимы, они называются несравнимыми; то есть и несравнимы, если ни один из них ${\displaystyle S}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle a\leq b{\text{ or }}b\leq a.}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x\leq y{\text{ nor }}y\leq x.}$

Цепь в — это подмножество , в котором каждая пара элементов сравнима; то есть полностью упорядочена . Антицепь в — это подмножество в , в котором каждая пара различных элементов несравнима; то есть между любыми двумя различными элементами в нет отношения порядка (Однако некоторые авторы используют термин «антицепь» для обозначения сильной антицепи , подмножества, такого, что нет элемента частично упорядоченного множества, меньшего, чем два различных элемента антицепи.) ${\displaystyle S}$ ${\displaystyle C\subseteq S}$ ${\displaystyle C}$ ${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle A.}$

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

Максимальная антицепь — это антицепь, которая не является собственным подмножеством какой-либо другой антицепи. Максимальная антицепь — это антицепь, мощность которой по крайней мере такая же, как у любой другой антицепи. Ширина частично упорядоченного множества — это мощность максимальной антицепи. Любая антицепь может пересекать любую цепь не более чем по одному элементу, поэтому, если мы можем разбить элементы порядка на цепи, то ширина порядка должна быть не более (если антицепь имеет больше элементов, по принципу ящика , то 2 ее элемента будут принадлежать одной и той же цепи, противоречие). Теорема Дилворта утверждает, что эта граница всегда может быть достигнута: всегда существует антицепь и разбиение элементов на цепи, такие, что количество цепей равно количеству элементов в антицепи, которое, следовательно, также должно быть равно ширине. ^[1] Аналогично можно определить высоту частичного порядка как максимальную мощность цепи. Теорема Мирского утверждает, что в любом частичном порядке конечной высоты высота равна наименьшему числу антицепей, на которые может быть разбит порядок. ^[2] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

семьи Шпернер

Антицепь в порядке включения подмножеств множества -элементов известна как семейство Шпернера . Количество различных семейств Шпернера подсчитывается с помощью чисел Дедекинда , ^[3] первые несколько из которых являются ${\displaystyle n}$

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

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

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

Любая антицепь соответствует нижнему множеству. В конечном частичном порядке (или, в более общем случае, частичном порядке, удовлетворяющем условию возрастающей цепи ) все нижние множества имеют эту форму. Объединение любых двух нижних множеств является другим нижним множеством, и операция объединения соответствует, таким образом, операции соединения на антицепях: Аналогично, мы можем определить операцию встречи на антицепях, соответствующую пересечению нижних множеств: Операции соединения и встречи на всех конечных антицепях конечных подмножеств множества определяют дистрибутивную решетку , свободная дистрибутивная решетка, порожденная теоремой Биркгофа о представлении для дистрибутивных решеток, утверждает, что каждая конечная дистрибутивная решетка может быть представлена ​​с помощью операций соединения и встречи на антицепях конечного частичного порядка или, что эквивалентно, как операций объединения и пересечения на нижних множествах частичного порядка. ^[4] ${\displaystyle A}$ $${\displaystyle L_{A}=\{x:\exists y\in A{\mbox{ such that }}x\leq y\}.}$$ $${\displaystyle A\vee B=\{x\in A\cup B:\nexists y\in A\cup B{\mbox{ such that }}x<y\}.}$$ $${\displaystyle A\wedge B=\{x\in L_{A}\cap L_{B}:\nexists y\in L_{A}\cap L_{B}{\mbox{ such that }}x<y\}.}$$ ${\displaystyle X}$ ${\displaystyle X.}$

Сложность вычислений

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

Ссылки

1. Дилворт, Роберт П. (1950), «Теорема разложения для частично упорядоченных множеств», Annals of Mathematics , 51 (1): 161–166, doi :10.2307/1969503, JSTOR  1969503
2. Мирский, Леон (1971), «Двойственная теорема разложения Дилворта», American Mathematical Monthly , 78 (8): 876–877, doi :10.2307/2316481, JSTOR  2316481
3. Кан, Джефф (2002), «Энтропия, независимые множества и антицепи: новый подход к проблеме Дедекинда», Труды Американского математического общества , 130 (2): 371–378, doi : 10.1090/S0002-9939-01-06058-0 , MR  1862115
4. Биркгоф, Гарретт (1937), «Кольца множеств», Duke Mathematical Journal , 3 (3): 443–454, doi :10.1215/S0012-7094-37-00334-X
5. Фелснер, Стефан; Рагхаван, Виджай; Спинрад, Джереми (2003), «Алгоритмы распознавания для порядков малой ширины и графиков малого числа Дилворта», Order , 20 (4): 351–364 (2004), doi :10.1023/B:ORDE.0000034609.99940.fb, MR  2079151, S2CID  1363140
6. Прован, Дж. Скотт; Болл, Майкл О. (1983), «Сложность подсчета разрезов и вычисления вероятности того, что граф связен», SIAM Journal on Computing , 12 (4): 777–788, doi :10.1137/0212053, MR  0721012

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

• Вайсштейн, Эрик В. «Antichain». MathWorld .
• «Антихейн». PlanetMath .