Chromatic symmetric function explained

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) ≠ \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 :^[2] $$X\_G(x\_1,x\_2,\backslash ldots):=\backslash sum\_x\_x\_\backslash cdots\; x\_$$

Examples

For

λ a partition, let m _{λ} be the monomial symmetric polynomial associated to λ .

Example 1: complete graphs

K _{n} on n vertices:

• There are

n! ways to color K _{n} with exactly n colors yielding the term n!x _{1 …} 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 …} x _{n} = n!m _{(1,\ldots,1)}

Example 2: a path graph

P _{3} of length 3 :

• There are

3 ! ways to color P _{3} with exactly 3 colors, yielding the term 6 x _{1x} _{2x} _{3}

• For each pair of colors, there are

2 ways to color P _{3} yielding the terms x ^{2 x} _{j} and x _{ix} ^{2} ^{j} for i ≠ j

Altogether, the chromatic symmetric function of

P _{3} is then given by:$$X\_(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\_\; +\; m\_$$

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,\backslash ldots,1,0,0,\backslash ldots)=\backslash 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\_=X\_G\backslash 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 type (\pi) is the partition consisting of parts equal to the sizes of the connected components of the vertex induced subgraphs. For a partition λ \vdash n , let z _{λ} be the number of stable partitions of G with type (\pi) =λ= \langle 1 ^{r _{1}} 2 ^{r2} \ldots\rangle . Then, X _{G} expands into the augmented monomial symmetric functions, \tilde{m} _{λ:=r} _{1!r} _{2! …} m _{λ} with coefficients given by the number of stable partitions of G :$$X\_G=\backslash sum\_z\_\backslash lambda\; \backslash tilde\_\backslash lambda$$

• Let

p _{λ} be the power-sum symmetric function associated to a partition λ . For S\subseteq E , let λ (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=\backslash sum\_(-1)^$$p_

• Let $X\_G=\backslash sum\_c\_\backslash lambda\; e\_\backslash lambda$ be the expansion of

X _{G} in the basis of elementary symmetric functions e _{λ} . Let 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:$$\backslash text(G,s)=\backslash sum\_c\_\backslash 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

λ , let e _{λ} be the elementary symmetric function associated to λ .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 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.^[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 asc (\kappa) = \{\{i,j\}\in E:i<j and \kappa(i)<\kappa(j)\} . The chromatic quasisymmetric function of a graph G is then defined to be:$$X\_G(x\_1,x\_2,\backslash ldots;t):=\backslash sum\_t^$$x_\cdots x_

See also

• Chromatic polynomial
• Symmetric function

Further reading

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

Notes and References

1. Stanley . R.P. . Richard P. Stanley . 1995 . A Symmetric Function Generalization of the Chromatic Polynomial of a Graph . . 111 . 1 . 166–194 . 10.1006/aima.1995.1020 . free . 0001-8708.
2. Web site: Saliola . Franco . October 15, 2022 . Lectures on Symmetric Functions with a view towards Hessenberg varieties — Draft . live . https://web.archive.org/web/20221018024159/https://www.birs.ca/workshops/2022/22w5143/files/Franco%20Saliola/Saliola-Lectures-on-Chromatic-Symmetric-Functions.pdf . October 18, 2022 . April 27, 2024.
3. Gasharov . Vesselin . 1996 . Incomparability graphs of (3+1)-free posets are s-positive . . 157 . 1–3 . 193–197 . 10.1016/S0012-365X(96)83014-7 . free.
4. Sazdanovic . Radmila . Yip . Martha . 2018-02-01 . A categorification of the chromatic symmetric function . . Series A . 154 . 218–246 . 10.1016/j.jcta.2017.08.014 . free . 0097-3165. 1506.03133 .
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 . 10.1016/j.aam.2023.102559 . 0196-8858. 1911.13297 .
6. Crew . Logan . A Deletion-Contraction Relation for the Chromatic Symmetric Function . 2020 . 1910.11859 . 10.1016/j.ejc.2020.103143 . Spirkl . Sophie . . 89 . 103143.
7. Ciliberti . Azzurra . 2024-01-01 . A deletion–contraction long exact sequence for chromatic symmetric homology . . 115 . 103788 . 10.1016/j.ejc.2023.103788 . 0195-6698. 2211.00699 .
8. Shareshian . John . Wachs . Michelle L. . Michelle L. Wachs . June 4, 2016 . Chromatic quasisymmetric functions . . 295 . 497–551 . 10.1016/j.aim.2015.12.018 . free . 0001-8708. 1405.4629 .