Orden polinomial

El polinomio de orden es un polinomio estudiado en matemáticas, en particular en la teoría de grafos algebraicos y la combinatoria algebraica . El polinomio de orden cuenta el número de aplicaciones que preservan el orden de un conjunto parcial a una cadena de longitud . Estas aplicaciones que preservan el orden fueron introducidas por primera vez por Richard P. Stanley mientras estudiaba estructuras ordenadas y particiones como estudiante de doctorado en la Universidad de Harvard en 1971 bajo la guía de Gian-Carlo Rota . ${\displaystyle n}$

Definición

Sea un conjunto de objetos finito con elementos denotados , y sea una cadena de elementos. Una función preserva el orden si implica . El número de dichas funciones crece de forma polinómica con , y la función que cuenta su número es el polinomio de orden . ${\displaystyle P}$ ${\displaystyle p}$ ${\displaystyle x,y\in P}$ ${\displaystyle [n]=\{1<2<\ldots <n\}}$ ${\displaystyle n}$ ${\displaystyle \phi :P\to [n]}$ ${\displaystyle x\leq y}$ ${\displaystyle \phi (x)\leq \phi (y)}$ ${\displaystyle n}$ ${\displaystyle \Omega (n)=\Omega (P,n)}$

De manera similar, podemos definir un polinomio de orden que cuente el número de aplicaciones que preservan estrictamente el orden , es decir, implica . El número de dichas aplicaciones es el polinomio de orden estricto . ^[1] ${\displaystyle \phi :P\to [n]}$ ${\displaystyle x<y}$ ${\displaystyle \phi (x)<\phi (y)}$ ${\displaystyle \Omega ^{\circ }\!(n)=\Omega ^{\circ }\!(P,n)}$

Tanto y tienen grado . Las funciones 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 . ^[2] ${\displaystyle \Omega (n)}$ ${\displaystyle \Omega ^{\circ }\!(n)}$ ${\displaystyle p}$ ${\displaystyle P}$ ${\displaystyle \phi :P{\stackrel {\sim }{\longrightarrow }}[p]}$ ${\displaystyle \Omega (n)}$ ${\displaystyle \Omega ^{\circ }\!(n)}$ ${\displaystyle p!}$

Ejemplos

Dejando ser una cadena de elementos, tenemos ${\displaystyle P}$ ${\displaystyle p}$

${\displaystyle \Omega (n)={\binom {n+p-1}{p}}=\left(\!\left({n \atop p}\right)\!\right)}$ y ${\displaystyle \Omega ^{\circ }(n)={\binom {n}{p}}.}$

Sólo hay una extensión lineal (la función identidad) y ambos polinomios tienen como término principal . ${\displaystyle {\tfrac {1}{p!}}n^{p}}$

Si se deja que sea una anticadena de elementos incomparables, tenemos . Como cualquier biyección preserva (estrictamente) el orden, hay extensiones lineales y ambos polinomios se reducen al término principal . ${\displaystyle P}$ ${\displaystyle p}$ ${\displaystyle \Omega (n)=\Omega ^{\circ }(n)=n^{p}}$ ${\displaystyle \phi :P{\stackrel {\sim }{\longrightarrow }}[p]}$ ${\displaystyle p!}$ ${\displaystyle {\tfrac {p!}{p!}}n^{p}=n^{p}}$

Teorema de reciprocidad

Existe una relación entre los mapas que preservan estrictamente el orden y los mapas que preservan el orden: ^[3]

${\displaystyle \Omega ^{\circ }(n)=(-1)^{|P|}\Omega (-n).}$

En el caso de que se trate de una cadena, se recupera la identidad binomial negativa . Existen 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 . ^[4] ${\displaystyle P}$

Conexiones con otros polinomios de conteo

Polinomio cromático

El polinomio cromático cuenta el número de coloraciones propias de un grafo finito con colores disponibles. Para una orientación acíclica de las aristas de , existe un orden parcial "corriente abajo" natural en los vértices implícito en las relaciones básicas siempre que sea una arista dirigida de . (Por lo tanto, el diagrama de Hasse del conjunto parcial es un subgrafo del grafo orientado ). Decimos que es compatible con si preserva el orden. Entonces tenemos ${\displaystyle P(G,n)}$ ${\displaystyle G}$ ${\displaystyle n}$ ${\displaystyle \sigma }$ ${\displaystyle G}$ ${\displaystyle V(G)}$ ${\displaystyle u>v}$ ${\displaystyle u\rightarrow v}$ ${\displaystyle \sigma }$ ${\displaystyle \sigma }$ ${\displaystyle \phi :V(G)\rightarrow [n]}$ ${\displaystyle \sigma }$ ${\displaystyle \phi }$

${\displaystyle P(G,n)\ =\ \sum _{\sigma }\Omega ^{\circ }\!(\sigma ,n),}$

donde se ejecuta sobre todas las orientaciones acíclicas de G, consideradas como estructuras poset. ^[5] ${\displaystyle \sigma }$

Orden politopo y polinomio de Ehrhart

El politopo de orden asocia un politopo con un orden parcial. Para un conjunto parcial con elementos, el politopo de orden es el conjunto de funciones que preservan el orden , donde es el intervalo unitario ordenado, un conjunto parcial de cadena continua. ^{[6] [7]} De manera más geométrica, podemos enumerar los elementos , e identificar cualquier función con el punto ; entonces el politopo de orden es el conjunto de puntos con si . ^[2] ${\displaystyle P}$ ${\displaystyle p}$ ${\displaystyle O(P)}$ ${\displaystyle f:P\to [0,1]}$ ${\displaystyle [0,1]=\{t\in \mathbb {R} \mid 0\leq t\leq 1\}}$ ${\displaystyle P=\{x_{1},\ldots ,x_{p}\}}$ ${\displaystyle f:P\to \mathbb {R} }$ ${\displaystyle (f(x_{1}),\ldots ,f(x_{p}))\in \mathbb {R} ^{p}}$ ${\displaystyle (t_{1},\ldots ,t_{p})\in [0,1]^{p}}$ ${\displaystyle t_{i}\leq t_{j}}$ ${\displaystyle x_{i}\leq x_{j}}$

El polinomio de Ehrhart cuenta la cantidad de puntos reticulares enteros dentro de las dilataciones de un politopo . Específicamente, considere la red y un politopo de dimensión con vértices en ; luego definimos ${\displaystyle L=\mathbb {Z} ^{n}}$ ${\displaystyle d}$ ${\displaystyle K\subset \mathbb {R} ^{d}}$ ${\displaystyle L}$

${\displaystyle L(K,n)=\#(nK\cap L),}$

el número de puntos de la red en , la dilatación de por un escalar entero positivo . Ehrhart demostró que este es un polinomio racional de grado en la variable , siempre que tenga vértices en la red. ^[8] ${\displaystyle nK}$ ${\displaystyle K}$ ${\displaystyle n}$ ${\displaystyle d}$ ${\displaystyle n}$ ${\displaystyle K}$

De hecho, el polinomio de Ehrhart de un politopo de orden es igual al polinomio de orden del poset original (con un argumento desplazado): ^{[2] [9]}

${\displaystyle L(O(P),n)\ =\ \Omega (P,n{+}1).}$

Esta es una consecuencia inmediata de las definiciones, considerando la incrustación del conjunto poset de cadena . ${\displaystyle (n{+}1)}$ ${\displaystyle [n{+}1]=\{0<1<\cdots <n\}\subset \mathbb {R} }$

Referencias

1. Stanley, Richard P. (1972). Estructuras ordenadas y particiones . Providence, Rhode Island: American Mathematical Society.
2. Stanley, Richard P. (1986). "Dos politopos poset". Geometría discreta y computacional . 1 : 9–23. doi : 10.1007/BF02187680 .
3. 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.
4. Stanley, Richard P. (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  .
5. Stanley, Richard P. (1973). "Orientaciones acíclicas de grafos". Matemáticas discretas . 5 (2): 171–178. doi :10.1016/0012-365X(73)90108-8.
6. Karzanov, Alexander; Khachiyan, Leonid (1991). "Sobre la conductancia de las cadenas de Markov de orden ordinal". Orden . 8 : 7–15. doi :10.1007/BF00385809. S2CID  120532896.
7. Brightwell, Graham; Winkler, Peter (1991). "Conteo de extensiones lineales". Orden . 8 (3): 225–242. doi :10.1007/BF00383444. S2CID  119697949.
8. Beck, Matthias; Robins, Sinai (2015). Cálculo de la función continua de forma discreta . Nueva York: Springer. pp. 64–72. ISBN 978-1-4939-2968-9.
9. Linial, Nathan (1984). "El límite teórico de la información es bueno para la fusión". SIAM J. Comput . 13 (4): 795–801. doi :10.1137/0213049.
   Kahn, Jeff; Kim, Jeong Han (1995). "Entropía y ordenamiento". Revista de Ciencias de la Computación y Sistemas . 51 (3): 390–399. doi : 10.1006/jcss.1995.1077 .