Loading AI tools
Из Википедии, свободной энциклопедии
Антицепь — подмножество частично упорядоченного множества, в котором любые два различных элемента несравнимы.
Максимальная мощность антицепи частично упорядоченного множества называется его шириной; по теореме Дилуорса ширина также равна минимальному количеству цепей (полностью упорядоченных подмножеств), на которые можно разбить множество. Соответственно, высота частично упорядоченного множества (длина его самой длинной цепи) равна по теореме Мирского минимальному количеству антицепей, на которые это множество может быть разбито.
Семейство всех антицепей в конечном частично упорядоченном множестве может быть снабжено операциями объединения и пересечения, превращая их в дистрибутивную решетку[англ.]. Для частично упорядоченной системы всех подмножеств конечного множества, упорядоченных по включению множеств, антицепи называются семействами Шпернера[англ.], а их решётка является свободной дистрибутивной решеткой с дедекиндовым числом элементов. В общем случае задача подсчёта количества антицепей конечного частично упорядоченного множества является ♯P-полной[англ.].
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.