Из Википедии, бесплатной энциклопедии
Перейти к навигации Перейти к поиску

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

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

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

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

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

Цепь в S - это подмножество C в 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 ).

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

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

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

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

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

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

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

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

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

  1. ^ Дилворт, Роберт П. (1950), "Разложение теорема для частично упорядоченных множеств", Анналы математики , 51 (1): 161-166, да : 10,2307 / 1969503 , JSTOR  1969503
  2. ^ Мирский, Leon (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 , Руководство по ремонту 1862115 
  4. ^ Биркгофу, Garrett (1937), "Кольца множеств", Дюк математический журнал , 3 (3): 443-454, DOI : 10,1215 / S0012-7094-37-00334-X
  5. ^ Фельснер, Стефан; Рагхаван, Виджай; Спинрад, Джереми (2003), "Алгоритмы распознавания для порядков малой ширины и графиков небольшого числа Dilworth" , заказ , 20 (4): 351-364 (2004), DOI : 10,1023 / B: ORDE.0000034609.99940.fb , MR 2079151 , S2CID 1363140  
  6. ^ Прован, Дж. Скотт; Болл, Майкл О. (1983), «Сложность сокращений подсчета и вычисления вероятности того, что график соединен», SIAM журнал по вычислениям , 12 (4): 777-788, DOI : 10,1137 / 0212053 , МР 0721012 

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

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