Chromatic symmetric function

Template:Short description 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.

Definition

For a finite graph $G=(V,E)$ with vertex set $V=\{v_1,v_2,\dots ,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⟹\kappa (i)\ne \kappa (j)$). The chromatic symmetric function denoted $X_G(x_1,x_2,\dots )$ is defined to be the weight generating function of proper vertex colorings of $G$:$$X_G(x_1,x_2,\dots ):=\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,\dots ,x_n)=n!x_1\cdots x_n=n!m_{(1,\dots ,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\ne j$

Altogether, the chromatic symmetric function of $P_3$ is then given by:$$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$: $$X_G(1^k)=X_G(1,\dots ,1,0,0,\dots )={\chi }_G(k)$$
• If $G⨿H$ is the disjoint union of two graphs, then the chromatic symmetric function for $G⨿H$ can be written as a product of the corresponding functions for $G$ and $H$:$$X_{G⨿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 ⊢n$, let $z_{\lambda }$ be the number of stable partitions of $G$ with $\text{type}(\pi )=\lambda =⟨1^{r_1}{2}^{r2}\dots ⟩$. 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 ⊢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 ⊢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 ⊢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.

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. This homology theory is known to be a stronger invariant than the chromatic symmetric function alone. The chromatic symmetric function can also be defined for vertex-weighted graphs, 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.
• 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. 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:$$X_G(x_1,x_2,\dots ;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

Further reading

• Template:Cite arXiv
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite book