Античейн - Antichain

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

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

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

Определения

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

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

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

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

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

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

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

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

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

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

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

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

Операции соединения и пересечения на всех конечных антицепях конечных подмножеств множества Икс определить распределительная решетка, свободная распределительная решетка, порожденная Икс. Теорема Биркгофа о представлении для дистрибутивных решеток утверждает, что каждая конечная дистрибутивная решетка может быть представлена ​​через операции соединения и пересечения на антицепях конечного частичного порядка, или, что эквивалентно, как операции объединения и пересечения на нижние наборы частичного заказа.[4]

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

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

Рекомендации

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

внешняя ссылка