Chromatic symmetric function

On this page

Symmetric function invariant of graphs

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.

We don't have any images related to Chromatic symmetric function yet.

You can add one yourself here.

We don't have any YouTube videos related to Chromatic symmetric function yet.

You can add one yourself here.

We don't have any PDF documents related to Chromatic symmetric function yet.

You can add one yourself here.

We don't have any Books related to Chromatic symmetric function yet.

You can add one yourself here.

We don't have any archived web articles related to Chromatic symmetric function yet.

You can submit a link to a page to archive here.

Definition

For a finite graph G = ( V , E ) {\displaystyle G=(V,E)} with vertex set V = { v 1 , v 2 , … , v n } {\displaystyle V=\{v_{1},v_{2},\ldots ,v_{n}\}} , a vertex coloring is a function κ : V → C {\displaystyle \kappa :V\to C} where C {\displaystyle C} is a set of colors. A vertex coloring is called proper if all adjacent vertices are assigned distinct colors (i.e., { i , j } ∈ E ⟹ κ ( i ) ≠ κ ( j ) {\displaystyle \{i,j\}\in E\implies \kappa (i)\neq \kappa (j)} ). The chromatic symmetric function denoted X G ( x 1 , x 2 , … ) {\displaystyle X_{G}(x_{1},x_{2},\ldots )} is defined to be the weight generating function of proper vertex colorings of G {\displaystyle G} :² ³ X G ( x 1 , x 2 , … ) := ∑ κ : V → N proper x κ ( v 1 ) x κ ( v 2 ) ⋯ x κ ( v n ) {\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 m λ {\displaystyle m_{\lambda }} be the monomial symmetric polynomial associated to λ {\displaystyle \lambda } .

Example 1: complete graphs

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

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

Thus, X K n ( x 1 , … , x n ) = n ! x 1 ⋯ x n = n ! m ( 1 , … , 1 ) {\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 P 3 {\displaystyle P_{3}} of length 3 {\displaystyle 3} :

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

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

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

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

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

Theorem (Gasharov) Let G {\displaystyle G} be the incomparability graph of a ( 3 + 1 ) {\textstyle (3+1)} -free poset, then X G {\textstyle X_{G}} is s {\displaystyle 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 {\displaystyle P} -tableaux which are a generalization of semistandard Young tableaux instead labelled with the elements of P {\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.¹² 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 {\displaystyle 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 κ {\displaystyle \kappa } is defined to be asc ( κ ) = { { i , j } ∈ E : i < j and κ ( i ) < κ ( j ) } {\displaystyle {\text{asc}}(\kappa )=\{\{i,j\}\in E:i<j{\text{ and }}\kappa (i)<\kappa (j)\}} . The chromatic quasisymmetric function of a graph G {\displaystyle G} is then defined to be:¹⁷ X G ( x 1 , x 2 , … ; t ) := ∑ κ : V → N proper t | a s c ( κ ) | x κ ( v 1 ) ⋯ x κ ( v n ) {\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})}}

References

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. /wiki/Richard_P._Stanley ↩
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. /wiki/Richard_P._Stanley ↩
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. https://www.birs.ca/workshops/2022/22w5143/files/Franco%20Saliola/Saliola-Lectures-on-Chromatic-Symmetric-Functions.pdf ↩
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. https://www.birs.ca/workshops/2022/22w5143/files/Franco%20Saliola/Saliola-Lectures-on-Chromatic-Symmetric-Functions.pdf ↩
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. /wiki/Richard_P._Stanley ↩
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. /wiki/Richard_P._Stanley ↩
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. /wiki/Richard_P._Stanley ↩
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. /wiki/Richard_P._Stanley ↩
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. /wiki/Richard_P._Stanley ↩
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. /wiki/Richard_P._Stanley ↩
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. https://core.ac.uk/download/pdf/82067232.pdf ↩
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. https://doi.org/10.1016%2Fj.jcta.2017.08.014 ↩
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. https://www.sciencedirect.com/science/article/pii/S0196885823000775 ↩
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. /wiki/European_Journal_of_Combinatorics ↩
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. https://www.sciencedirect.com/science/article/pii/S0195669823001051 ↩
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. /wiki/Michelle_L._Wachs ↩
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. /wiki/Michelle_L._Wachs ↩

Definition

Examples

Example 1: complete graphs

Example 2: a path graph

Properties

Open problems

(3+1)-free conjecture

Generalizations

See also

Further reading

References