The symmetric functions catalog

An overview of symmetric functions and related topics

2020-10-02

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).$

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.

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.

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

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.

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