Anticadena

Una anticadena  es un subconjunto de un conjunto parcialmente ordenado en el que dos elementos distintos cualesquiera son incomparables.

La máxima cardinalidad de una anticadena de un conjunto parcialmente ordenado se llama ancho ; por el teorema de Dilworth , el ancho también es igual al número mínimo de cadenas (subconjuntos totalmente ordenados) en las que se puede dividir un conjunto. En consecuencia, la altura de un 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 que se puede dividir este conjunto.

La familia de todas las anticadenas en un conjunto finito parcialmente ordenado puede equiparse con operaciones de unión e intersección, convirtiéndolas en una red distributiva . Para un sistema parcialmente ordenado de todos los subconjuntos de un conjunto finito ordenado por inclusión de conjunto, las anticadenas se denominan familias de Sperner , y su red es una red distributiva libre con un número de elementos de Dedekind . En general, el problema de contar el número de anticadenas de un conjunto finito parcialmente ordenado es ♯P-completo .