Chromatic symmetric function

The chromatic symmetric function is a symmetric function invariant of graphs studied in algebraic graph theory, a branch of mathematics. It is the weight generating function for proper graph colorings, and was originally introduced by Richard Stanley as a generalization of the chromatic polynomial of a graph. ^[1]

Definition

For a finite graph ${\displaystyle G=(V,E)}$ with vertex set ${\displaystyle V=\{v_{1},v_{2},\ldots ,v_{n}\}}$, a vertex coloring is a function ${\displaystyle \kappa :V\to C}$ where ${\displaystyle C}$ is a set of colors. A vertex coloring is called proper if all adjacent vertices are assigned distinct colors (i.e., ${\displaystyle \{i,j\}\in E\implies \kappa (i)\neq \kappa (j)}$). The chromatic symmetric function denoted ${\displaystyle X_{G}(x_{1},x_{2},\ldots )}$ is defined to be the weight generating function of proper vertex colorings of ${\displaystyle G}$: ^{[1] [2]} $${\displaystyle X_{G}(x_{1},x_{2},\ldots ):=\sum _{\underset {\text{proper}}{\kappa :V\to \mathbb {N} }}x_{\kappa (v_{1})}x_{\kappa (v_{2})}\cdots x_{\kappa (v_{n})}}$$

Examples

For ${\displaystyle \lambda }$ a partition, let ${\displaystyle m_{\lambda }}$ be the monomial symmetric polynomial associated to ${\displaystyle \lambda }$.

Example 1: complete graphs

Consider the complete graph ${\displaystyle K_{n}}$ on ${\displaystyle n}$ vertices:

• There are ${\displaystyle n!}$ ways to color ${\displaystyle K_{n}}$ with exactly ${\displaystyle n}$ colors yielding the term ${\displaystyle n!x_{1}\cdots x_{n}}$
• Since every pair of vertices in ${\displaystyle K_{n}}$ is adjacent, it can be properly colored with no fewer than ${\displaystyle n}$ colors.

Thus, ${\displaystyle X_{K_{n}}(x_{1},\ldots ,x_{n})=n!x_{1}\cdots x_{n}=n!m_{(1,\ldots ,1)}}$

Example 2: a path graph

Consider the path graph ${\displaystyle P_{3}}$ of length ${\displaystyle 3}$:

• There are ${\displaystyle 3!}$ ways to color ${\displaystyle P_{3}}$ with exactly ${\displaystyle 3}$ colors, yielding the term ${\displaystyle 6x_{1}x_{2}x_{3}}$
• For each pair of colors, there are ${\displaystyle 2}$ ways to color ${\displaystyle P_{3}}$ yielding the terms ${\displaystyle x_{i}^{2}x_{j}}$ and ${\displaystyle x_{i}x_{j}^{2}}$ for ${\displaystyle i\neq j}$

Altogether, the chromatic symmetric function of ${\displaystyle P_{3}}$ is then given by: ^[2] $${\displaystyle X_{P_{3}}(x_{1},x_{2},x_{3})=6x_{1}x_{2}x_{3}+x_{1}^{2}x_{2}+x_{1}x_{2}^{2}+x_{1}^{2}x_{3}+x_{1}x_{3}^{2}+x_{2}^{2}x_{3}+x_{2}x_{3}^{2}=6m_{(1,1,1)}+m_{(1,2)}}$$

Properties

• Let ${\displaystyle \chi _{G}}$ be the chromatic polynomial of ${\displaystyle G}$, so that ${\displaystyle \chi _{G}(k)}$ is equal to the number of proper vertex colorings of ${\displaystyle G}$ using at most ${\displaystyle k}$ distinct colors. The values of ${\displaystyle \chi _{G}}$ can then be computed by specializing the chromatic symmetric function, setting the first ${\displaystyle k}$ variables ${\displaystyle x_{i}}$ equal to ${\displaystyle 1}$ and the remaining variables equal to ${\displaystyle 0}$: ^[1] $${\displaystyle X_{G}(1^{k})=X_{G}(1,\ldots ,1,0,0,\ldots )=\chi _{G}(k)}$$
• If ${\displaystyle G\amalg H}$ is the disjoint union of two graphs, then the chromatic symmetric function for ${\displaystyle G\amalg H}$ can be written as a product of the corresponding functions for ${\displaystyle G}$ and ${\displaystyle H}$: ^[1] $${\displaystyle X_{G\amalg H}=X_{G}\cdot X_{H}}$$
• A stable partition${\displaystyle \pi }$ of ${\displaystyle G}$ is defined to be a set partition of vertices ${\displaystyle V}$ such that each block of ${\displaystyle \pi }$ is an independent set in ${\displaystyle G}$. The type of a stable partition ${\displaystyle {\text{type}}(\pi )}$ is the partition consisting of parts equal to the sizes of the connected components of the vertex induced subgraphs. For a partition ${\displaystyle \lambda \vdash n}$, let ${\displaystyle z_{\lambda }}$ be the number of stable partitions of ${\displaystyle G}$ with ${\displaystyle {\text{type}}(\pi )=\lambda =\langle 1^{r_{1}}2^{r2}\ldots \rangle }$. Then, ${\displaystyle X_{G}}$ expands into the augmented monomial symmetric functions, ${\displaystyle {\tilde {m}}_{\lambda }:=r_{1}!r_{2}!\cdots m_{\lambda }}$ with coefficients given by the number of stable partitions of ${\displaystyle G}$: ^[1] $${\displaystyle X_{G}=\sum _{\lambda \vdash n}z_{\lambda }{\tilde {m}}_{\lambda }}$$
• Let ${\displaystyle p_{\lambda }}$ be the power-sum symmetric function associated to a partition ${\displaystyle \lambda }$. For ${\displaystyle S\subseteq E}$, let ${\displaystyle \lambda (S)}$ be the partition whose parts are the vertex sizes of the connected components of the edge-induced subgraph of ${\displaystyle G}$ specified by ${\displaystyle S}$. The chromatic symmetric function can be expanded in the power-sum symmetric functions via the following formula: ^[1] $${\displaystyle X_{G}=\sum _{S\subseteq E}(-1)^{|S|}p_{\lambda (S)}}$$
• Let ${\textstyle X_{G}=\sum _{\lambda \vdash n}c_{\lambda }e_{\lambda }}$ be the expansion of ${\displaystyle X_{G}}$ in the basis of elementary symmetric functions ${\displaystyle e_{\lambda }}$. Let ${\displaystyle {\text{sink}}(G,s)}$ be the number of acyclic orientations on the graph ${\displaystyle G}$ which contain exactly ${\displaystyle s}$ sinks. Then we have the following formula for the number of sinks: ^[1] $${\displaystyle {\text{sink}}(G,s)=\sum _{\underset {l(\lambda )=s}{\lambda \vdash n}}c_{\lambda }}$$

Open problems

There are a number of outstanding questions regarding the chromatic symmetric function which have received substantial attention in the literature surrounding them.

(3+1)-free conjecture

For a partition ${\displaystyle \lambda }$, let ${\displaystyle e_{\lambda }}$ be the elementary symmetric function associated to ${\displaystyle \lambda }$.

A partially ordered set ${\displaystyle P}$ is called ${\displaystyle (3+1)}$-free if it does not contain a subposet isomorphic to the direct sum of the ${\displaystyle 3}$ element chain and the ${\displaystyle 1}$ element chain. The incomparability graph ${\displaystyle {\text{inc}}(P)}$ of a poset ${\displaystyle P}$ is the graph with vertices given by the elements of ${\displaystyle P}$ which includes an edge between two vertices if and only if their corresponding elements in ${\displaystyle P}$ are incomparable.

Conjecture (Stanley–Stembridge) Let ${\displaystyle G}$ be the incomparability graph of a ${\textstyle (3+1)}$-free poset, then ${\textstyle X_{G}}$ is ${\displaystyle e}$-positive. ^[1]

A weaker positivity result is known for the case of expansions into the basis of Schur functions.

Theorem (Gasharov) Let ${\displaystyle G}$ be the incomparability graph of a ${\textstyle (3+1)}$-free poset, then ${\textstyle X_{G}}$ is ${\displaystyle s}$-positive. ^[3]

In the proof of the theorem above, there is a combinatorial formula for the coefficients of the Schur expansion given in terms of ${\displaystyle P}$-tableaux which are a generalization of semistandard Young tableaux instead labelled with the elements of ${\displaystyle P}$.

Generalizations

There are a number of generalizations of the chromatic symmetric function:

• There is a categorification of the invariant into a homology theory which is called chromatic symmetric homology. ^[4] This homology theory is known to be a stronger invariant than the chromatic symmetric function alone. ^[5] The chromatic symmetric function can also be defined for vertex-weighted graphs, ^[6] where it satisfies a deletion-contraction property analogous to that of the chromatic polynomial. If the theory of chromatic symmetric homology is generalized to vertex-weighted graphs as well, this deletion-contraction property lifts to a long exact sequence of the corresponding homology theory. ^[7]
• There is also a quasisymmetric refinement of the chromatic symmetric function which can be used to refine the formulae expressing ${\displaystyle X_{G}}$ in terms of Gessel's basis of fundamental quasisymmetric functions and the expansion in the basis of Schur functions. ^[8] Fixing an order for the set of vertices, the ascent set of a proper coloring ${\displaystyle \kappa }$ is defined to be ${\displaystyle {\text{asc}}(\kappa )=\{\{i,j\}\in E:i<j{\text{ and }}\kappa (i)<\kappa (j)\}}$. The chromatic quasisymmetric function of a graph ${\displaystyle G}$ is then defined to be: ^[8] $${\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})}}$$

See also

• Chromatic polynomial
• Symmetric function

References

1. Stanley, R.P. (1995). "A Symmetric Function Generalization of the Chromatic Polynomial of a Graph". Advances in Mathematics . 111 (1): 166–194. doi: 10.1006/aima.1995.1020 . ISSN   0001-8708.
2. Saliola, Franco (October 15, 2022). "Lectures on Symmetric Functions with a view towards Hessenberg varieties — Draft" (PDF). Archived (PDF) from the original on October 18, 2022. Retrieved April 27, 2024.
3. Gasharov, Vesselin (1996). "Incomparability graphs of (3+1)-free posets are s-positive" (PDF). Discrete Mathematics . 157 (1–3): 193–197. doi: 10.1016/S0012-365X(96)83014-7 .
4. Sazdanovic, Radmila; Yip, Martha (2018-02-01). "A categorification of the chromatic symmetric function". Journal of Combinatorial Theory . Series A. 154: 218–246. arXiv: 1506.03133 . doi: 10.1016/j.jcta.2017.08.014 . ISSN   0097-3165.
5. Chandler, Alex; Sazdanovic, Radmila; Stella, Salvatore; Yip, Martha (2023-09-01). "On the strength of chromatic symmetric homology for graphs". Advances in Applied Mathematics. 150 102559. arXiv: 1911.13297 . doi:10.1016/j.aam.2023.102559. ISSN   0196-8858.
6. Crew, Logan; Spirkl, Sophie (2020). "A Deletion-Contraction Relation for the Chromatic Symmetric Function". European Journal of Combinatorics . 89 103143. arXiv: 1910.11859 . doi:10.1016/j.ejc.2020.103143.
7. Ciliberti, Azzurra (2024-01-01). "A deletion–contraction long exact sequence for chromatic symmetric homology". European Journal of Combinatorics . 115 103788. arXiv: 2211.00699 . doi:10.1016/j.ejc.2023.103788. ISSN   0195-6698.
8. Shareshian, John; Wachs, Michelle L. (June 4, 2016). "Chromatic quasisymmetric functions". Advances in Mathematics . 295: 497–551. arXiv: 1405.4629 . doi: 10.1016/j.aim.2015.12.018 . ISSN   0001-8708.

Further reading

• Blasiak, Jonah; Eriksson, Holden; Pylyavskyy, Pavlo; Siegl, Isaiah (2022). "Noncommutative Schur functions for posets". arXiv: 2211.03967 [math.CO].
• Chow, Timothy Y. (1999). "Descents, Quasi-Symmetric Functions, Robinson-Schensted for Posets, and the Chromatic Symmetric Function". Journal of Algebraic Combinatorics. 10 (3): 227–240. doi:10.1023/A:1018719315718.
• Harada, Megumi; Precup, Martha E. (2019). "The cohomology of abelian Hessenberg varieties and the Stanley–Stembridge conjecture". Algebraic Combinatorics. 2 (6): 1059–1108. arXiv: 1709.06736 . doi:10.5802/alco.76.
• Hwang, Byung-Hak (2024). "Chromatic quasisymmetric functions and noncommutative ${\displaystyle P}$-symmetric functions". Transactions of the American Mathematical Society. 377 (4): 2855–2896. arXiv: 2208.09857 . doi:10.1090/tran/9096.
• Shareshian, John; Wachs, Michelle L. (2012). "Chromatic quasisymmetric functions and Hessenberg varieties". Configuration Spaces. pp. 433–460. arXiv: 1106.4287 . doi:10.1007/978-88-7642-431-1_20. ISBN   978-88-7642-430-4.