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 $G=(V,E)$ with vertex set $V=\{v_{1},v_{2},\ldots ,v_{n}\}$ , a vertex coloring is a function $\kappa :V\to C$ where $C$ is a set of colors. A vertex coloring is called proper if all adjacent vertices are assigned distinct colors (i.e., $\{i,j\}\in E\implies \kappa (i)\neq \kappa (j)$ ). The chromatic symmetric function denoted $X_{G}(x_{1},x_{2},\ldots )$ is defined to be the weight generating function of proper vertex colorings of $G$ :^[1]^[2] $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 $\lambda$ a partition, let $m_{\lambda }$ be the monomial symmetric polynomial associated to $\lambda$ .

Example 1: complete graphs

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

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

Thus, $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 $P_{3}$ of length $3$ :

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

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

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

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

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

Theorem (Gasharov) Let $G$ be the incomparability graph of a ${\textstyle (3+1)}$ -free poset, then ${\textstyle X_{G}}$ is $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 $P$ -tableaux which are a generalization of semistandard Young tableaux instead labelled with the elements of $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 $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 $\kappa$ is defined to be ${\text{asc}}(\kappa )=\{\{i,j\}\in E:i<j{\text{ and }}\kappa (i)<\kappa (j)\}$ . The chromatic quasisymmetric function of a graph $G$ is then defined to be:^[8] $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})}$

References

^ ^a ^b ^c ^d ^e ^f ^g ^h 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.
^ ^a ^b 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.
^ 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.
^ 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.
^ 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.
^ 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.
^ 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.
^ ^a ^b 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.