Hispanopedia Wiki
Articulo de referencia

polinomio de orden

El polinomio de orden es un polinomio estudiado en matemáticas, en particular en la teoría algebraica de grafos y la combinatoria algebraica . El polinomio de orden cuenta el nú...

Hispanopedia WikiContenido en espanolLectura gratuita

El polinomio de orden es un polinomio estudiado en matemáticas, en particular en la teoría algebraica de grafos y la combinatoria algebraica . El polinomio de orden cuenta el número de aplicaciones que preservan el orden de un poset a una cadena de longitudnorte{\displaystyle n}Estos mapas que preservan el orden fueron introducidos 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 dirección de Gian-Carlo Rota .

Definición

DejarPAG{\displaystyle P}ser un conjunto parcialmente ordenado finito conpag{\displaystyle p}elementos denotadosincógnita,y∈PAG{\displaystyle x,y\in P}y dejar[norte]={1<2<…<norte}{\displaystyle [n]=\{1<2<\ldots <n\}}ser una cadena connorte{\displaystyle n}elementos. Un mapaϕ:PAG→[norte]{\displaystyle \phi :P\a [n]}es que se preserva el orden siincógnita≤y{\displaystyle x\leq y}implicaϕ(incógnita)≤ϕ(y){\displaystyle \phi (x)\leq \phi (y)}El número de tales mapas crece polinómicamente connorte{\displaystyle n}y la función que cuenta su número es el polinomio de ordenΩ(norte)=Ω(PAG,norte){\displaystyle \Omega (n)=\Omega (P,n)}.

De manera similar, podemos definir un polinomio de orden que cuente el número de mapas que preservan estrictamente el orden.ϕ:PAG→[norte]{\displaystyle \phi :P\a [n]}, significadoincógnita<y{\displaystyle x<y}implicaϕ(incógnita)<ϕ(y){\displaystyle \phi (x)<\phi (y)}El número de tales mapas es el polinomio de orden estricto .Ω∘(norte)=Ω∘(PAG,norte){\displaystyle \Omega ^{\circ }\!(n)=\Omega ^{\circ }\!(P,n)}. [ 1 ]

AmbosΩ(norte){\displaystyle \Omega (n)}yΩ∘(norte){\displaystyle \Omega ^{\circ }\!(n)}tener títulopag{\displaystyle p}. Los mapas que preservan el orden generalizan las extensiones lineales dePAG{\displaystyle P}, las biyecciones que preservan el ordenϕ:PAG⟶∼[pag]{\displaystyle \phi :P{\stackrel {\sim }{\longrightarrow }}[p]}. De hecho, el coeficiente principal deΩ(norte){\displaystyle \Omega (n)}yΩ∘(norte){\displaystyle \Omega ^{\circ }\!(n)}es el número de extensiones lineales dividido porpag¡{\displaystyle p!}. [ 2 ]

Ejemplos

AlquilerPAG{\displaystyle P}ser una cadena depag{\displaystyle p}elementos, tenemos

Ω(norte)=(norte+pag−1pag)=((nortepag)){\displaystyle \Omega (n)={\binom {n+p-1}{p}}=\left(\!\left({n \atop p}\right)\!\right)} y Ω∘(norte)=(nortepag).{\displaystyle \Omega ^{\circ }(n)={\binom {n}{p}}.}

Solo existe una extensión lineal (la aplicación identidad ), y ambos polinomios tienen término principal.1pag¡nortepag{\displaystyle {\tfrac {1}{p!}}n^{p}}.

AlquilerPAG{\displaystyle P}ser una anticadena depag{\displaystyle p}elementos incomparables, tenemosΩ(norte)=Ω∘(norte)=nortepag{\displaystyle \Omega (n)=\Omega ^{\circ }(n)=n^{p}}. Dado que cualquier biyecciónϕ:PAG⟶∼[pag]{\displaystyle \phi :P{\stackrel {\sim }{\longrightarrow }}[p]}es (estrictamente) preservador del orden, haypag¡{\displaystyle p!}extensiones lineales, y ambos polinomios se reducen al término principal.pag¡pag¡nortepag=nortepag{\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 ]

Ω∘(norte)=(−1)|PAG|Ω(−norte).{\displaystyle \Omega ^{\circ }(n)=(-1)^{|P|}\Omega (-n).}

En el caso de quePAG{\displaystyle P}es una cadena, esto 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 ]

Conexiones con otros polinomios de conteo

polinomio cromático

El polinomio cromáticoPAG(GRAMO,norte){\displaystyle P(G,n)}cuenta el número de coloraciones propias de un grafo finitoGRAMO{\displaystyle G}connorte{\displaystyle n}Colores disponibles. Para una orientación acíclica.σ{\displaystyle \sigma }de los bordes deGRAMO{\displaystyle G}, existe un orden parcial "descendente" natural en los vérticesV(GRAMO){\displaystyle V(G)}implícito en las relaciones básicastú>v{\displaystyle u>v}cuando seatú→v{\displaystyle u\rightarrow v}es un borde dirigido deσ{\displaystyle \sigma }. (Por lo tanto, el diagrama de Hasse del poset es un subgrafo del grafo orientado)σ{\displaystyle \sigma }.) Decimosϕ:V(GRAMO)→[norte]{\displaystyle \phi :V(G)\rightarrow [n]}es compatible conσ{\displaystyle \sigma }siϕ{\displaystyle \phi }es que preserva el orden. Entonces tenemos

PAG(GRAMO,norte) = ∑σΩ∘(σ,norte),{\displaystyle P(G,n)\ =\ \sum _{\sigma }\Omega ^{\circ }\!(\sigma ,n),}

dóndeσ{\displaystyle \sigma }recorre todas las orientaciones acíclicas de G, consideradas como estructuras de poset. [ 5 ]

Orden politopo y polinomio de Ehrhart

El politopo de orden asocia un politopo con un orden parcial. Para un posetPAG{\displaystyle P}conpag{\displaystyle p}elementos, el politopo de ordenO(PAG){\displaystyle O(P)}es el conjunto de mapas que preservan el ordenF:PAG→[0,1]{\displaystyle f:P\to [0,1]}, dónde[0,1]={t∈R∣0≤t≤1}{\displaystyle [0,1]=\{t\in \mathbb {R} \mid 0\leq t\leq 1\}}es el intervalo unitario ordenado , un poset de cadena continua. [ 6 ] [ 7 ] De forma más geométrica, podemos enumerar los elementosPAG={incógnita1,…,incógnitapag}{\displaystyle P=\{x_{1},\ldots ,x_{p}\}}y identificar cualquier mapeoF:PAG→R{\displaystyle f:P\to \mathbb {R} }con el punto(F(incógnita1),…,F(incógnitapag))∈Rpag{\displaystyle (f(x_{1}),\ldots ,f(x_{p}))\in \mathbb {R} ^{p}}; entonces el politopo de orden es el conjunto de puntos(t1,…,tpag)∈[0,1]pag{\displaystyle (t_{1},\ldots ,t_{p})\in [0,1]^{p}}con ti≤tj{\displaystyle t_{i}\leq t_{j}}siincógnitai≤incógnitaj{\displaystyle x_{i}\leq x_{j}}. [ 2 ]

El polinomio de Ehrhart cuenta el número de puntos reticulares enteros dentro de las dilataciones de un politopo . Específicamente, consideremos la redL=Znorte{\displaystyle L=\mathbb {Z} ^{n}}y und{\displaystyle d}politopo -dimensionalK⊂Rd{\displaystyle K\subset \mathbb {R} ^{d}}con vértices enL{\displaystyle L}; luego definimos

L(K,norte)=#(norteK∩L),{\displaystyle L(K,n)=\#(nK\cap L),}

el número de puntos de la red ennorteK{\displaystyle nK}, la dilatación deK{\displaystyle K}por un escalar entero positivonorte{\displaystyle n}Ehrhart demostró que este es un polinomio racional de gradod{\displaystyle d}en la variablenorte{\displaystyle n}, proporcionóK{\displaystyle K}tiene vértices en la red. [ 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): [ 2 ] [ 9 ]

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

Esto es una consecuencia inmediata de las definiciones, considerando la incorporación de la(norte+1){\displaystyle (n{+}1)}-cadena poset[norte+1]={0<1<⋯<norte}⊂R{\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. 1 2 3 Stanley, Richard P. (1986). "Dos politopos de 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". Actas de la 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 homogéneas lineales". Combinatoria enumerativa. Volumen 1 (2.ª ed.). Nueva York: Cambridge University Press. ISBN  9781139206549OCLC 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". Order . 8 : 7–15 . doi : 10.1007/BF00385809 . S2CID 120532896 . 
  7. ↑ Brightwell, Graham; Winkler, Peter (1991). "Counting linear extensions". Order . 8 (3): 225– 242. doi : 10.1007/BF00383444 . S2CID 119697949 . 
  8. ↑ Beck, Matthias; Robins, Sinai (2015). Computing the continuous discretely . 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 ordenación" . Journal of Computer and System Sciences . 51 (3): 390– 399. doi : 10.1006/jcss.1995.1077 .