Введение
Подмножество несравнимых элементов
В математике, в области теории порядка, антицепочка — это подмножество частично упорядоченного множества, такое что любые два различных элемента в этом подмножестве несравнимы. Размер наибольшей антицепочки в частично упорядоченном множестве называется его шириной. По теореме Дилворта, это также равно минимальному числу цепей (полностью упорядоченных подмножеств), на которые можно разбить множество. Двойственно, высота частично упорядоченного множества (длина его самой длинной цепи) равна, согласно теореме Мирского, минимальному числу антицепочек, на которые можно разбить множество. Семейству всех антицепочек в конечном частично упорядоченном множестве можно задать операции объединения и пересечения, превращая её в дистрибутивную решётку. Для частично упорядоченной системы всех подмножеств конечного множества, упорядоченной по включению, антицепочки называются семействами Спернера, а их решётка является свободной дистрибутивной решёткой с числом элементов Дедекинда. В более общем случае, вычисление количества антицепочек конечного частично упорядоченного множества является задачей класса #P-полных задач.
In mathematics, in the area of order theory, an antichain is a subset of a partially ordered set such that any two distinct elements in the subset are incomparable. The size of the largest antichain in a partially ordered set is known as its width. By Dilworth's theorem, this also equals the minimum number of chains (totally ordered subsets) into which the set can be partitioned. Dually, the height of the partially ordered set (the length of its longest chain) equals by Mirsky's theorem the minimum number of antichains into which the set can be partitioned. The family of all antichains in a finite partially ordered set can be given join and meet operations, making them into a distributive lattice. For the partially ordered system of all subsets of a finite set, ordered by set inclusion, the antichains are called Sperner families
and their lattice is a free distributive lattice, with a Dedekind number of elements. More generally, counting the number of antichains of a finite partially ordered set is #P complete.
Определения
Пусть – частично упорядоченное множество. Два элемента и частично упорядоченного множества называются сопоставимыми, если . Если два элемента не сопоставимы, они называются несравнимыми; то есть, и несравнимы, если не выполняется ни , ни .
Цепь в – это подмножество , в котором каждая пара элементов сопоставима; то есть, тотально упорядочена. Антицепь в – это подмножество , в котором каждая пара различных элементов несравнимы; то есть, между любыми двумя различными элементами в нет отношения порядка. (Однако некоторые авторы используют термин "антицепь" для обозначения сильной антицепи, подмножества, в котором нет элемента частично упорядоченного множества, меньшего, чем два различных элемента антицепи.)
(However, some authors use the term "antichain" to mean strong antichain, a subset such that there is no element of the poset smaller than two distinct elements of the antichain.)
Высота и ширина
Максимальная антицепочка — это антицепочка, которая не является собственным подмножеством какой-либо другой антицепочки. Антицепочка с максимальной кардинальностью — это антицепочка, имеющая кардинальность не меньше, чем у любой другой антицепочки. Ширина частично упорядоченного множества — это кардинальность антицепочки с максимальной кардинальностью. Любая антицепочка может пересекать любую цепочку не более чем в одном элементе, поэтому, если мы можем разбить элементы порядка на цепочки, то ширина порядка должна быть не больше (если антицепочка содержит более одного элемента, то по принципу Дирихле, найдется две ее элемента, принадлежащие одной и той же цепочке, что является противоречием). Теорема Дилворта утверждает, что эта граница всегда достижима: всегда существует антицепочка и разбиение элементов на цепочки, такие что число цепочек равно числу элементов в антицепочке, которое, следовательно, также равно ширине. Аналогично, высоту частичного порядка можно определить как максимальную кардинальность цепочки. Теорема Мирского утверждает, что в любом частичном порядке конечной высоты, высота равна минимальному числу антицепочек, на которые можно разбить порядок.
Семейства Sperner
Антицепочка в частичном порядке по включению подмножеств n-элементного множества называется семейством Спернера. Количество различных семейств Спернера подсчитывается числами Дедекинда, первые из которых равны 2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788. Даже пустое множество имеет две антицепи в своём множестве степеней: одна содержит единственный набор (само пустое множество), а другая не содержит ни одного набора.
2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 Even the empty set has two antichains in its power set: one containing a single set (the empty set itself) and one containing no sets.
Комплексность вычислений
Максимальная антицепь (и её размер, ширина данного частично упорядоченного множества) может быть найдена за полиномиальное время. Вычисление количества антицепей в данном частично упорядоченном множестве является #P-полной задачей.