Antichain - Antichain

Em matemática , na área da teoria da ordem , uma anticadeia é um subconjunto de um conjunto parcialmente ordenado de modo que quaisquer dois elementos distintos no subconjunto são incomparáveis .

O tamanho da maior anticadeia em um conjunto parcialmente ordenado é conhecido como largura . Pelo teorema de Dilworth , isso também é igual ao número mínimo de cadeias (subconjuntos totalmente ordenados) em que o conjunto pode ser particionado. Duplamente, a altura do conjunto parcialmente ordenado (o comprimento de sua cadeia mais longa) é igual, pelo teorema de Mirsky, ao número mínimo de antichains em que o conjunto pode ser particionado.

A família de todas as antichains em um conjunto finito parcialmente ordenado pode receber operações de junção e reunião , tornando-as em uma rede distributiva . Para o sistema parcialmente ordenado de todos os subconjuntos de um conjunto finito, ordenados por inclusão de conjunto, os antichains são chamados de famílias Sperner e sua rede é uma rede distributiva livre , com um número de elementos de Dedekind . Mais geralmente, a contagem do número de antichains de um conjunto finito parcialmente ordenado é # P-completo .

Definições

Let Ser um conjunto parcialmente ordenado. Dois elementos e de um conjunto parcialmente ordenado são chamados comparável se Se dois elementos não são comparáveis, eles são chamados incomparável; isto é, e são incomparáveis se nenhum ${\ displaystyle S}$ ${\ displaystyle a}$ ${\ displaystyle b}$ ${\ displaystyle a \ leq b {\ text {ou}} b \ leq a.}$ ${\ displaystyle x}$ ${\ displaystyle y}$ ${\ displaystyle x \ leq y {\ text {nor}} y \ leq x.}$

Uma cadeia em é um subconjunto no qual cada par de elementos é comparável; ou seja, está totalmente ordenado . Uma antichain em é um subconjunto de em que cada par de elementos diferentes é incomparável; ou seja, não há relação de ordem entre quaisquer dois elementos diferentes em (No entanto, alguns autores usam o termo "antichain" para significar forte antichain , um subconjunto tal que não há nenhum elemento do poset menor do que dois elementos distintos da antichain. ) ${\ displaystyle S}$ ${\ displaystyle C \ subseteq S}$ ${\ displaystyle C}$ ${\ displaystyle S}$ ${\ displaystyle A}$ ${\ displaystyle S}$ ${\ displaystyle A.}$

Altura e largura

Uma anticadeia máxima é uma anticadeia que não é um subconjunto apropriado de qualquer outra anticadeia. Uma anticadeia máxima é uma anticadeia que tem cardinalidade pelo menos tão grande quanto qualquer outra anticadeia. A largura de um conjunto parcialmente ordenado é a cardinalidade de uma anticadeia máxima. Qualquer anticadeia pode interceptar qualquer cadeia em no máximo um elemento, então, se pudermos particionar os elementos de uma ordem em cadeias, a largura da ordem deve ser no máximo (se a anticadeia tiver mais do que elementos, pelo princípio do escaninho , seriam 2 de seus elementos pertencentes à mesma cadeia, contradição). O teorema de Dilworth afirma que esse limite sempre pode ser alcançado: sempre existe uma anticadeia e uma partição dos elementos em cadeias, de modo que o número de cadeias é igual ao número de elementos na anticadeia, que, portanto, também deve ser igual à largura. Da mesma forma, pode-se definir a altura de uma ordem parcial como a cardinalidade máxima de uma cadeia. O teorema de Mirsky afirma que em qualquer ordem parcial de altura finita, a altura é igual ao menor número de antichains em que a ordem pode ser particionada. ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle k}$

Famílias Sperner

Uma anticadeia na ordem de inclusão de subconjuntos de um conjunto de elementos é conhecida como família Sperner . O número de famílias Sperner diferentes é contado pelos números de Dedekind , os primeiros dos quais são ${\ displaystyle n}$

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (sequência A000372 no OEIS ).

Mesmo o conjunto vazio tem dois antichains em seu conjunto de potência: um contendo um único conjunto (o próprio conjunto vazio) e outro contendo nenhum conjunto.

Junte-se e conheça as operações

Qualquer anticadeia corresponde a um conjunto inferior ${\ displaystyle A}$

{\ displaystyle L_ {A} = \ {x: \ existe y \ em A {\ mbox {tal que}} x \ leq y \}.}

Em uma ordem parcial finita (ou mais geralmente uma ordem parcial que satisfaça a condição de cadeia ascendente ), todos os conjuntos inferiores têm essa forma. A união de quaisquer dois conjuntos inferiores é outro conjunto inferior, e a operação de união corresponde, desta forma, a uma operação de junção em antichains:

{\ displaystyle A \ vee B = \ {x \ in A \ cup B: \ nexiste y \ in A \ cup B {\ mbox {tal que}} x <y \}.}

Da mesma forma, podemos definir uma operação de encontro em antichains, correspondendo à interseção de conjuntos inferiores:

{\ displaystyle A \ wedge B = \ {x \ in L_ {A} \ cap L_ {B}: \ nexiste y \ in L_ {A} \ cap L_ {B} {\ mbox {tal que}} x <y \}.}

As operações de junção e reunião em todos os antichains finitos de subconjuntos finitos de um conjunto definem uma rede distributiva , a rede distributiva livre gerada pelo teorema de representação de Birkhoff para redes distributivas afirma que cada rede distributiva finita pode ser representada por meio de operações de junção e encontro em antichains de um ordem parcial finita, ou equivalentemente como operações de união e interseção nos conjuntos inferiores da ordem parcial.

{\ displaystyle X}

{\ displaystyle X.}

Complexidade computacional

Uma anticadeia máxima (e seu tamanho, a largura de um determinado conjunto parcialmente ordenado) pode ser encontrada em tempo polinomial . Contar o número de antichains em um determinado conjunto parcialmente ordenado é # P-completo .

Referências

links externos

Weisstein, Eric W. "Antichain" . MathWorld .
"Antichain" . PlanetMath .

Languages

In other projects