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

edit

For a finite graph   with vertex set  , a vertex coloring is a function   where   is a set of colors. A vertex coloring is called proper if all adjacent vertices are assigned distinct colors (i.e.,  ). The chromatic symmetric function denoted   is defined to be the weight generating function of proper vertex colorings of  :[1][2] 

Examples

edit

For   a partition, let   be the monomial symmetric polynomial associated to  .

Example 1: Complete Graphs

edit

Consider the complete graph   on   vertices:

  • There are   ways to color   with exactly   colors yielding the term  
  • Since every pair of vertices in   is adjacent, it can be properly colored with no fewer than   colors.

Thus,  

Example 2: A Path Graph

edit

Consider the path graph   of length  :

  • There are   ways to color   with exactly   colors, yielding the term  
  • For each pair of colors, there are   ways to color   yielding the terms   and   for  

Altogether, the chromatic symmetric function of   is then given by:[2] 

Properties

edit
  • Let   be the chromatic polynomial of  , so that   is equal to the number of proper vertex colorings of   using at most   distinct colors. The values of   can then be computed by specializing the chromatic symmetric function, setting the first   variables   equal to   and the remaining variables equal to  :[1]  
  • If   is the disjoint union of two graphs, then the chromatic symmetric function for   can be written as a product of the corresponding functions for   and  :[1] 
  • A stable partition   of   is defined to be a set partition of vertices   such that each block of   is an independent set in  . The type of a stable partition   is the partition consisting of parts equal to the sizes of the connected components of the vertex induced subgraphs. For a partition  , let   be the number of stable partitions of   with  . Then,   expands into the augmented monomial symmetric functions,   with coefficients given by the number of stable partitions of  :[1] 
  • Let   be the power-sum symmetric function associated to a partition  . For  , let   be the partition whose parts are the vertex sizes of the connected components of the edge-induced subgraph of   specified by  . The chromatic symmetric function can be expanded in the power-sum symmetric functions via the following formula:[1] 
  • Let   be the expansion of   in the basis of elementary symmetric functions  . Let   be the number of acyclic orientations on the graph   which contain exactly   sinks. Then we have the following formula for the number of sinks:[1] 

Open Problems

edit

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

edit

For a partition  , let   be the elementary symmetric function associated to  .

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

Conjecture: (Stanley-Stembridge) Let   be the incomparability graph of a  -free poset, then   is  -positive.[1]

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

Theorem (Gasharov) Let   be the incomparability graph of a  -free poset, then   is  -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  -tableaux which are a generalization of semistandard Young tableaux instead labelled with the elements of  .

Generalizations

edit

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   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   is defined to be  . The chromatic quasisymmetric function of a graph   is then defined to be:[8] 

References

edit
  1. ^ a b c d e f g h 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. ^ a b 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: 193–197.
  4. ^ Sazdanovic, Radmila; Yip, Martha (2018-02-01). "A categorification of the chromatic symmetric function". Journal of Combinatorial Theory, Series A. 154: 218–246. 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. doi:10.1016/j.aam.2023.102559. ISSN 0196-8858.
  6. ^ Crew, Logan; Spirkl, Sophie (2020-01-15), A Deletion-Contraction Relation for the Chromatic Symmetric Function, doi:10.48550/arXiv.1910.11859, retrieved 2024-04-27
  7. ^ Ciliberti, Azzurra (2024-01-01). "A deletion–contraction long exact sequence for chromatic symmetric homology". European Journal of Combinatorics. 115: 103788. doi:10.1016/j.ejc.2023.103788. ISSN 0195-6698.
  8. ^ a b Shareshian, John; Wachs, Michelle L. (June 4, 2016). "Chromatic quasisymmetric functions". Advances in Mathematics. 295: 497–551. doi:10.1016/j.aim.2015.12.018. ISSN 0001-8708.