Anticadena

Subconjunto de elementos incomparables

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 en el subconjunto son incomparables .

El tamaño de la anticadena más grande en un conjunto parcialmente ordenado se conoce como su ancho . Según el teorema de Dilworth , esto también es igual 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 anticadenas en las que se puede dividir el conjunto.

A la familia de todas las anticadenas de 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 Dedekind de elementos. De manera más general, contar la cantidad de anticadenas de un conjunto finito parcialmente ordenado es #P-completo .

Definiciones

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

Una cadena en es un subconjunto en el que cada par de elementos es comparable; es decir, está totalmente ordenado . Una anticadena en 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 cualesquiera en (Sin embargo, algunos autores usan el término "anticadena" para referirse a una anticadena fuerte , un subconjunto tal que no existe ningún elemento del conjunto poset más pequeño que dos elementos distintos de la anticadena). ${\displaystyle S}$ ${\displaystyle C\subseteq S}$ ${\displaystyle C}$ ${\displaystyle S}$ ${\displaystyle A}$ ${\displaystyle S}$ ${\displaystyle A.}$

Altura y anchura

Una anticadena máxima es una anticadena que no es un subconjunto propio 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 intersecar cualquier cadena en como máximo un elemento, por lo que, si podemos dividir los elementos de un orden en cadenas, entonces el ancho del orden debe ser como máximo (si la anticadena tiene más de elementos, por el principio del palomar , habría 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 en 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 menor número de anticadenas en las que se puede dividir el orden. ^[2] ${\displaystyle k}$ ${\displaystyle k}$ ${\displaystyle k}$

Familias Sperner

Una anticadena en el orden de inclusión de subconjuntos de un conjunto de elementos se conoce como familia de Sperner . El número de familias de Sperner diferentes se cuenta mediante los números de Dedekind , ^[3] los primeros de los cuales son ${\displaystyle n}$

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

Incluso el conjunto vacío tiene dos anticadenas en su conjunto potencia: una que contiene un solo conjunto (el conjunto vacío en sí) y otra que no contiene ningún conjunto.

Únase y conozca las operaciones

Cualquier anticadena 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 cualesquiera es otro conjunto inferior, y la operación de unión corresponde de esta manera a una operación de unión sobre anticadenas: De manera similar, podemos definir una operación de encuentro sobre anticadenas, correspondiente a la intersección de conjuntos inferiores: Las operaciones de unión y encuentro sobre todas las anticadenas finitas de subconjuntos finitos de un conjunto definen una red distributiva , la red distributiva libre generada por el teorema de representación de Birkhoff para redes distributivas establece que toda red distributiva finita puede representarse mediante operaciones de unión y encuentro sobre anticadenas de un orden parcial finito, o equivalentemente como operaciones de unión e intersección sobre los conjuntos inferiores del orden parcial. ^[4] ${\displaystyle A}$ $${\displaystyle L_{A}=\{x:\exists y\in A{\mbox{ such that }}x\leq y\}.}$$ $${\displaystyle A\vee B=\{x\in A\cup B:\nexists y\in A\cup B{\mbox{ such that }}x<y\}.}$$ $${\displaystyle A\wedge B=\{x\in L_{A}\cap L_{B}:\nexists y\in L_{A}\cap L_{B}{\mbox{ such that }}x<y\}.}$$ ${\displaystyle X}$ ${\displaystyle X.}$

Complejidad computacional

Una anticadena máxima (y su tamaño, el ancho de un conjunto parcialmente ordenado dado) se puede encontrar en tiempo polinomial . ^[5] Contar el número de anticadenas en un conjunto parcialmente ordenado dado es #P-completo . ^[6]

Referencias

1. 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
2. Mirsky, Leon (1971), "Un dual del teorema de descomposición de Dilworth", American Mathematical Monthly , 78 (8): 876–877, doi :10.2307/2316481, JSTOR  2316481
3. Kahn, Jeff (2002), "Entropía, conjuntos independientes y anticadenas: un nuevo enfoque al problema de Dedekind", Actas de la American Mathematical Society , 130 (2): 371–378, doi : 10.1090/S0002-9939-01-06058-0 , MR  1862115
4. Birkhoff, Garrett (1937), "Anillos de conjuntos", Duke Mathematical Journal , 3 (3): 443–454, doi :10.1215/S0012-7094-37-00334-X
5. Felsner, Stefan; Raghavan, Vijay; Spinrad, Jeremy (2003), "Algoritmos de reconocimiento para órdenes de ancho pequeño y gráficos de números de Dilworth pequeños", Order , 20 (4): 351–364 (2004), doi :10.1023/B:ORDE.0000034609.99940.fb, MR  2079151, S2CID  1363140
6. 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. "Anticadena". MathWorld .
• "Anticadena". PlanetMath .