Polinomio de orden

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 aplicaciones 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 y particiones ordenadas como doctorado. Estudiante en la Universidad de Harvard en 1971 bajo la dirección de Gian-Carlo Rota . ${\displaystyle n}$

Definición

Sea un poset finito con elementos denotados y sea una cadena de elementos. Un mapa conserva el orden si implica . El número de tales aplicaciones crece polinomialmente 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 , lo que significa que implica . El número de tales 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)}$

Ambos y tienen título . 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 . ^[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 (el mapeo de identidad) y ambos polinomios tienen un término principal . ${\displaystyle {\tfrac {1}{p!}}n^{p}}$

Dejando de ser una anticadena de elementos incomparables, tenemos . Dado que 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 mapas que preservan estrictamente el orden y mapas que preservan el orden: ^[3]

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

En el caso de que sea 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 . ^[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 gráfico finito con colores disponibles. Para una orientación acíclica de las aristas de , existe un orden parcial natural "aguas abajo" en los vértices implicados por las relaciones básicas siempre que haya una arista dirigida de . (Por lo tanto, el diagrama de Hasse del poset es un subgrafo del grafo orientado ). Decimos que es compatible con si preserva el orden. Entonces nosotros 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 recorre todas las orientaciones acíclicas de G, consideradas estructuras poset. ^[5] ${\displaystyle \sigma }$

Orden politopo y polinomio de Ehrhart

El politopo de orden asocia un politopo con un orden parcial. Para un poset con elementos, el politopo de orden es el conjunto de mapas que conservan el orden , donde es el intervalo unitario ordenado, un poset de cadena continua. ^{[6] [7]} Más geométricamente, podemos enumerar los elementos e identificar cualquier mapeo con el punto ; entonces el politopo de orden es el conjunto de puntos con if . ^[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 el número de puntos enteros de la red dentro de las dilataciones de un politopo . Específicamente, considere la red y el politopo adimensional con vértices en ; entonces 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 incorporación del poset cadena . ${\displaystyle (n{+}1)}$ ${\displaystyle [n{+}1]=\{0<1<\cdots <n\}\subset \mathbb {R} }$

Referencias

1. Stanley, Richard P. (1972). Estructuras y tabiques ordenados . Providence, Rhode Island: Sociedad Matemática Estadounidense.
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áticas Combinatorias y sus Aplicaciones. : 421–427.
4. Stanley, Richard P. (2012). "4.5.14 Teorema de reciprocidad para ecuaciones diofánticas lineales homogéneas". Combinatoria enumerativa. Volumen 1 (2ª ed.). Nueva York: Cambridge University Press. ISBN 9781139206549. OCLC  777400915.
5. 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.
6. Karzanov, Alejandro; Khachiyan, Leonid (1991). "Sobre la conducta de las cadenas del orden de Markov". Orden . 8 : 7–15. doi :10.1007/BF00385809. S2CID  120532896.
7. Brightwell, Graham; Winkler, Peter (1991). "Contando extensiones lineales". Orden . 8 (3): 225–242. doi :10.1007/BF00383444. S2CID  119697949.
8. Beck, Matías; Robins, Sinaí (2015). Calcular la continua discretamente . Nueva York: Springer. págs. 64–72. ISBN 978-1-4939-2968-9.
9. Linial, Nathan (1984). "El límite de la teoría de la información es bueno para fusionar". SIAM J. Computación . 13 (4): 795–801. doi :10.1137/0213049.
   Kahn, Jeff; Kim, Jeong Han (1995). "Entropía y clasificación". Revista de Ciencias de la Computación y de Sistemas . 51 (3): 390–399. doi : 10.1006/jcss.1995.1077 .