Антицепь

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

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

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

Определения [ править ]

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

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

Высота и ширина [ править ]

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

Семьи Спернеров [ править ]

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

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

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

Присоединяйтесь и встречайтесь с операциями [ править ]

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

L_{A}=\{x:\exists y\in A{\mbox{ such that }}x\leq y\}.

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

A\vee B=\{x\in A\cup B:\nexists y\in A\cup B{\mbox{ such that }}x<y\}.

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

A\wedge B=\{x\in L_{A}\cap L_{B}:\nexists y\in L_{A}\cap L_{B}{\mbox{ such that }}x<y\}.

Операции соединения и встречи на всех конечных антицепях конечных подмножеств множества

X

определим дистрибутивную решетку , свободную дистрибутивную решетку, порожденную

X.

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

Вычислительная сложность [ править ]

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

Ссылки [ править ]

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

Внешние ссылки [ править ]

[dilworth-1] Дилворт, Роберт П. (1950), «Теорема о разложении частично упорядоченных множеств», Annals of Mathematics , 51 (1): 161–166, doi : 10.2307/1969503 , JSTOR 1969503

[mirsky-2] Мирский, Леон (1971), «Двойственная теорема Дилворта о разложении», American Mathematical Monthly , 78 (8): 876–877, doi : 10.2307/2316481 , JSTOR 2316481

[kahn-3] Кан, Джефф (2002), «Энтропия, независимые множества и антицепи: новый подход к проблеме Дедекинда», Proceedings of the American Mathematical Society , 130 (2): 371–378, doi : 10.1090/S0002-9939-01-06058 -0 , МР 1862115

[birkhoff-4] Биркгоф, Гаррет (1937), «Кольца множеств», Duke Mathematical Journal , 3 (3): 443–454, doi : 10.1215/S0012-7094-37-00334-X

[felragspin-5] Фельснер, Стефан; Рагхаван, Виджай; Спинрад, Джереми (2003), «Алгоритмы распознавания порядков малой ширины и графов малого числа Дилворта» , Order , 20 (4): 351–364 (2004), doi : 10.1023/B:ORDE.0000034609.99940.fb , MR 2079151 , S2CID 1363140

[provball-6] Прован, Дж. Скотт; Болл, Майкл О. (1983), «Сложность подсчета разрезов и вычисления вероятности того, что граф связен», SIAM Journal on Computing , 12 (4): 777–788, doi : 10.1137/0212053 , MR 0721012

[1]

[2]

[3]

[4]

[5]

[6]

v т Это Теория порядка
Topics Glossary Category
Key concepts	Binary relation Boolean algebra Cyclic order Lattice Partial order Preorder Total order Weak ordering
Results	Boolean prime ideal theorem Cantor–Bernstein theorem Cantor's isomorphism theorem Dilworth's theorem Dushnik–Miller theorem Hausdorff maximal principle Knaster–Tarski theorem Kruskal's tree theorem Laver's theorem Mirsky's theorem Szpilrajn extension theorem Zorn's lemma
Properties & Types (list)	Antisymmetric Asymmetric Boolean algebra topics Completeness Connected Covering Dense Directed (Partial) Equivalence Foundational Heyting algebra Homogeneous Idempotent Lattice Bounded Complemented Complete Distributive Join and meet Reflexive Partial order Chain-complete Graded Eulerian Strict Prefix order Preorder Total Semilattice Semiorder Symmetric Total Tolerance Transitive Well-founded Well-quasi-ordering (Better) (Pre) Well-order
Constructions	Composition Converse/Transpose Lexicographic order Linear extension Product order Reflexive closure Series-parallel partial order Star product Symmetric closure Transitive closure
Topology & Orders	Alexandrov topology & Specialization preorder Ordered topological vector space Normal cone Order topology Order topology Topological vector lattice Banach Fréchet Locally convex Normed
Related	Antichain Cofinal Cofinality Comparability Graph Duality Filter Hasse diagram Ideal Net Subnet Order morphism Embedding Isomorphism Order type Ordered field Positive cone of an ordered field Ordered vector space Partially ordered Positive cone of an ordered vector space Riesz space Partially ordered group Positive cone of a partially ordered group Upper set Young's lattice