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 siguientes dos propiedades:
- La función de rango es compatible con el pedido, lo que significa que por cada x y y en el orden con x < y , debe ser el caso de que ρ ( x ) < ρ ( Y ), y
- El rango es consistente con la relación de cobertura de los pedidos, lo que significa que para cada x y y para el que Y cubiertas x , tiene que ser el caso de que ρ ( y ) = ρ ( x ) + 1.
El valor de la función de rango para un elemento del poset se llama rango . A veces, un poset calificado se denomina poset clasificado, pero esa frase tiene otros significados; ver Poset clasificado . Un rango o nivel de rango de un poset calificado es el subconjunto de todos los elementos del poset que tienen un valor de rango dado. [1] [2]
Los posets clasificados juegan un papel importante en la combinatoria y se pueden visualizar mediante un diagrama de Hasse .
Ejemplos de
Algunos ejemplos de publicaciones graduadas (con la función de rango entre paréntesis) son:
- los números naturales N , con su orden habitual (rango: el número en sí), o algún intervalo [0, N ] de este conjunto,
- N n , con el orden del producto (suma de los componentes), o una subpropuesta del mismo que es un producto de intervalos,
- los enteros positivos, ordenados por divisibilidad (número de factores primos, contados con multiplicidad), o una subposicion de él formada por los divisores de un N fijo ,
- la red booleana de subconjuntos finitos de un conjunto (número de elementos del subconjunto),
- la celosía de las particiones de un conjunto en un número finito de partes, ordenadas por refinamiento inverso (número de partes),
- la celosía de particiones de un conjunto finito X , ordenada por refinamiento (número de elementos de X menos número de partes),
- un grupo y un grupo electrógeno, o equivalentemente su gráfico de Cayley , ordenados por el orden de Bruhat débil o fuerte , y clasificados por longitud de palabra (longitud de la palabra más corta y reducida).
- En particular para los grupos de Coxeter , por ejemplo, permutaciones de un conjunto de elementos n totalmente ordenados , con el orden de Bruhat débil o fuerte (número de inversiones adyacentes),
- celosías geométricas , como la celosía de subespacios de un espacio vectorial (dimensión del subespacio),
- la red distributiva de conjuntos inferiores finitos de otro poset (número de elementos),
- Celosía de Young , una instancia particular del ejemplo anterior (número de cajas en el diagrama de Young),
- celosías faciales de politopos convexos (dimensión de la cara, más uno),
- politopos abstractos ("distancia" de la menor cara, menos una),
- complejos simpliciales abstractos (número de elementos del simplex).
Caracterizaciones alternativas
Un poset acotado [3] admite una calificación si y solo si todas las cadenas máximas en P tienen la misma longitud: [4] establecer el rango del elemento mínimo en 0 entonces 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, las publicaciones ilimitadas pueden ser más complicadas.
Una función de rango candidato, compatible con el orden, convierte un poset en poset graduado si y solo si, siempre que uno tiene 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 z se toma para ser una cubierta de x , la única opción posible es y = x que muestra que las filas de x y z difieren en 1, y es necesario debido a que en una poset graduada puede tomar para y cualquier elemento de rango máximo con x ≤ y < z , que siempre existe y está cubierto por z .
A menudo, un poset viene con un candidato natural para una función de rango; por ejemplo, si sus elementos son subconjuntos finitos de algún conjunto básico 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 mencionar las cubiertas. Por ejemplo, si B es en sí mismo un conjunto, y P consta de 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 conjuntos inferiores x ⊆ z siempre hay un elemento máximo de z que está ausente de x , y se puede quitar de z para formar y .
En algunos posets comunes, como el enrejado de caras de un politopo convexo, hay una clasificación natural por dimensión , que si se usa como función de rango daría al elemento mínimo, la cara vacía, rango –1. En tales casos, puede ser conveniente modificar la definición indicada anteriormente adjuntando el valor –1 al conjunto de valores permitidos para la función de rango. Sin embargo, permitir enteros arbitrarios como rango daría una noción fundamentalmente diferente; por ejemplo, ya no se garantizarí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 mayor elemento x , ya que de lo contrario tendría que tener elementos de rango arbitrariamente pequeño (y eventualmente negativo). Por ejemplo, los enteros (con el orden habitual) 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 . [5] ) Por lo tanto, de ahora en adelante solo consideraremos posets en los que esto no sucede. Esto implica que cada vez que x < y que podemos obtener de x a y por la elección de una cubierta en repetidas ocasiones, un número finito de veces. También significa que (para funciones de rango entero positivo) la compatibilidad de ρ con el orden se deriva del requisito sobre las cubiertas. Como variante de la definición de poset graduado, Birkhoff [6] permite que las funciones de rango tengan valores enteros arbitrarios (en lugar de solo no negativos). En esta variante, los números enteros se pueden calificar (por la función de identidad) en su configuración, y la compatibilidad de los rangos con el orden no es redundante. Como tercera variante, Brightwell y West [7] definen una función de rango para que sea de valor entero, pero no requieren su compatibilidad con el orden; por lo tanto, esta variante puede calificar incluso, por ejemplo, los números reales mediante cualquier función, ya que el requisito sobre cubiertas es vacío para este ejemplo.
Tenga 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.
Un poset se califica si y solo si se califica cada componente conectado de su gráfico de comparabilidad , 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 cambio 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 calificado es equivalente a la condición de que para cualquier elemento x todas las cadenas máximas en el intervalo [Ô, x ] tengan la misma longitud. Esta condición es necesaria ya que cada paso en una cadena máxima es una relación de cobertura, que debería cambiar el rango en 1. La condición también es suficiente, ya que cuando se cumple, se 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 que uno menos que su número de elementos), y siempre que x cubre y , unir x a una cadena máxima en [Ô, y ] da una cadena máxima en [Ô, x ] .
Si P también tiene un elemento mayor Î (de modo que es un poset 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 maximales en [O, x ] se pueden extender por una cadena máxima en [ x , Î] para dar un par de cadenas maximales en P .
- Nota Stanley define un poset para ser calificado 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 está principalmente en posets finitos, y aunque el libro posteriormente a menudo descarta la parte "de longitud n ", no parece apropiado usar esto como definición de "graduado" para posets generales, porque ( 1) no dice nada sobre posets cuyas cadenas máximas son infinitas, en particular (2) excluye posets importantes como el enrejado de Young . Además, no está claro por qué en un conjunto graduado todos los elementos mínimos, así como todos los elementos máximos, deberían tener la misma longitud, incluso si Stanley da ejemplos que dejan en claro que él tiene la intención de exigir eso (ibid, págs. y 219).
El caso habitual
Muchos autores en combinatoria definen posiciones graduadas de tal manera que todos los elementos mínimos de P deben tener rango 0 y, además, existe un rango máximo r que es el rango de cualquier elemento máximo. Entonces, ser clasificado significa que todas las cadenas máximas tienen una 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 asocian los números de rango o números de Whitney . Estos números están definidos por= número de elementos de P que tienen rango i .
Los números de Whitney están conectados con muchos teoremas combinatorios importantes . El ejemplo clásico es el teorema de Sperner , que se puede formular de la siguiente manera:
- Para el grupo de poder de cada conjunto finito la cardinalidad máxima de una familia Sperner es igual al número máximo de Whitney .
Esto significa:
- Cada conjunto de potencia finito tiene la propiedad de Sperner
Ver también
- Calificado (matemáticas)
- Ordenamiento previo : un ordenamiento previo con una norma es análogo a un poset graduado, reemplazando un mapa a los enteros con un mapa a los ordinales
- Producto estrella , un método para combinar dos posets calificados
Notas
- ^ Stanley, Richard (1984), "Cocientes de posets de Peck", Orden , 1 (1): 29-34, doi : 10.1007 / BF00396271 , MR 0745587 , S2CID 14857863.
- ^ Butler, Lynne M. (1994), Subgrupos enrejados y funciones simétricas , Memorias de la Sociedad Matemática Estadounidense, 539 , Sociedad Matemática Estadounidense, p. 151, ISBN 9780821826003.
- ^ Lo que significa que tiene un elemento menor yun elemento mayor .
- ^ Es decir, uno no tiene una situación como y siendo ambos cadenas máximas.
- ^ No contener cadenas descendentes arbitrariamente largas que comiencen en un elemento fijo, por supuesto, excluye cualquier cadena descendente infinita. Sin embargo, la primera condición es estrictamente más fuerte; el conjunto tiene cadenas arbitrariamente largas que descienden de , pero no tiene infinitas cadenas descendentes.
- ^ 'Teoría de celosía', Am. Matemáticas. Soc., Publicaciones del coloquio, Vol. 25, 1967, p.5
- ^ Ver referencia [2], p.722.
Referencias
- Stanley, Richard (1997). Combinatoria enumerativa (vol.1, Cambridge Studies in Advanced Mathematics 49) . Prensa de la Universidad de Cambridge . 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: The Rota Way . Cambridge, Reino Unido (et al.): Cambridge University Press. ISBN 978-0-521-73794-4.