2022-10-20

## Chromatic quasisymmetric functions

### Historical overview

R. Stanley introduced the chromatic symmetric function of a graph $G$ in [Sta95].
This definition was later refined by J. Shareshian and M. Wachs in [SW12a] and [SW16],
where the graph $G$ is labeled and a parameter $q$ is introduced.

In Spring 2016, B. Ellzey [Ell17a] presented a generalization where labeled graphs are replaced with *oriented graphs*.
This new model is equivalent to the Shareshian–Wachs model when the orientation of the edges has no directed cycle.
See also G. Panova, P. Alexandersson [AP18], who considered the same model from a different perspective.

The main open problem in this area concerns the conjectured positive expansion of chromatic symmetric functions in the elementary symmetric function basis, and later the refined conjecture by J. Shareshian and M. Wachs in [SW12aSW16]. These conjectures are referred to the Stanley–Stembridge conjecture and Shareshian–Wachs conjecture, respectively.

For a representation-theoretical perspective, see [Ska20], where connections with immanents and characters is studied.

### Definition

Let $G$ be an *oriented graph* with $n$ vertices. Given a vertex-coloring $\kappa:G\to \setP,$
let $\asc(\kappa)$ denote the number of directed edges $(u,v)$ in $G$ such that $\kappa(u) \lt \kappa(v).$

The chromatic quasisymmetric function of $G$ is defined as

\[ \chrom_G(\xvec;q) \coloneqq \sum_{\substack{\kappa : G\to \setP \\ \kappa \text{ proper}} } x_{\kappa(1)}\dotsm x_{\kappa(n)} q^{\asc(\kappa)}, \]where the sum runs over all proper colorings of the graph $G.$ A coloring is proper there are no edges whose endpoints recieve the same color. The function $\chrom_G(\xvec;q)$ is quasi-symmetric in $\xvec.$

From the definition, it is clear that

\[ \chrom_G(1^k;1) \]is the number of ways to color $G$ with $k$ colors, so the classical chromatic polynomial $\chi_G(k)$ is given by the specialization $\chrom_G(1^k;1).$ See [SV21] for a nice article with bijective proofs of properties of $\chi_G(k).$

Note that every labeling induces an orientation, by orienting edges in the direction of largest label. This labeled model is what was introduced in [SW12aSW16].

### Claw-free graphs

If $G$ is a claw-free graph, Gasharov (see [Sta98]) conjecture that $\chrom_G(\xvec;1)$ is Schur-positive. There is no known $q$-analogue of this conjecture.

### Unit interval graphs

The following definition using area sequences is from [AP18].

A circular unit arc digraph (or circular Dyck path) $\Gamma_\avec$ is a directed graph with vertex set $[n]$ and edges

\begin{align} (i-a_i) \to i, \; (i-a_i + 1) \to i, \; (i-a_i + 2) \to i, \; \dotsc \; , (i-1) \to i % i \to i+1, \; i \to i+2,\; \dotsc, i \to i+a_i \end{align}for all $i = 1,\dotsc,n,$ where indices are taken modulo $n,$ and the integers $\avec=(a_1,\dotsc,a_n)$ satisfy

- $0 \leq a_i \leq n-1 $ for $1 \leq i \leq n,$
- $a_{i+1} \leq a_{i} + 1$ for $1 \leq i \leq n,$ (index mod $n$).

Whenever $a_1=0,$ $\Gamma_\avec$ is a unit interval graph. The sequence $\avec = (a_1,a_2,\dotsc,a_n)$ is called the area sequence of the graph.

There are Catalan $\frac{1}{n+1}\binom{2n}{n}$ many unit interval graphs on $n$ vertices, and a total of

\[ (n+2)\binom{2n-1}{n-1} - 2^{2n-1} \]circular unit arc digraph on $n$ vertices, see [ALP19] for a proof. This sequence appears as A194460 in the OEIS.

**Example.**

The area sequences $(0,1,2,1,1)$ and $(3,2,1,2,2)$ can be
presented as *Dyck diagrams*, or in the second circular case,
a circular Dyck diagram:

$\square$ | $\square$ | $\square$ | $5$ | |

$\square$ | $\square$ | $4$ | ||

$3$ | ||||

$2$ | ||||

$1$ |

$\square$ | $\square$ | $5$ | ||||||

$\square$ | $\square$ | $4$ | ||||||

$\square$ | $\square$ | $\square$ | $3$ | |||||

$\square$ | $\square$ | $2$ | ||||||

$\square$ | $1$ |

The labeled boxes represent vertices, the empty boxes are edges (connecting the vertex in the same column with the vertex in the same row), and the squares represent non-edges. The first graph has 5 edges, while the second has 9 edges. Note that circular Dyck diagrams "wrap around" at top and bottom. Edges are directed upwards (or rightwards) in these diagrams.

## Properties of chromatic quasisymmetric functions

### Symmetry

Whenever $G$ is a unit arc digraph as above, $\chrom_G(\xvec;q)$ is symmetric (for labeled graphs, [SW12aSW16] and for oriented graphs, [Ell17aAP18]). Furthermore, the coefficients in $\setZ[q]$ in the monomial basis are palindromic. To be precise,

\[ \chrom_\avec(\xvec;q)=\sum_\lambda c_\lambda(q) \monomial_\lambda(\xvec) \qquad \Longrightarrow \qquad c_\lambda(q) = q^{|\avec|}c_\lambda(1/q), \]where $|\avec|$ denotes the sum $a_1+a_2+\dotsb + a_n.$

### Reciprocity

Let $\chi_G(k)$ be the chromatic polynomial associated with the graph $G$ on the vertex set $[n].$ O.Bernardi and P. Nadeau [BN19a] gave the following interpretation of the specialization $(-1)^{n-i}\chi^{(i)}_G(-j).$

**Theorem.**

Let $i,j \geq 0.$ Then $(-1)^{n-i}\chi^{(i)}_G(-j)$ counts the number of tuples

\[ \left( (V_1, \theta_1),\dotsc,(V_{i+j}, \theta_{i+j}) \right) \]such that

- $V_1,\dotsc,V_{i+j}$ is a set-partition of the vertices of $G,$
- $\theta_\ell$ is an acyclic orientation of the graph induced by $V_\ell,$
- for all $\ell \in [i],$ $V_\ell$ is non-empty and $\theta$ has a unique source, given by $\min V_\ell.$

### Relationship with LLT polynomials

Carlson–Mellit [Prop.3.4, CM17] proved the following plethystic relationship between chromatic quasisymmetric functions and unicellular LLT polynomials indexed by unit interval graphs on $n$ vertices:

\[ (q-1)^{-n} \LLT_\avec[\xvec(q-1);q] = \chrom_\avec(\xvec;q). \]This relationship is not always true in the circular case, that is, for area sequences where $a_1 \gt 0.$ The relationship is reminiscent of the technique introduced by Haglund, Haiman and Loehr [HHL05].

This plethystic relationship is generalized in [Thm. 6.2, NT19], where a non-commutative lift is given. J.-C. Novelli and J.-Y. Thibon also introduce a non-commutative lift of the unicellular LLT polynomials.

### Fundamental quasisymmetric positivity

It is easy to show that

\[ \chrom_G(\xvec;q) = \sum_{\theta \in AO(G)} q^{\asc(\theta)} K_{P(\theta)}(\xvec) \]where $K_{P(\theta)}(\xvec)$ is the generating function
of *strict* order-preserving maps
from the poset $P(\theta)$ given by the transitive closure of the directed edges in $\theta,$
to the set of positive integers.

From this, it follows that $\chrom_G(\xvec;q)$ is positive in the fundamental quasisymmetric basis.

### Power-sum positivity

In [AS19b], it is proved that $\omega \chrom_G(\xvec;q)$ is always $\qPsi$-positive, that is, positive in a quasisymmetric powersum basis. Consequently, $\omega \chrom_G(\xvec;q)$ is $\powerSum$-positive whenever $\chrom_G(\xvec;q)$ is symmetric. This was proved earlier in [Ell17a], and in the case of unit interval graphs $G$ in [Ath15]. A combinatorial formula in the unit-interval case was conjectured earlier by Shareshian–Wachs.

We have the following expansion, proved in [AS19b]:

**Theorem (Alexandersson, Sulzgruber (2018)).**

Let $G$ be a graph on $n$ vertices. The quasisymmetric power-sum expansion of $\omega \chrom_G(\xvec;q)$ is given by

\[ \omega \chrom_G(\xvec;q) = \sum_{\theta \in AO(G)} q^{\asc(\theta)} \sum_{f \in \opsurj^{\ast}(\theta)} \frac{\qPsi_{\type(f)}(\xvec)}{z_{\type(f)}} \]where the first sum ranges over acyclic orientations of $G.$ The set $\opsurj_{\alpha}^{\ast}(\theta)$ consists of of order-preserving surjections $f$ from $\theta$ to some $[k],$ such that $\theta$ restricted to the vertices $f^{-1}(j)$ has a unique sink. The type of $f$ is the composition $\alpha$ given by $\alpha_j \coloneqq |f^{-1}(j)|.$

In particular, for $q=1,$ we have that $\chrom_G(\xvec) = \chrom_G(\xvec;1)$ is symmetric. Thus, the formula above gives that

\begin{align} \omega \chrom_G(\xvec) &= \sum_{\theta \in AO(G)} \sum_{f \in \opsurj^{\ast}(\theta)} \frac{\powerSum_{\type(f)}(\xvec)}{z_{\type(f)}}. \end{align}This can further be simplified, to give

\begin{align} \omega \chrom_G(\xvec) &=\sum_{\theta \in AO(G)} \powerSum_{\type(\theta)}(\xvec), \end{align}where $\type(\theta)$ is given by the *source-components*
of $\theta,$ see [BN19a].
This formula is very similar to the stronger result by C. Athanasiadis [Ath15],
which treats the case with general $q.$

### Schur positivity

In [Gas96], Gasharov proved that the $\chrom_G(\xvec;1)$ are Schur-positive with an explicit expansion, whenever $G$ is the incomparability graph of a $3+1$-free poset. In particular, this implies the unit-interval case, as those are given as the incomparability graphs of $3+1$ and $2+2$-free posets. Gasharov's proof uses a kind of sign-reversing involution.

Gasharov's result was later extended to the Shareshian–Wachs setting (with a $q$-parameter), by using a different involution. That is, $\chrom_G(\xvec;q)$ is Schur-positive for unit-interval graphs $G,$ see [Thm. 6.3, SW12a].

**Example.**

We have the following Schur expansions of chromatic quasisymmetric functions, indexed by area sequences:

\begin{align*} \chrom_{000}(x;q)&=\schurS_{111}+2 \schurS_{21}+\schurS_{3} \\ \chrom_{001}(x;q)&=(1+q) \schurS_{111}+(1+q) \schurS_{21} \\ \chrom_{011}(x;q)&=(1+2 q+q^2) \schurS_{111}+q \schurS_{210} \\ \chrom_{111}(x;q)&=(3 q+3 q^2) \schurS_{111} \\ \chrom_{012}(x;q)&=(1+2 q+2 q^2+q^3) \schurS_{111} \\ \chrom_{112}(x;q)&=(q+4 q^2+q^3) \schurS_{111} \\ \chrom_{122}(x;q)&=(3 q^2+3 q^3) \schurS_{111} \\ \chrom_{222}(x;q)&=6 q^3 \schurS_{111} \end{align*}**Problem.**

Prove that $\chrom_G(\xvec;q)$ is Schur-positive (with coefficients in $\setN[q]$) in the case of *circular* unit arc digraphs.
This conjecture has been verified for all circular unit arc digraphs up to 10 vertices.

Find a bijective proof of Schur-positivitity (using crystals or a version of RSK). Gasharov's result provides a hint on how a crystal graph structure might be defined.

In [WW20], the authors give a (signed) formula for the Schur coefficients of the chromatic symmetric function of any graph. They do this by inverting the matrix of Kostka coefficients. The approach is reminiscent of how one can turn a fundamental quasisymmetric expansion into a Schur expansion, using the slinky rule. The authors also characterize all Schur positive complete tripartite graphs.

### Elementary symmetric expansion

The Stanley–Stembridge conjecture (1993) is a long-standing open problem in algebraic combinatorics, first formulated in [SS93] and [Sta95] (for $q=1$). A refinement using the general $q$-parameter was presented in [Conj. 4.9, SW12a], which we now state.

**Conjecture (Shareshian–Wach (2012)).**

Let $G$ be a unit interval graph. Find a statistic $\mu$ on acyclic orientations of $G,$ such that

\[ \chrom_G(\xvec;q) = \sum_{\theta \in AO(G)} q^{\asc(\theta)} \elementaryE_{\mu(\theta)}(\xvec). \]That is, prove that $\chrom_G(\xvec;q)$ are $\elementaryE$-positive.

See the weighed Dyck path enumeration page for more info.

This conjecture extends to the circular unit arc digraph case, see [Ell17aAP18]. According to A. Mellit (personal communication), this would imply Conjecture 5.4 in https://arxiv.org/pdf/1506.08188.pdf.

Positivity has been proved for several families of unit-interval graphs, see the separate subsection on the current status.

**Conjecture (See [Conj. 5.1, SW16]).**

The following unimodality conjecture is posed: Write

\[ \chrom_{G}(\xvec;q) = \sum_{j=0}^m q^j a_j(\xvec), \]where $m$ is the number of edges of $G.$ Then $a_{j+1}(\xvec) - a_{j}(\xvec)$ is $\elementaryE$-positive for all $0 \leq j \lt (m-1)/2.$

This conjecture extends to the circular unit arc digraphs.

The main theorem of [CHL20], gives an explicit condition for when a coefficient in the $\elementaryE$-expansion is positive.

### Current status of the Stanley–Stembridge/Shareshian–Wach conjecture

The following references give proofs of $\elementaryE$-positivity for some families of graphs.

- Combinatorial interpretation of line graph, complete graph and cycle graph, [Ell17aAP18].
- When the complement graph is also a unit-interval graph, [FHM19].
- Triangular ladders, [Dah18]. This correspond to area sequences of the form $(0,1,2,2,\dotsc,2).$
- Lollipop graphs for $q=1,$ [DvW18].
- Melting lollipop graphs, [HNY20].
- Abelian area sequences with bounce number 2, using a recursive method, [HP19]. See also the alternative proof in [CH19b], using a sign-reversing involution.
- Area sequences with bounce number 3, [CH19a].
- Generalized pyramid graphs, and $(claw, 2K_2)$-free unit interval graphs, [LY21].

Moreover, some larger families of graphs are shown not to be e-positive, see [DFW17FKKAMT18].

### Deletion contraction property

There is an extension to extended chromatic symmetric functions which admits a deletion-contraction recurrence.

## Chromatic symmetric functions of trees

R. Stanley conjectures [Sta95] that the chromatic symmetric function of a tree, uniquely determines the tree.

In [Thm. 1.3, HT17], it is proved that ordered trees are distinguished by their order quasisymmetric function (where the rooted tree is viewed as a poset, colors are increasing away from the root). Both the weakly increasing, or strictly increasing version of the quasisymmetric function does the job. The work by Hasabe and Tsujie is continued in [Zho20], where one is interested in reconstructing the tree from the quasisymmetric function.

It is still an open problem (posed by Hasabe and Tsujie) to prove that the P-partition quasisymmetric function distinguishes posets whose Hasse diagrams are trees.

In [AS19b], we conjecture that in the family of directed trees, the chromatic quasisymmetric function uniquely determines the directed tree. This conjecture would follow from the conjecture by Hasabe and Tsujie.

See also [FKKAMT21].

## Connection with Hessenberg varieties

In [Conj. 5.3, SW12a], a connection with cohomology of regular semisimple Hessenberg varieties was conjectures. This conjecture was resolved in in 2015, where Brosnan and Chow proved that for unit-interval graphs $\avec,$ the symmetric function $\omega \chrom_\avec(\xvec;q)$ is the Frobenius characteristic of a symmetric group action on the cohomology of regular semisimple Hessenberg varieties. Note that their result implies Schur positivity.

### Hessenberg varieties

This section uses information from these slides.

See also the PhD thesis by N. Teff [Tef13].

A Hessenberg sequence is a sequence of natural numbers $(m_1,\dotsc,m_n)$ such that $i \leq m_i \leq n.$ These are in bijection with area sequences of unit inverval graphs, via $a_i = m_i - i.$

Let $F(n)$ be the set of all flags, $F_1 \subset F_2 \subset \dotsb \subset F_n = \setC^n,$ where $F_i$ has dimension $i.$ Let $D$ be a diagonal $n\times n$-matrix with distinct diagonal entries.

Then the type $A$ Hessenberg variety associated with $m$ is defined as

\[ H(m) \coloneqq \{ F \in F(n) : DF_i \subseteq F_{m_i} \text{ for all $i$} \}. \]**Example.**

The area sequence $(0,1,2,1,1)$ correspond to the Hessenberg sequence $(2,3,5,5,5).$ Note that the Hessenberg sequence is simply the number of non-$\square$ boxes in each row in the extended $n\times n$-diagram.

$\square$ | $\square$ | $\square$ | ||

$\square$ | $\square$ | |||

There is a torus action on $H(m),$ by left multiplication of invertible $n\times n$-matrices. We consider $0$-dimensional and $1$-dimensional fixed-points under this torus action. This is what is called the moment graph, associated with $H(m).$

The combinatorial description of the moment graph is easier to define using the corresponding unit-interval graph $\Gamma_\avec,$ with edge set $E.$ The vertices are the permutations in $\symS_n,$ and the edge set is

\[ \{ (\sigma, (i,j)\sigma : \sigma \in \symS_n \text{ and } \{i,j\} \in E \}. \]Let us denote this graph by $MG(\avec).$

One can then define the so called Tymoczko’s representation [Tym08b] where $\symS_n$ act on a certain polynomial ring defined via $MG(\avec).$

## References

- [ALP19] Per Alexandersson, Svante Linusson and Samu Potka. The cyclic sieving phenomenon on circular Dyck paths. The Electronic Journal of Combinatorics, 26:1–32, October 2019.
- [AP18] Per Alexandersson and Greta Panova. LLT polynomials, chromatic quasisymmetric functions and graphs with cycles. Discrete Mathematics, 341(12):3453–3482, December 2018.
- [AS19b] Per Alexandersson and Robin Sulzgruber. P-partitions and P-positivity. International Mathematics Research Notices, July 2019.
- [Ath15] Christos A. Athanasiadis. Power sum expansion of chromatic quasisymmetric functions. The Electronic Journal of Combinatorics, 22(2):1–9, April 2015.
- [BN19a] Olivier Bernardi and Philippe Nadeau. Combinatorial reciprocity for the chromatic polynomial and the chromatic symmetric function. arXiv e-prints, 2019.
- [CH19a] Soojin Cho and Jaehyun Hong. Positivity of chromatic symmetric functions associated with Hessenberg functions of bounce number 3. arXiv e-prints, 2019.
- [CH19b] Soojin Cho and JiSun Huh. On $e$-positivity and $e$-unimodality of chromatic quasi-symmetric functions. SIAM Journal on Discrete Mathematics, 33(4):2286–2315, January 2019.
- [CHL20] Soojin Cho, Jaehyun Hong and Eunjeong Lee. Bases of the equivariant cohomologies of regular semisimple Hessenberg varieties. arXiv e-prints, 2020.
- [CM17] Erik Carlsson and Anton Mellit. A proof of the shuffle conjecture. Journal of the American Mathematical Society, 31(3):661–697, November 2017.
- [Dah18] Samantha Dahlberg. Triangular ladders $p_{d,2}$ are $e$-positive. arXiv e-prints, 2018.
- [DFW17] Samantha Dahlberg, Angèle Foley and Stephanie van Willigenburg. Resolving Stanley's $e$-positivity of claw-contractible-free graphs. arXiv e-prints, 2017.
- [DvW18] Samantha Dahlberg and Stephanie van Willigenburg. Lollipop and lariat symmetric functions. SIAM Journal on Discrete Mathematics, 32(2):1029–1039, January 2018.
- [Ell17a] Brittney Ellzey. A directed graph generalization of chromatic quasisymmetric functions. arXiv e-prints, 2017.
- [FHM19] Angèle M. Foley, Chính T. Hoàng and Owen D. Merkel. Classes of graphs with $e$-positive chromatic symmetric function. The Electronic Journal of Combinatorics, 26(3), September 2019.
- [FKKAMT18] Angèle M. Foley, Joshua Kazdan, Larissa Kröll, Sofía Martínez Alberga, Oleksii Melnyk and Alexander Tenenbaum. Spiders and their kin ($k_n$). arXiv e-prints, 2018.
- [FKKAMT21] Angèle M. Foley, Joshua Kazdan, Larissa Kröll, Sofía Martínez Alberga, Oleksii Melnyk and Alexander Tenenbaum. Transplanting trees: chromatic symmetric function results through the group algebra of $s_n$. arXiv e-prints, 2021.
- [Gas96] Vesselin Gasharov. Incomparability graphs of $(3+1)$-free posets are $s$-positive. Discrete Mathematics, 157(1):193–197, 1996.
- [HHL05] James Haglund, Mark D. Haiman and Nicholas A. Loehr. A combinatorial formula for Macdonald polynomials. J. Amer. Math. Soc., 18(03):735–762, July 2005.
- [HNY20] JiSun Huh, Sun-Young Nam and Meesue Yoo. Melting lollipop chromatic quasisymmetric functions and Schur expansion of unicellular LLT polynomials. Discrete Mathematics, 343(3):111728, March 2020.
- [HP19] Megumi Harada and Martha E. Precup. The cohomology of abelian Hessenberg varieties and the Stanley–Stembridge conjecture. Algebraic Combinatorics, 2(6):1059–1108, 2019.
- [HT17] Takahiro Hasebe and Shuhei Tsujie. Order quasisymmetric functions distinguish rooted trees. Journal of Algebraic Combinatorics, 46(3-4):499–515, May 2017.
- [LY21] Grace M. X. Li and Arthur L. B. Yang. On the $e$-positivity of $(claw, 2k_2)$-free graphs. The Electronic Journal of Combinatorics, 28(2), June 2021.
- [NT19] Jean-Christophe Novelli and Jean-Yves Thibon. Noncommutative unicellular LLT polynomials. arXiv e-prints, 2019.
- [Ska20] Mark Skandera. Characters and chromatic symmetric functions. arXiv e-prints, 2020.
- [SS93] Richard P. Stanley and John R. Stembridge. On immanants of Jacobi–Trudi matrices and permutations with restricted position. Journal of Combinatorial Theory, Series A, 62(2):261–279, March 1993.
- [Sta95] Richard P. Stanley. A symmetric function generalization of the chromatic polynomial of a graph. Advances in Mathematics, 111(1):166–194, 1995.
- [Sta98] Richard P. Stanley. Graph colorings and related symmetric functions: ideas and applications. Discrete Mathematics, 193(1):267–286, 1998.
- [SV21] Bruce Sagan and Vincent Vatter. Bijective proofs of proper coloring theorems. The American Mathematical Monthly, 128(6):483–499, May 2021.
- [Tef13] Nicholas James Teff. The Hessenberg representation. 2013.
- [Tym08b] Julianna S. Tymoczko. Permutation representations on Schubert varieties. American Journal of Mathematics, 130(5):1171–1194, 2008.
- [WW20] David G.L. Wang and Monica M.Y. Wang. A combinatorial formula for the Schur coefficients of chromatic symmetric functions. Discrete Applied Mathematics, 285:621–630, October 2020.
- [Zho20] Jeremy Zhou. Reconstructing rooted trees from their strict order quasisymmetric functions. arXiv e-prints, 2020.