Misplaced Pages

Chromatic symmetric function

Article snapshot taken from Wikipedia with creative commons attribution-sharealike license. Give it a read and then ask your questions in the chat. We can research this topic together.
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.

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})}}

See also

References

  1. ^ 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.
  2. ^ 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.
  3. 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.
  4. 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.
  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. arXiv:1911.13297. doi:10.1016/j.aam.2023.102559. ISSN 0196-8858.
  6. 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.
  7. 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.
  8. ^ 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.

Further reading

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