Anticaína - Antichain

En matemáticas , en el área de la teoría del orden , un antichain es un subconjunto de un conjunto parcialmente ordenado de manera que dos elementos distintos del subconjunto son incomparables .

El tamaño del antichain más grande en un conjunto parcialmente ordenado se conoce como su ancho . Según el teorema de Dilworth , esto también equivale al número mínimo de cadenas (subconjuntos totalmente ordenados) en los que se puede dividir el conjunto. Dualmente, la altura del conjunto parcialmente ordenado (la longitud de su cadena más larga) es igual, según el teorema de Mirsky, al número mínimo de antichains en los que se puede dividir el conjunto.

La familia de todas las antichains en un conjunto finito parcialmente ordenado puede recibir operaciones de unión y encuentro , convirtiéndolas en una red distributiva . Para el sistema parcialmente ordenado de todos los subconjuntos de un conjunto finito, ordenados por inclusión de conjuntos, los antichains se denominan familias de Sperner y su retícula es una retícula distributiva libre , con un número Dedekind de elementos. De manera más general, contar el número de antichains de un conjunto finito parcialmente ordenado es # P-completo .

Definiciones

Sea un conjunto parcialmente ordenado. Dos elementos y de un conjunto parcialmente ordenado se denominan comparables si dos elementos no son comparables se denominan incomparables; es decir, y son incomparables si ninguno ${\ Displaystyle S}$ ${\ Displaystyle a}$ ${\ Displaystyle b}$ ${\ Displaystyle a \ leq b {\ text {o}} b \ leq a.}$ ${\ Displaystyle x}$ ${\ Displaystyle y}$ ${\ Displaystyle x \ leq y {\ text {nor}} y \ leq x.}$

Una cadena es un subconjunto en el que cada par de elementos es comparable; es decir, está totalmente ordenado . Un antichain in es un subconjunto de en el que cada par de elementos diferentes es incomparable; es decir, no existe una relación de orden entre dos elementos diferentes en (Sin embargo, algunos autores usan el término "antichain" para significar antichain fuerte , un subconjunto tal que no hay ningún elemento del poset más pequeño que dos elementos distintos del antichain. ) ${\ Displaystyle S}$ ${\ Displaystyle C \ subseteq S}$ ${\ Displaystyle C}$ ${\ Displaystyle S}$ ${\ Displaystyle A}$ ${\ Displaystyle S}$ ${\ Displaystyle A.}$

Alto y ancho

Un antichain máximo es un antichain que no es un subconjunto adecuado de ningún otro antichain. Un antichain máximo es un antichain que tiene cardinalidad al menos tan grande como cualquier otro antichain. El ancho de un conjunto parcialmente ordenado es la cardinalidad de un antichain máximo. Cualquier antichain puede intersecar cualquier cadena en como máximo un elemento, por lo que, si podemos dividir los elementos de un pedido en cadenas, entonces el ancho del pedido debe ser como máximo (si el antichain tiene más de elementos, por el principio de casillero , hay serían 2 de sus elementos pertenecientes a la misma cadena, contradicción). El teorema de Dilworth establece que este límite siempre se puede alcanzar: siempre existe un antichain y una partición de los elementos en cadenas, de modo que el número de cadenas es igual al número de elementos en el antichain, que por lo tanto también debe ser igual al ancho. De manera similar, se puede definir la altura de un pedido parcial como la cardinalidad máxima de una cadena. El teorema de Mirsky establece que en cualquier orden parcial de altura finita, la altura es igual al número más pequeño de antichains en los que se puede dividir el orden. ${\ Displaystyle k}$ ${\ Displaystyle k}$ ${\ Displaystyle k}$

Familias de Sperner

Un antichain en el orden de inclusión de subconjuntos de un conjunto de elementos se conoce como familia Sperner . El número de familias de Sperner diferentes se cuenta mediante los números de Dedekind , los primeros números son ${\ Displaystyle n}$

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788 (secuencia A000372 en la OEIS ).

Incluso el conjunto vacío tiene dos antichains en su conjunto de poder: uno que contiene un conjunto único (el conjunto vacío en sí mismo) y otro que no contiene conjuntos.

Únase y conozca operaciones

Cualquier antichain corresponde a un conjunto inferior ${\ Displaystyle A}$

{\ Displaystyle L_ {A} = \ {x: \ existe y \ en A {\ mbox {tal que}} x \ leq y \}.}

En un orden parcial finito (o más generalmente un orden parcial que satisface la condición de cadena ascendente ) todos los conjuntos inferiores tienen esta forma. La unión de dos conjuntos inferiores es otro conjunto inferior, y corresponde la operación de unión de esta manera a una unirse operación en anticadenas:

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

De manera similar, podemos definir una operación de encuentro en antichains, correspondiente a la intersección de conjuntos inferiores:

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

Las operaciones de unión y encuentro en todos los antichains finitos de subconjuntos finitos de un conjunto definen un retículo distributivo , el retículo distributivo libre generado por el teorema de representación de Birkhoff para retículos distributivos establece que cada retículo distributivo finito se puede representar mediante operaciones de unión y encuentro en antichains de un orden parcial finito, o equivalentemente como operaciones de unión e intersección en los conjuntos inferiores del orden parcial.

{\ Displaystyle X}

{\ Displaystyle X.}

Complejidad computacional

Un antichain máximo (y su tamaño, el ancho de un conjunto parcialmente ordenado dado) se puede encontrar en tiempo polinomial . Contar el número de antichains en un conjunto parcialmente ordenado es # P-completo .

Referencias

enlaces externos

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

Languages

In other projects