The symmetric functions catalog

An overview of symmetric functions and related topics

2023-11-28

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. Shareshian and Wachs also conjectured that $\omega \chrom_G(\xvec;q)$ is related to the equivariant cohomology of regular semisimple Hessenberg varieties.

In [Hwa22], Byung-Hak Hwang introduces an additional refinement on the chromatic quasisymmetric functions. He defines a "flip" operator on colorings and show that connected components under such flips are Schur-positive. The ascent parameter introduced by Shareshian–Wachs is preserved by such flips. It is conjectured that each such component is positive in the elementary symmetric function basis. See also [Hwa23] for a connection with non-commutative functions.

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 receive 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 (2019)).

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].
  • A generalization of melting lollipop graphs, [Tom23]. This paper includes a signed $\elementaryE$-expansion derived from the $\elementaryE$-expansion of unicellular LLT polynomials.

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].

There is a variant of Stanley's chromatic symmetric functions defined for rooted trees, and this rooted version is shown to distinguish non-isomorphic trees, see [LW24].

In [WYZ23] it is shown that trees with exactly two vertices of degree greater than 2, are distinguished by their chromatic symmetric functions.

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. This was also proved independently by Guay-Paquet [Gua16]. 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