En matemáticas , en el área de la teoría del orden , un antichain es un subconjunto de un conjunto parcialmente ordenado de modo 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, por 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 S un conjunto parcialmente ordenado. Dos elementos un y B de un conjunto parcialmente ordenado se llaman comparable si un ≤ b o b ≤ una . Si dos elementos no son comparables, se denominan incomparables; es decir, x y y son incomparable si ninguno x ≤ y ni y ≤ x .
Una cadena en S es un subconjunto C de S en el que cada par de elementos es comparable; es decir, C está totalmente ordenado . Un antichain en S es un subconjunto A de S en el que cada par de elementos diferentes es incomparable; que es, no hay ninguna relación de orden entre dos elementos diferentes en A . (Sin embargo, algunos autores usan el término "antichain" para referirse a un antichain fuerte , un subconjunto tal que no hay ningún elemento del poset más pequeño que dos elementos distintos del antichain).
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 k cadenas, entonces el ancho del pedido debe ser como máximo k (si el antichain tiene más de k elementos, por el casillero principio , habría 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. [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 menor número de antichains en los que se puede dividir el orden. [2]
Familias de Sperner
Un antichain en el orden de inclusión de subconjuntos de un conjunto de n elementos se conoce como familia Sperner . El número de familias de Sperner diferentes se cuenta mediante los números de Dedekind , [3] los primeros números son
- 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 A corresponde a un conjunto inferior
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:
De manera similar, podemos definir una operación de encuentro en antichains, correspondiente a la intersección de conjuntos inferiores:
La unión y la actividad se atenga a todas las anticadenas finitos de subconjuntos finitos de un conjunto X definir un retículo distributivo , el retículo distributivo libre generado por X . El teorema de representación de Birkhoff para celosías distributivas establece que cada celosía distributiva finita 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. [4]
Complejidad computacional
Un antichain máximo (y su tamaño, el ancho de un conjunto parcialmente ordenado dado) se puede encontrar en tiempo polinomial . [5] Contar el número de antichains en un conjunto parcialmente ordenado dado es # P-completo . [6]
Referencias
- ^ Dilworth, Robert P. (1950), "Un teorema de descomposición para conjuntos parcialmente ordenados", Annals of Mathematics , 51 (1): 161-166, doi : 10.2307 / 1969503 , JSTOR 1969503
- ^ Mirsky, Leon (1971), "Un teorema de descomposición dual de Dilworth", American Mathematical Monthly , 78 (8): 876–877, doi : 10.2307 / 2316481 , JSTOR 2316481
- ^ Kahn, Jeff (2002), "Entropía, conjuntos independientes y antichains: un nuevo enfoque al problema de Dedekind", Proceedings of the American Mathematical Society , 130 (2): 371-378, doi : 10.1090 / S0002-9939-01-06058 -0 , MR 1862115
- ^ Birkhoff, Garrett (1937), "Rings of sets", Duke Mathematical Journal , 3 (3): 443–454, doi : 10.1215 / S0012-7094-37-00334-X
- ^ Felsner, Stefan; Raghavan, Vijay; Spinrad, Jeremy (2003), "Algoritmos de reconocimiento para órdenes de pequeño ancho y gráficos de pequeño número de Dilworth" , Order , 20 (4): 351–364 (2004), doi : 10.1023 / B: ORDE.0000034609.99940.fb , MR 2079151 , S2CID 1363140
- ^ Provan, J. Scott; Ball, Michael O. (1983), "La complejidad de contar cortes y de calcular la probabilidad de que un gráfico esté conectado", SIAM Journal on Computing , 12 (4): 777–788, doi : 10.1137 / 0212053 , MR 0721012
enlaces externos
- Weisstein, Eric W. "Antichain" . MathWorld .
- "Antichain" . PlanetMath .