En matemáticas , en el área de la teoría del orden , una anticadena es un subconjunto de un conjunto parcialmente ordenado tal que dos elementos distintos cualesquiera en el subconjunto son incomparables .
El tamaño de la anticadena más grande en un conjunto parcialmente ordenado se conoce como ancho . Según el teorema de Dilworth , esto también es igual al número mínimo de cadenas (subconjuntos totalmente ordenados) en las 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 anticadenas en las que se puede dividir el conjunto.
A la familia de todas las anticadenas en un conjunto finito parcialmente ordenado se le pueden dar 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, las anticadenas se denominan familias de Sperner y su red es una red distributiva libre , con un número de elementos de Dedekind. De manera más general, contar el número de anticadenas de un conjunto finito parcialmente ordenado es #P-completo .
Sea un conjunto parcialmente ordenado. Dos elementos de un conjunto parcialmente ordenado se llaman comparables si dos elementos no son comparables se llaman incomparables; es decir, y son incomparables si ninguno de los dos
Una cadena es un subconjunto en el que cada par de elementos es comparable; es decir, está totalmente ordenado . Una anticadena 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 (sin embargo, algunos autores usan el término "anticadena" para referirse a una anticadena fuerte , un subconjunto tal que no hay ningún elemento del poset más pequeño que dos elementos distintos de la anticadena. )
Una anticadena máxima es una anticadena que no es un subconjunto adecuado de ninguna otra anticadena. Una anticadena máxima es una anticadena que tiene una cardinalidad al menos tan grande como cualquier otra anticadena. El ancho de un conjunto parcialmente ordenado es la cardinalidad de una anticadena máxima. Cualquier anticadena puede intersectar cualquier cadena en como máximo un elemento, por lo tanto, si podemos dividir los elementos de un pedido en cadenas, entonces el ancho del orden debe ser como máximo (si la anticadena tiene más de elementos, según el principio de casillero , hay serían 2 de sus elementos pertenecientes a la misma cadena, una contradicción). El teorema de Dilworth establece que este límite siempre se puede alcanzar: siempre existe una anticadena y una partición de los elementos en cadenas, de modo que el número de cadenas es igual al número de elementos de la anticadena, que por lo tanto también debe ser igual al ancho. [1] De manera similar, se puede definir la altura de un orden 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 anticadenas en las que se puede dividir el orden. [2]
Una anticadena en el orden de inclusión de subconjuntos de un conjunto de elementos se conoce como familia Sperner . El número de familias Sperner diferentes se cuenta mediante los números de Dedekind , [3] los primeros números son
Incluso el conjunto vacío tiene dos anticadenas en su conjunto de poder: una que contiene un único conjunto (el conjunto vacío en sí) y otra que no contiene conjuntos.
Cualquier anticadena corresponde a un conjunto inferior
Una anticadena máxima (y su tamaño, el ancho de un conjunto parcialmente ordenado) se puede encontrar en tiempo polinómico . [5] Contar el número de anticadenas en un conjunto parcialmente ordenado dado es #P-completo . [6]
