Función simétrica cromática

La función simétrica cromática es una función simétrica invariante de grafos estudiada en la teoría algebraica de grafos , una rama de las matemáticas . Es la función generadora de pesos para coloraciones de grafos propias y fue introducida originalmente por Richard Stanley como una generalización del polinomio cromático de un grafo. ^{[ 1 ]}

Para un grafo finito${\displaystyle G=(V,E)}$con conjunto de vértices${\displaystyle V=\{v_{1},v_{2},\ldots,v_{n}\}}$, una coloración de vértices es una función${\displaystyle \kappa :V\a C}$dónde${\displaystyle C}$es un conjunto de colores. Una coloración de vértices se llama propia si a todos los vértices adyacentes se les asignan colores distintos (es decir,${\displaystyle \{i,j\}\in E\implica \kappa (i)\neq \kappa (j)}$). La función simétrica cromática denotada${\displaystyle X_{G}(x_{1},x_{2},\ldots )}$se define como la función generadora de pesos de coloraciones de vértices propias de${\displaystyle G}$: ^{[ 1 ] [ 2 ]}$${\displaystyle X_{G}(x_{1},x_{2},\ldots ):=\sum _{\underset {\text{propio}}{\kappa :V\to \mathbb {N} }}x_{\kappa (v_{1})}x_{\kappa (v_{2})}\cdots x_{\kappa (v_{n})}}$$

Para${\displaystyle \lambda }$una partición , sea${\displaystyle m_{\lambda }}$sea ​​el polinomio simétrico monomial asociado a${\displaystyle \lambda }$.

• Dejar${\displaystyle \chi _{G}}$sea ​​el polinomio cromático de${\displaystyle G}$, de modo que${\displaystyle \chi _{G}(k)}$es igual al número de coloraciones de vértices propias de${\displaystyle G}$utilizando como máximo${\displaystyle k}$colores distintos. Los valores de${\displaystyle \chi _{G}}$Luego se puede calcular especializando la función simétrica cromática, estableciendo el primero${\displaystyle k}$variables${\displaystyle x_{i}}$igual a${\displaystyle 1}$y las variables restantes son iguales a${\displaystyle 0}$: ^{[ 1 ]}$${\displaystyle X_{G}(1^{k})=X_{G}(1,\ldots ,1,0,0,\ldots )=\chi _{G}(k)}$$
• Si${\displaystyle G\amalg H}$es la unión disjunta de dos grafos, entonces la función simétrica cromática para${\displaystyle G\amalg H}$se puede escribir como un producto de las funciones correspondientes para${\displaystyle G}$y${\displaystyle H}$: ^{[ 1 ]}$${\displaystyle X_{G\amalg H}=X_{G}\cdot X_{H}}$$
• Una partición estable${\displaystyle \pi }$de${\displaystyle G}$se define como una partición de conjuntos de vértices${\displaystyle V}$de tal manera que cada bloque de${\displaystyle \pi }$es un conjunto independiente en${\displaystyle G}$. El tipo de partición estable${\displaystyle {\text{type}}(\pi )}$es la partición que consta de partes iguales a los tamaños de las componentes conexas de los subgrafos inducidos por vértices. Para una partición${\displaystyle \lambda \vdash n}$, dejar${\displaystyle z_{\lambda }}$sea ​​el número de particiones estables de${\displaystyle G}$con${\displaystyle {\text{tipo}}(\pi )=\lambda =\langle 1^{r_{1}}2^{r2}\ldots \rangle }$. Entonces,${\displaystyle X_{G}}$se expande en las funciones simétricas monomiales aumentadas,${\displaystyle {\tilde {m}}_{\lambda }:=r_{1}!r_{2}!\cdots m_{\lambda }}$con coeficientes dados por el número de particiones estables de${\displaystyle G}$: ^{[ 1 ]}$${\displaystyle X_{G}=\sum _{\lambda \vdash n}z_{\lambda }{\tilde {m}}_{\lambda }}$$
• Dejar${\displaystyle p_{\lambda }}$sea ​​la función simétrica de suma de potencias asociada a una partición${\displaystyle \lambda }$. Para${\displaystyle S\subseteq E}$, dejar${\displaystyle \lambda (S)}$sea ​​la partición cuyas partes son los tamaños de vértice de las componentes conexas del subgrafo inducido por aristas de${\displaystyle G}$especificado por${\displaystyle S}$. La función simétrica cromática se puede expandir en funciones simétricas de suma de potencias mediante la siguiente fórmula: ^{[ 1 ]}$${\displaystyle X_{G}=\sum _{S\subseteq E}(-1)^{|S|}p_{\lambda (S)}}$$
• Dejar${\textstyle X_{G}=\sum _{\lambda \vdash n}c_{\lambda }e_{\lambda }}$ser la expansión de${\displaystyle X_{G}}$en la base de funciones simétricas elementales${\displaystyle e_{\lambda }}$. Dejar${\displaystyle {\text{sink}}(G,s)}$sea ​​el número de orientaciones acíclicas en el gráfico${\displaystyle G}$que contienen exactamente${\displaystyle s}$sumideros. Entonces tenemos la siguiente fórmula para el número de sumideros: ^{[ 1 ]}$${\displaystyle {\text{sink}}(G,s)=\sum _{\underset {l(\lambda )=s}{\lambda \vdash n}}c_{\lambda }}$$

Existen varias cuestiones relativas a la función simétrica cromática que han recibido una atención considerable en la literatura especializada al respecto.

Existen varias generalizaciones de la función simétrica cromática:

• Existe una categorización del invariante en una teoría de homología llamada homología simétrica cromática. ^{[ 5 ]} Se sabe que esta teoría de homología es un invariante más fuerte que la función simétrica cromática por sí sola. ^{[ 6 ]} La función simétrica cromática también puede definirse para grafos ponderados por vértices, ^{[ 7 ]} donde satisface una propiedad de eliminación-contracción análoga a la del polinomio cromático. Si la teoría de la homología simétrica cromática se generaliza también a grafos ponderados por vértices, esta propiedad de eliminación-contracción se extiende a una larga secuencia exacta de la teoría de homología correspondiente. ^{[ 8 ]}
• También existe un refinamiento cuasi-simétrico de la función simétrica cromática que puede utilizarse para refinar las fórmulas que expresan${\displaystyle X_{G}}$en términos de la base de Gessel de funciones cuasisimétricas fundamentales y la expansión en la base de funciones de Schur. ^{[ 9 ]} Fijando un orden para el conjunto de vértices, el conjunto de ascenso de una coloración propia${\displaystyle \kappa }$se define como${\displaystyle {\text{asc}}(\kappa )=\{\{i,j\}\in E:i<j{\text{ and }}\kappa (i)<\kappa (j)\}}$La función cuasisimétrica cromática de un gráfico${\displaystyle G}$entonces se define como: ^{[ 9 ]}$${\displaystyle X_{G}(x_{1},x_{2},\ldots ;t):=\sum _{\underset {\text{proper}}{\kappa :V\to \mathbb {N} }}t^{|asc(\kappa )|}x_{\kappa (v_{1})}\cdots x_{\kappa (v_{n})}}$$

• polinomio cromático
• Función simétrica

• Blasiak, Jonás; Eriksson, Holden; Pylyavskyy, Pavlo; Siegl, Isaías (2022). "Funciones de Schur no conmutativas para posets". arXiv : 2211.03967 [ matemáticas.CO ].
• Chow, Timothy Y. (1999). "Descensos, funciones cuasi-simétricas, Robinson-Schensted para conjuntos parcialmente ordenados y la función simétrica cromática". Journal of Algebraic Combinatorics . 10 (3): 227– 240. doi : 10.1023/A:1018719315718 .
• Harada, Megumi; Precup, Martha E. (2019). "La cohomología de las variedades de Hessenberg abelianas y la conjetura de Stanley-Stembridge". Combinatoria Algebraica . 2 (6): 1059– 1108. arXiv : 1709.06736 . doi : 10.5802/alco.76 .
• Hwang, Byung-Hak (2024). "Funciones cuasisimétricas cromáticas y no conmutativas${\displaystyle P}$-funciones simétricas". Transactions of the American Mathematical Society . 377 (4): 2855– 2896. arXiv : 2208.09857 . doi : 10.1090/tran/9096 .
• Shareshian, John; Wachs, Michelle L. (2012). «Funciones cuasisimétricas cromáticas y variedades de Hessenberg». Configuration Spaces . pp. 433–460 . arXiv : 1106.4287 . doi : 10.1007/978-88-7642-431-1_20 . ISBN  978-88-7642-430-4.