El polinomio de orden es un polinomio estudiado en matemáticas, en particular en teoría de grafos algebraicos y combinatoria algebraica . El polinomio de orden cuenta el número de mapas que conservan el orden desde un poset hasta una cadena de longitud. Estos mapas que preservan el orden fueron introducidos por primera vez por Richard P. Stanley mientras estudiaba estructuras ordenadas y particiones como Ph.D. estudiante de la Universidad de Harvard en 1971 bajo la dirección de Gian-Carlo Rota .
Definición
Dejar ser un poset finito con elementos indicados , y deja ser una cadena elementos. Un mapa es preservar el orden si implica . El número de tales mapas crece polinomialmente con, y la función que cuenta su número es el polinomio de orden .
De manera similar, podemos definir un polinomio de orden que cuente el número de mapas que preservan estrictamente el orden, significado implica . El número de tales mapas es el polinomio de orden estricto . [1]
Ambas cosas y tener grado . Los mapas que preservan el orden generalizan las extensiones lineales de, las biyecciones que preservan el orden . De hecho, el coeficiente principal de y es el número de extensiones lineales dividido por .
Ejemplos de
Dejando ser una cadena de elementos, tenemos
y
Solo hay una extensión lineal (el mapeo de identidad), y ambos polinomios tienen un término principal .
Dejando ser un antichain de elementos incomparables, tenemos . Dado que cualquier biyección es (estrictamente) conservando el orden, hay extensiones lineales, y ambos polinomios se reducen al término principal .
Teorema de reciprocidad
Existe una relación entre mapas que preservan estrictamente el orden y mapas que preservan el orden: [2]
En el caso de que es una cadena, esta recupera la identidad binomial negativa . Hay resultados similares para el polinomio cromático y el polinomio de Ehrhart (ver más abajo), todos casos especiales del teorema de reciprocidad general de Stanley . [3]
Conexiones con otros polinomios de conteo
Polinomio cromático
El polinomio cromático cuenta el número de coloraciones adecuadas de un gráfico finito con Colores disponibles. Para una orientación acíclica de los bordes de , hay un orden parcial natural "descendente" en los vértices implícito en las relaciones básicas cuando sea es un borde dirigido de . (Por lo tanto, el diagrama de Hasse del poset es un subgrafo del grafo orientado.) Decimos es compatible con Si es preservar el orden. Entonces nosotros tenemos
dónde recorre todas las orientaciones acíclicas de G, consideradas como estructuras poset. [4]
Orden politopo y polinomio de Ehrhart
El orden politopo asocia un politopo con un orden parcial. Para un poset con elementos, el orden politopo es el conjunto de mapas que conservan el orden , dónde es el intervalo unitario ordenado, un poset de cadena continua. [5] [6] Más geométricamente, podemos enumerar los elementose identificar cualquier mapeo con el punto ; entonces el orden politopo es el conjunto de puntos con Si . [7]
El polinomio de Ehrhart cuenta el número de puntos reticulares enteros dentro de las dilataciones de un politopo . Específicamente, considere la celosía y un -politopo dimensional con vértices en ; entonces definimos
el número de puntos de celosía en , la dilatación de por un escalar entero positivo . Ehrhart demostró que este es un polinomio racional de grado en la variable , previsto tiene vértices en la celosía. [8]
De hecho, el polinomio de Ehrhart de un politopo de orden es igual al polinomio de orden del poset original (con un argumento desplazado): [7] [9]
Esta es una consecuencia inmediata de las definiciones, considerando la incorporación de la -poset cadena .
Referencias
- ^ Stanley, Richard P. (1972). Estructuras y particiones ordenadas . Providence, Rhode Island: Sociedad Matemática Estadounidense.
- ^ Stanley, Richard P. (1970). "Un polinomio de tipo cromático para conjuntos ordenados". Proc. Segunda Conferencia de Chapel Hill sobre matemática combinatoria y sus aplicaciones. : 421–427.
- ^ Stanley, Richard P., 1944- (2012). "4.5.14 Teorema de reciprocidad para ecuaciones diofánticas homogéneas lineales". Combinatoria enumerativa. Volumen 1 (2ª ed.). Nueva York: Cambridge University Press. ISBN 9781139206549. OCLC 777400915 .CS1 maint: varios nombres: lista de autores ( enlace )
- ^ Stanley, Richard P. (1973). "Orientaciones acíclicas de gráficos" . Matemáticas discretas . 5 (2): 171-178. doi : 10.1016 / 0012-365X (73) 90108-8 .
- ^ Karzanov, Alexander; Khachiyan, Leonid (1991). "Sobre la conductancia de las Cadenas de Orden de Markov". Orden . 8 : 7-15. doi : 10.1007 / BF00385809 . S2CID 120532896 .
- ^ Brightwell, Graham; Winkler, Peter (1991). "Contando extensiones lineales". Orden . 8 (3): 225–242. doi : 10.1007 / BF00383444 . S2CID 119697949 .
- ^ a b Stanley, Richard P. (1986). "Dos politopos poset" . Geometría discreta y computacional . 1 : 9-23. doi : 10.1007 / BF02187680 .
- ^ Beck, Matthias; Petirrojos, Sinaí (2015). Calcular lo continuo de forma discreta . Nueva York: Springer. págs. 64–72. ISBN 978-1-4939-2968-9.
- ^ Linial, Nathan (1984). "El límite de la teoría de la información es bueno para fusionar". SIAM J. Comput . 13 (4): 795–801. doi : 10.1137 / 0213049 .
Kahn, Jeff; Kim, Jeong Han (1995). "Entropía y ordenación" . Revista de Ciencias de la Computación y Sistemas . 51 : 390–399. doi : 10.1145 / 129712.129731 . ISBN 0897915119.