Chromatic Symmetric Function
   HOME

TheInfoList



OR:

The chromatic symmetric function is a
symmetric function In mathematics, a function of n variables is symmetric if its value is the same no matter the order of its arguments. For example, a function f\left(x_1,x_2\right) of two arguments is a symmetric function if and only if f\left(x_1,x_2\right) = f\ ...
invariant of
graphs Graph may refer to: Mathematics *Graph (discrete mathematics), a structure made of vertices and edges **Graph theory, the study of such graphs and their properties * Graph (topology), a topological space resembling a graph in the sense of discre ...
studied in
algebraic graph theory Algebraic graph theory is a branch of mathematics in which algebraic methods are applied to problems about graphs. This is in contrast to geometric, combinatoric, or algorithmic approaches. There are three main branches of algebraic graph the ...
, a branch of
mathematics Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
. It is the weight
generating function In mathematics, a generating function is a representation of an infinite sequence of numbers as the coefficients of a formal power series. Generating functions are often expressed in closed form (rather than as a series), by some expression invo ...
for proper
graph coloring In graph theory, graph coloring is a methodic assignment of labels traditionally called "colors" to elements of a Graph (discrete mathematics), graph. The assignment is subject to certain constraints, such as that no two adjacent elements have th ...
s, and was originally introduced by Richard Stanley as a generalization of the
chromatic polynomial The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to stud ...
of a graph.


Definition

For a finite graph G=(V,E) with vertex set V=\, 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., \\in E \implies \kappa(i)\neq\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:X_G(x_1,x_2,\ldots):=\sum_x_x_\cdots x_


Examples

For \lambda a partition, let m_\lambda be the
monomial symmetric polynomial In mathematics, a symmetric polynomial is a polynomial in variables, such that if any of the variables are interchanged, one obtains the same polynomial. Formally, is a ''symmetric polynomial'' if for any permutation of the subscripts one has ...
associated to \lambda.


Example 1: complete graphs

Consider the
complete graph In the mathematical field of graph theory, a complete graph is a simple undirected graph in which every pair of distinct vertices is connected by a unique edge. A complete digraph is a directed graph in which every pair of distinct vertices i ...
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_(x_1,\ldots,x_n)=n!x_1\cdots x_n = n!m_


Example 2: a path graph

Consider the
path graph In the mathematical field of graph theory, a path graph (or linear graph) is a graph whose vertices can be listed in the order such that the edges are where . Equivalently, a path with at least two vertices is connected and has two termina ...
P_3 of length 3: * There are 3! ways to color P_3 with exactly 3 colors, yielding the term 6x_1x_2x_3 * For each pair of colors, there are 2 ways to color P_3 yielding the terms x_i^2x_j and x_ix_j^2 for i\neq 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,\ldots,1,0,0,\ldots)=\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\cdot X_H * A ''stable partition'' \pi of G is defined to be a
set partition In mathematics, a partition of a set is a grouping of its elements into non-empty subsets, in such a way that every element is included in exactly one subset. Every equivalence relation on a set defines a partition of this set, and every parti ...
of vertices V such that each block of \pi is an independent set in G. The type of a stable partition \text(\pi) is the partition consisting of parts equal to the sizes of the connected components of the vertex induced subgraphs. For a partition \lambda\vdash n, let z_\lambda be the number of stable partitions of G with \text(\pi)=\lambda=\langle1^2^\ldots\rangle. Then, X_G expands into the augmented monomial symmetric functions, \tilde_\lambda:=r_1!r_2!\cdots m_\lambda with coefficients given by the number of stable partitions of G:X_G=\sum_z_\lambda \tilde_\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_(-1)^p_ * Let X_G=\sum_c_\lambda e_\lambda be the expansion of X_G in the basis of elementary symmetric functions e_\lambda. Let \text(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(G,s)=\sum_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 In mathematics, especially order theory, a partial order on a Set (mathematics), set is an arrangement such that, for certain pairs of elements, one precedes the other. The word ''partial'' is used to indicate that not every pair of elements need ...
P is called (3+1)''-free'' if it does not contain a subposet isomorphic to the direct sum of the 3 element
chain A chain is a serial assembly of connected pieces, called links, typically made of metal, with an overall character similar to that of a rope in that it is flexible and curved in compression but linear, rigid, and load-bearing in tension. A ...
and the 1 element chain. The incomparability graph \text(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 In mathematics, categorification is the process of replacing set-theoretic theorems with category-theoretic analogues. Categorification, when done successfully, replaces sets with categories, functions with functors, and equations with natural ...
of the invariant into a
homology theory In mathematics, the term homology, originally introduced in algebraic topology, has three primary, closely-related usages. The most direct usage of the term is to take the ''homology of a chain complex'', resulting in a sequence of abelian grou ...
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(\kappa)=\. The ''chromatic quasisymmetric function'' of a graph G is then defined to be:X_G(x_1,x_2,\ldots;t):=\sum_t^x_\cdots x_


See also

*
Chromatic polynomial The chromatic polynomial is a graph polynomial studied in algebraic graph theory, a branch of mathematics. It counts the number of graph colorings as a function of the number of colors and was originally defined by George David Birkhoff to stud ...
*
Symmetric function In mathematics, a function of n variables is symmetric if its value is the same no matter the order of its arguments. For example, a function f\left(x_1,x_2\right) of two arguments is a symmetric function if and only if f\left(x_1,x_2\right) = f\ ...


References


Further reading

* * * * * {{cite book , doi=10.1007/978-88-7642-431-1_20 , chapter=Chromatic quasisymmetric functions and Hessenberg varieties , title=Configuration Spaces , date=2012 , last1=Shareshian , first1=John , last2=Wachs , first2=Michelle L. , pages=433–460 , arxiv=1106.4287 , isbn=978-88-7642-430-4 Functions and mappings