Chromatic symmetric function

Last updated September 24, 2024

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)\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$ :^[1]^[2] $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 $\lambda$ a partition, let $m_{\lambda }$ be the monomial symmetric polynomial associated to $\lambda$ .

Example 1: complete graphs

Consider the complete graph $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_{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}$ of length $3$ :

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

Altogether, the chromatic symmetric function of $P_{3}$ is then given by:^[2] $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 $\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$ :^[1] $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$ :^[1] $X_{G\amalg H}=X_{G}\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 ${\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 $\lambda \vdash n$ , let $z_{\lambda }$ be the number of stable partitions of $G$ with ${\text{type}}(\pi )=\lambda =\langle 1^{r_{1}}2^{r2}\ldots \rangle$ . Then, $X_{G}$ expands into the augmented monomial symmetric functions, ${\tilde {m}}_{\lambda }:=r_{1}!r_{2}!\cdots m_{\lambda }$ with coefficients given by the number of stable partitions of $G$ :^[1] $X_{G}=\sum _{\lambda \vdash n}z_{\lambda }{\tilde {m}}_{\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:^[1] $X_{G}=\sum _{S\subseteq E}(-1)^{|S|}p_{\lambda (S)}$
Let ${\textstyle X_{G}=\sum _{\lambda \vdash n}c_{\lambda }e_{\lambda }}$ be the expansion of $X_{G}$ in the basis of elementary symmetric functions $e_{\lambda }$ . Let ${\text{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:^[1] ${\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 $\lambda$ , let $e_{\lambda }$ be the elementary symmetric function associated to $\lambda$ .

A partially ordered set $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 ${\text{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 ${\textstyle (3+1)}$ -free poset, then ${\textstyle X_{G}}$ is $e$ -positive.^[1]

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 ${\textstyle (3+1)}$ -free poset, then ${\textstyle 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 ${\text{asc}}(\kappa )=\{\{i,j\}\in E:i<j{\text{ and }}\kappa (i)<\kappa (j)\}$ . The chromatic quasisymmetric function of a graph $G$ is then defined to be:^[8] $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})}$

Related Research Articles

In graph theory, an expander graph is a sparse graph that has strong connectivity properties, quantified using vertex, edge or spectral expansion. Expander constructions have spawned research in pure and applied mathematics, with several applications to complexity theory, design of robust computer networks, and the theory of error-correcting codes.

In graph theory, a perfect matching in a graph is a matching that covers every vertex of the graph. More formally, given a graph $G = (V, E)$ , a perfect matching in $G$ is a subset $M$ of edge set $E$ , such that every vertex in the vertex set $V$ is adjacent to exactly one edge in $M$ .

In graph theory and computer science, an adjacency matrix is a square matrix used to represent a finite graph. The elements of the matrix indicate whether pairs of vertices are adjacent or not in the graph.

In the mathematical discipline of graph theory, a matching or independent edge set in an undirected graph is a set of edges without common vertices. In other words, a subset of the edges is a matching if each vertex appears in at most one edge of that matching. Finding a matching in a bipartite graph can be treated as a network flow problem.

The Gram–Charlier A series, and the Edgeworth series are series that approximate a probability distribution in terms of its cumulants. The series are the same; but, the arrangement of terms differ. The key idea of these expansions is to write the characteristic function of the distribution whose probability density function $f$ is to be approximated in terms of the characteristic function of a distribution with known and suitable properties, and to recover $f$ through the inverse Fourier transform.

<span class="mw-page-title-main">Strongly regular graph</span> Concept in graph theory

In graph theory, a strongly regular graph (SRG) is a regular graph $G = (V, E)$ with $v$ vertices and degree $k$ such that for some given integers

In mathematics and computer science, connectivity is one of the basic concepts of graph theory: it asks for the minimum number of elements that need to be removed to separate the remaining nodes into two or more isolated subgraphs. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its resilience as a network.

In mathematics, Schur polynomials, named after Issai Schur, are certain symmetric polynomials in n variables, indexed by partitions, that generalize the elementary symmetric polynomials and the complete homogeneous symmetric polynomials. In representation theory they are the characters of polynomial irreducible representations of the general linear groups. The Schur polynomials form a linear basis for the space of all symmetric polynomials. Any product of Schur polynomials can be written as a linear combination of Schur polynomials with non-negative integral coefficients; the values of these coefficients is given combinatorially by the Littlewood–Richardson rule. More generally, skew Schur polynomials are associated with pairs of partitions and have similar properties to Schur polynomials.

The Tutte polynomial, also called the dichromate or the Tutte–Whitney polynomial, is a graph polynomial. It is a polynomial in two variables which plays an important role in graph theory. It is defined for every undirected graph $and contains information about how the graph is connected. It is denoted by .$

The expander mixing lemma intuitively states that the edges of certain $-regular graphs are evenly distributed throughout the graph. In particular, the number of edges between two vertex subsets and is always close to the expected number of edges between them in a random -regular graph, namely .$

In mathematics, the Jack function is a generalization of the Jack polynomial, introduced by Henry Jack. The Jack polynomial is a homogeneous, symmetric polynomial which generalizes the Schur and zonal polynomials, and is in turn generalized by the Heckman–Opdam polynomials and Macdonald polynomials.

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with $colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős, after whom it is named.$

In mathematics, a Bratteli diagram is a combinatorial structure: a graph composed of vertices labelled by positive integers ("level") and unoriented edges between vertices having levels differing by one. The notion was introduced by Ola Bratteli in 1972 in the theory of operator algebras to describe directed sequences of finite-dimensional algebras: it played an important role in Elliott's classification of AF-algebras and the theory of subfactors. Subsequently Anatoly Vershik associated dynamical systems with infinite paths in such graphs.

In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate. The degeneracy of a graph is a measure of how sparse it is, and is within a constant factor of other sparsity measures such as the arboricity of a graph.

In algebra and in particular in algebraic combinatorics, a quasisymmetric function is any element in the ring of quasisymmetric functions which is in turn a subring of the formal power series ring with a countable number of variables. This ring generalizes the ring of symmetric functions. This ring can be realized as a specific limit of the rings of quasisymmetric polynomials in n variables, as n goes to infinity. This ring serves as universal structure in which relations between quasisymmetric polynomials can be expressed in a way independent of the number n of variables.

In mathematics, the Lindström–Gessel–Viennot lemma provides a way to count the number of tuples of non-intersecting lattice paths, or, more generally, paths on a directed graph. It was proved by Gessel–Viennot in 1985, based on previous work of Lindström published in 1973.

In combinatorial mathematics, the hook length formula is a formula for the number of standard Young tableaux whose shape is a given Young diagram. It has applications in diverse areas such as representation theory, probability, and algorithm analysis; for example, the problem of longest increasing subsequences. A related formula gives the number of semi-standard Young tableaux, which is a specialization of a Schur polynomial.

In coding theory, Zemor's algorithm, designed and developed by Gilles Zemor, is a recursive low-complexity approach to code construction. It is an improvement over the algorithm of Sipser and Spielman.

In complex analysis, a discipline in mathematics, and in statistical physics, the Asano contraction or Asano–Ruelle contraction is a transformation on a separately affine multivariate polynomial. It was first presented in 1970 by Taro Asano to prove the Lee–Yang theorem in the Heisenberg spin model case. This also yielded a simple proof of the Lee–Yang theorem in the Ising model. David Ruelle proved a general theorem relating the location of the roots of a contracted polynomial to that of the original. Asano contractions have also been used to study polynomials in graph theory.

Quantum optimization algorithms are quantum algorithms that are used to solve optimization problems. Mathematical optimization deals with finding the best solution to a problem from a set of possible solutions. Mostly, the optimization problem is formulated as a minimization problem, where one tries to minimize an error which depends on the solution: the optimal solution has the minimal error. Different optimization techniques are applied in various fields such as mechanics, economics and engineering, and as the complexity and amount of data involved rise, more efficient ways of solving optimization problems are needed. Quantum computing may allow problems which are not practically feasible on classical computers to be solved, or suggest a considerable speed up with respect to the best known classical algorithm.

References

1 2 3 4 5 6 7 8 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.
1 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.
↑ 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 .
↑ 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.
↑ 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.
↑ 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.
↑ 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.
1 2 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.