Posit graduado

Un conjunto de potencias , parcialmente ordenado por inclusión , con rango definido como el número de elementos, forma un conjunto ordenado gradualmente.

En matemáticas , en la rama de la combinatoria , un poset graduado es un conjunto parcialmente ordenado (poset) P equipado con una función de rango ρ desde P hasta el conjunto N de todos los números naturales . ρ debe satisfacer las dos propiedades siguientes:

• La función de rango es compatible con el ordenamiento, lo que significa que para todos los x e y en el orden, si x  <  y entonces ρ ( x ) <  ρ ( y ), y
• El rango es consistente con la relación de cobertura del ordenamiento, lo que significa que para todos los x e y , si y cubre a x entonces ρ ( y ) =  ρ ( x ) + 1.

El valor de la función de rango de un elemento del conjunto parcial se denomina rango . A veces, un conjunto parcial graduado se denomina conjunto parcial clasificado, pero esa frase tiene otros significados; consulte Conjunto parcial clasificado . Un rango o nivel de rango de un conjunto parcial graduado es el subconjunto de todos los elementos del conjunto parcial que tienen un valor de rango determinado. ^{[1] [2]}

Los posets graduados juegan un papel importante en la combinatoria y pueden visualizarse mediante un diagrama de Hasse .

Ejemplos

Algunos ejemplos de posets graduados (con la función de rango entre paréntesis) son:

• Números naturales N con su orden habitual (rango: el número mismo), o algún intervalo [0,  N ] de este conjunto parcial
• N ⁿ con el orden del producto (suma de los componentes), o un subconjunto del mismo que es un producto de intervalos
• Enteros positivos ordenados por divisibilidad (número de factores primos , contados con multiplicidad), o un subconjunto del mismo formado por los divisores de un N fijo
• La red booleana de subconjuntos finitos de un conjunto ordenados por inclusión (número de elementos del subconjunto)
• Cualquier red distributiva de conjuntos inferiores finitos de otro poset (número de elementos)
  • En particular, cualquier red distributiva finita
• Conjunto de todos los conjuntos no etiquetados en (número de elementos) ^[3] ${\displaystyle \{1,...,n\}}$
• Retículo de Young (número de casillas en el diagrama de Young)
• Cualquier red geométrica , como la red de subespacios de un espacio vectorial ( dimensión del subespacio)
• Red de particiones de un conjunto en un número finito de partes, ordenadas por refinamiento inverso (número de partes)
• Red de particiones de un conjunto finito X , ordenadas por refinamiento (número de elementos de X menos número de partes)
• Red de caras de politopos convexos (dimensión de la cara, más uno)
• Politopo abstracto ("distancia" desde la cara más pequeña, menos uno)
• Complejo simple abstracto (número de elementos del simplex)
• Un grupo con un conjunto generador , o equivalentemente su gráfico de Cayley , ordenado por el orden Bruhat débil o fuerte , y clasificado por longitud de palabra (longitud de la palabra reducida más corta)
  • En particular, un grupo de Coxeter , por ejemplo, permutaciones de un conjunto de n elementos totalmente ordenado, con orden de Bruhat débil o fuerte (número de inversiones adyacentes).

Caracterizaciones alternativas

La red N° ₅ no se puede graduar.

Un conjunto parcial acotado ^[4] admite una clasificación si y solo si todas las cadenas máximas en P tienen la misma longitud: ^[5] al establecer el rango del elemento menor en 0, se determina la función de rango por completo. Esto cubre muchos casos finitos de interés; vea la imagen para un ejemplo negativo. Sin embargo, los conjuntos parciales no acotados pueden ser más complicados.

Una función de rango candidata, compatible con el ordenamiento, convierte un conjunto parcial en un conjunto parcial graduado si y solo si, siempre que se tenga x  <  z con z de rango n  + 1, se puede encontrar un elemento y de rango n con x  ≤  y  <  z . Esta condición es suficiente porque si se toma z como una cubierta de x , la única opción posible es y  =  x mostrando que los rangos de x y z difieren en 1, y es necesaria porque en un conjunto parcial graduado se puede tomar como y cualquier elemento de rango máximo con x  ≤  y  <  z , que siempre existe y está cubierto por z .

A menudo, un conjunto parcial viene con un candidato natural para una función de rango; por ejemplo, si sus elementos son subconjuntos finitos de algún conjunto base B , se puede tomar el número de elementos de esos subconjuntos. Entonces, el criterio que se acaba de dar puede ser más práctico que la definición porque evita la mención de coberturas. Por ejemplo, si B es en sí mismo un conjunto parcial, y P consiste en sus conjuntos inferiores finitos (subconjuntos para los cuales con cada uno de sus elementos, todos los elementos más pequeños también están en el subconjunto), entonces el criterio se satisface automáticamente, ya que para los conjuntos inferiores x  ⊆  z siempre hay un elemento maximal de z que está ausente de x , y puede eliminarse de z para formar y .

En algunos conjuntos de elementos comunes, como la red de caras de un politopo convexo, existe una clasificación natural por dimensión , que, si se utiliza como función de rango, daría al elemento mínimo, la cara vacía, rango −1. En tales casos, podría ser conveniente modificar la definición indicada anteriormente añadiendo el valor −1 al conjunto de valores permitidos para la función de rango. Sin embargo, permitir números enteros arbitrarios como rango daría una noción fundamentalmente diferente; por ejemplo, ya no se aseguraría la existencia de un elemento mínimo.

Un poset graduado (con rangos enteros positivos) no puede tener ningún elemento x para el cual existan cadenas arbitrariamente largas con el elemento x más grande , ya que de lo contrario tendría que tener elementos de rango arbitrariamente pequeño (y eventualmente negativo). Por ejemplo, los números enteros (con el orden usual) no pueden ser un poset graduado, ni tampoco ningún intervalo (con más de un elemento) de números racionales o reales . (En particular, los posets graduados están bien fundados , lo que significa que satisfacen la condición de cadena descendente (DCC): no contienen ninguna cadena descendente infinita . ^[6] ) De ahora en adelante, por lo tanto, solo consideraremos posets en los que esto no sucede. Esto implica que siempre que x  <  y podemos llegar de x a y eligiendo repetidamente una cobertura, un número finito de veces. También significa que (para funciones de rango entero positivo) la compatibilidad de ρ con el orden se sigue del requisito sobre las coberturas. Como una variante de la definición de un poset graduado, Birkhoff ^[7] permite que las funciones de rango tengan valores enteros arbitrarios (en lugar de solo no negativos). En esta variante, los números enteros pueden ser calificados (por la función identidad) en su contexto, y la compatibilidad de los rangos con el ordenamiento no es redundante. Como tercera variante, Brightwell y West ^[8] definen una función de rango como valor entero, pero no requieren su compatibilidad con el ordenamiento; por lo tanto, esta variante puede calificar incluso, por ejemplo, los números reales por cualquier función, ya que el requisito sobre las coberturas es nulo para este ejemplo.

Téngase en cuenta que los posets graduados no necesitan satisfacer la condición de cadena ascendente (ACC): por ejemplo, los números naturales contienen la cadena ascendente infinita . ${\displaystyle 0<1<2<\dots }$

Un conjunto parcial se clasifica si y solo si cada componente conectado de su gráfico de comparabilidad se clasifica, por lo que las caracterizaciones posteriores supondrán que este gráfico de comparabilidad está conectado. En cada componente conectado, la función de rango solo es única hasta un desplazamiento uniforme (por lo que la función de rango siempre se puede elegir de modo que los elementos de rango mínimo en su componente conectado tengan rango 0).

Si P tiene un elemento mínimo Ô entonces ser graduado es equivalente a la condición de que para cualquier elemento x todas las cadenas maximalistas en el intervalo [Ô,  x ] tengan la misma longitud. Esta condición es necesaria ya que cada paso en una cadena maximalista es una relación de recubrimiento, que debería cambiar el rango en 1. La condición también es suficiente, ya que cuando se cumple, uno puede usar la longitud mencionada para definir el rango de x (la longitud de una cadena finita es su número de "pasos", por lo tanto uno menos que su número de elementos), y siempre que x cubra y , adjuntando x a una cadena maximalista en [Ô, y ] da una cadena maximalista en [Ô, x ].

Si P también tiene un elemento máximo Î (de modo que es un conjunto parcial acotado ), entonces la condición anterior se puede simplificar al requisito de que todas las cadenas máximas en P tengan la misma longitud (finita). Esto es suficiente, ya que cualquier par de cadenas máximas en [Ô, x ] se puede extender por una cadena máxima en [ x , Î] para dar un par de cadenas máximas en P .

Nota Stanley define que un conjunto parcial se clasifica como de longitud n si todas sus cadenas máximas tienen longitud n (Stanley 1997, p. 99). Esta definición se da en un contexto en el que el interés se centra principalmente en los conjuntos parciales finitos, y aunque posteriormente el libro suele omitir la parte "de longitud n ", no parece apropiado utilizarla como definición de "clasificado" para conjuntos parciales generales, porque (1) no dice nada sobre los conjuntos parciales cuyas cadenas máximas son infinitas, en particular (2) excluye conjuntos parciales importantes como el retículo de Young . Tampoco está claro por qué en un conjunto parcial clasificado se debería exigir que todos los elementos mínimos, así como todos los elementos máximos, tengan la misma longitud, incluso si Stanley da ejemplos que dejan claro que sí quiere exigir eso (ibid, pp. 216 y 219).

El caso habitual

Muchos autores en combinatoria definen los posets graduados de tal manera que todos los elementos mínimos de P deben tener rango 0, y además que existe un rango máximo r que es el rango de cualquier elemento máximo. Entonces, ser graduado significa que todas las cadenas máximas tienen longitud r , como se indicó anteriormente. En este caso se dice que P tiene rango r .

Además, en este caso, a los niveles de rango se les asocian los números de rango o números de Whitney . Estos números se definen por = número de elementos de P que tienen rango i . ${\displaystyle W_{0},W_{1},W_{2},...}$ ${\displaystyle W_{i}}$

Los números de Whitney están relacionados con muchos teoremas combinatorios importantes . El ejemplo clásico es el teorema de Sperner , que puede formularse de la siguiente manera:

Para el conjunto potencia de cada conjunto finito, la cardinalidad máxima de una familia de Sperner es igual al número máximo de Whitney . ${\displaystyle {\mathcal {P}}(S)}$ ${\displaystyle S}$

Esto significa:

Todo conjunto de potencias finitas tiene la propiedad de Sperner

Véase también

• Calificado (matemáticas)
• Prewellordering : un prewellordering con una norma es análogo a un conjunto ordenado graduado, reemplazando una función a los números enteros con una función a los ordinales.
• Producto estrella , un método para combinar dos posets graduados

Notas

1. Stanley, Richard (1984), "Cocientes de posets de Peck", Order , 1 (1): 29–34, doi :10.1007/BF00396271, MR  0745587, S2CID  14857863.
2. Butler, Lynne M. (1994), Redes de subgrupos y funciones simétricas, Memorias de la American Mathematical Society, vol. 539, American Mathematical Society, pág. 151, ISBN 9780821826003.
3. Culberson, Joseph C.; Rawlins, Gregory JE (1990), "Nuevos resultados de un algoritmo para contar conjuntos parciales", Order , 7 (4): 361–374, doi :10.1007/BF00383201, S2CID  120473635
4. Lo que significa que tiene un elemento menor y un elemento mayor .
5. Es decir, no se tiene una situación como y ambas siendo cadenas máximas. ${\displaystyle x<z_{1}<y}$ ${\displaystyle x<w_{1}<w_{2}<y}$
6. El hecho de que no contenga cadenas descendentes arbitrariamente largas que comiencen en un elemento fijo excluye, por supuesto, cualquier cadena descendente infinita. Sin embargo, la primera condición es estrictamente más fuerte; el conjunto tiene cadenas arbitrariamente largas que descienden desde  , pero no tiene cadenas descendentes infinitas. ${\displaystyle \mathbb {N} \cup \{\infty \}}$ ${\displaystyle \infty }$
7. 'Teoría de retículas', Am. Math. Soc., Colloquium Publications, vol. 25, 1967, pág. 5
8. Véase la referencia [2], p.722.

Referencias

• Stanley, Richard (1997). Combinatoria enumerativa (vol. 1, Cambridge Studies in Advanced Mathematics 49) . Cambridge University Press . ISBN 0-521-66351-2.
• Anderson, Ian (1987). Combinatoria de conjuntos finitos . Oxford, Reino Unido: Clarendon Press . ISBN. 0-19-853367-5.
• Engel, Konrad (1997). Teoría de Sperner . Cambridge, Reino Unido (et al.): Cambridge University Press. ISBN 0-521-45206-6.
• Kung, Joseph PS; Rota, Gian-Carlo ; Yan, Catherine H. (2009). Combinatoria: el estilo Rota . Cambridge, Reino Unido (et al.): Cambridge University Press. ISBN 978-0-521-73794-4.