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.{{Cite journal |last=Stanley |first=R.P. |authorlink=Richard P. Stanley |date=1995 |title=A Symmetric Function Generalization of the Chromatic Polynomial of a Graph |journal=Advances in Mathematics |volume=111 |issue=1 |pages=166–194 |doi=10.1006/aima.1995.1020 |doi-access=free |issn=0001-8708}}

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$ :{{Cite web |last=Saliola |first=Franco |date=October 15, 2022 |title=Lectures on Symmetric Functions with a view towards Hessenberg varieties — Draft |url=https://www.birs.ca/workshops/2022/22w5143/files/Franco%20Saliola/Saliola-Lectures-on-Chromatic-Symmetric-Functions.pdf |url-status=live |archive-url=https://web.archive.org/web/20221018024159/https://www.birs.ca/workshops/2022/22w5143/files/Franco%20Saliola/Saliola-Lectures-on-Chromatic-Symmetric-Functions.pdf |archive-date=October 18, 2022 |access-date=April 27, 2024}} $X_G(x_1,x_2,\ldots):=\sum_{\underset{\text{proper}}{\kappa:V\to\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_1x_2x_3$
For each pair of colors, there are $2$ ways to color $P_3$ yielding the terms $x_i^2x_j$ and $x_ix_j^2$ for $i\neq j$

Altogether, the chromatic symmetric function of $P_3$ is then given by: $X_{P_3}(x_1,x_2,x_3) = 6x_1x_2x_3 + x_1^2x_2 + x_1x_2^2 + x_1^2x_3 + x_1x_3^2 + x_2^2x_3 + x_2x_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$ : $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$ : $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=\langle1^{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$ : $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: $X_G=\sum_{S\subseteq E}(-1)^$
S
p_{\lambda(S)}
Let $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: $\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 $(3+1)$ -free poset, then $X_G$ is $e$ -positive.

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 $(3+1)$ -free poset, then $X_G$ is $s$ -positive.{{Cite journal |last=Gasharov |first=Vesselin |date=1996 |title=Incomparability graphs of (3+1)-free posets are s-positive |url=https://core.ac.uk/download/pdf/82067232.pdf |journal=Discrete Mathematics |volume=157 | issue=1–3 |pages=193–197 |doi=10.1016/S0012-365X(96)83014-7 |doi-access=free}}

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.{{Cite journal |last1=Sazdanovic |first1=Radmila |last2=Yip |first2=Martha |date=2018-02-01 |title=A categorification of the chromatic symmetric function |journal=Journal of Combinatorial Theory |series=Series A |volume=154 |pages=218–246 |doi=10.1016/j.jcta.2017.08.014 |doi-access=free |issn=0097-3165|arxiv=1506.03133 }} This homology theory is known to be a stronger invariant than the chromatic symmetric function alone.{{Cite journal |last1=Chandler |first1=Alex |last2=Sazdanovic |first2=Radmila |last3=Stella |first3=Salvatore |last4=Yip |first4=Martha |date=2023-09-01 |title=On the strength of chromatic symmetric homology for graphs |url=https://www.sciencedirect.com/science/article/pii/S0196885823000775 |journal=Advances in Applied Mathematics |volume=150 |pages=102559 |doi=10.1016/j.aam.2023.102559 |issn=0196-8858|arxiv=1911.13297 }} The chromatic symmetric function can also be defined for vertex-weighted graphs,{{Cite journal |last1=Crew |first1=Logan |title=A Deletion-Contraction Relation for the Chromatic Symmetric Function |date=2020 |arxiv=1910.11859 |doi=10.1016/j.ejc.2020.103143 |last2=Spirkl |first2=Sophie |journal=European Journal of Combinatorics |volume=89 |pages=103143}} 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.{{Cite journal |last=Ciliberti |first=Azzurra |date=2024-01-01 |title=A deletion–contraction long exact sequence for chromatic symmetric homology |url=https://www.sciencedirect.com/science/article/pii/S0195669823001051 |journal=European Journal of Combinatorics |volume=115 |pages=103788 |doi=10.1016/j.ejc.2023.103788 |issn=0195-6698|arxiv=2211.00699 }}
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.{{Cite journal |last1=Shareshian |first1=John |last2=Wachs |first2=Michelle L. |authorlink2=Michelle L. Wachs |date=June 4, 2016 |title=Chromatic quasisymmetric functions |journal=Advances in Mathematics |volume=295 |pages=497–551 |doi=10.1016/j.aim.2015.12.018 |doi-access=free |issn=0001-8708|arxiv=1405.4629 }} 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 . The$ chromatic quasisymmetric function of a graph $G$ is then defined to be: $X_G(x_1,x_2,\ldots;t):=\sum_{\underset{\text{proper}}{\kappa:V\to \N}}t^$
asc(\kappa)
x_{\kappa(v_1)}\cdots x_{\kappa(v_n)}