Hikita's proof of the Stanley-Stembridge Conjecture

In this arXiv paper, Hikita recently posted a proof of the famous Stanley-Stembridge conjecture! I went through the proof with my Advanced Combinatorics class, and wrote up lecture notes here:

Lecture Notes on Stanley-Stembridge Part I

Lecture Notes on Stanley-Stembridge Part II

which I will summarize in this post.

What is the Stanley-Stembridge conjecture?

Stanley defined the chromatic symmetric function of a vertex-labeled graph $\Gamma$ as follows: for every proper coloring of $\Gamma$ with colors from $\{1,2,3,\ldots\}$ (such that no two adjacent vertices have the same color), associate the monomial $\prod_i x_i^{m_i}$ where $m_i$ is the multiplicity of the color $i$ in the coloring. Then the sum of these monomials over all proper colorings is the chromatic symmetric function, written $\chi_\Gamma(\mathbf{x})$.

For example, consider the path graph below, with two colorings shown along with their associated monomials:

There are $6$ ways to color it with any choice of three distinct colors, and one way to color it with two $i$’s and one $j$ for any $i$ and $j$, and so the chromatic symmetric function looks like:

\[ 6x_1 x_2 x_3 + 6x_1 x_2 x_4 + \cdots +x_1^2 x_2+\cdots = 6m_{(1,1,1)} + m_{(2,1)}\]

in terms of monomial symmetric functions. In terms of elementary symmetric functions, this equals

\[(x_1x_2+x_1x_3+\cdots)(x_1+x_2+x_3+\cdots) +3(x_1x_2x_3+\cdots)=e_2e_1+3e_{3}\]

Stanley and Stembridge conjectured that for “nice enough” graphs, the chromatic symmetric function is e-positive, meaning that its coefficients in the elementary basis are nonnegative integers. Guay-Paquet reduced their conjecture (which was precisely about incomparability graphs of $3+1$-free posets) to the case of unit interval graphs, which are graphs whose vertices $v_1,\ldots, v_n$ correspond to unit length intervals ordered by their left endpoint on the real line, and such that there is an edge between two vertices if and only if the corresponding unit intervals overlap. For instance:

Unit interval graphs can be encoded combinatorially (up to isomorphism) by Hessenberg functions, which are weakly increasing functions $h:\{1,2,\ldots,n\} \to \{1,2,\ldots, n\}$ such that $h(i)\ge i$ for all $i$. The unit interval graph on $v_1,\ldots, v_n$ associated to $h$ is the graph formed by connecting $v_1$ to all $v_j$ with $j\le h(1)$, then connecting $v_2$ to all $v_j$ with $2\le j \le h(2)$, and so on.

As an example, the unit interval graph above is associated to the Hessenberg function $h=(2,3,3,4,7,7,7)$, and we draw it as a Dyck path whose heights of the horizontal steps are $h(1),h(2),\ldots, h(n)$ from left to right:

Finally, Hikita uses the complementary Hessenberg function $\mathbf{e}:\{1,2,\ldots,n\} \to \{1,2,\ldots, n\}$ defined by $\mathbf{e}(i)=n - h(n+1-i)$. That is, the function $\mathbf{e}$ gives the number of squares above the Dyck path in each column from right to left, and in the above example, $\mathbf{e}=(0,0,0,3,4,4,5)$ with $n=7$.

Shareshian-Wachs Conjecture

There is an important $q$-analog of the chromatic symmetric function used in Hikita’s proof, known as the chromatic quasisymmetric function $\chi_\Gamma(\mathbf{x};q)$. This is defined similarly to the chromatic symmetric function, except we multiply the monomial associated to a coloring $\kappa$ by the power $q^{\mathrm{asc}(\kappa)}$, where $\mathrm{asc}(\kappa)$ is the number of pairs of vertices $v_i,v_j$ connected by an edge such that $i<j$ and $\kappa(i)< \kappa(j)$. Such a pair is called an ascent.

An analysis of the ascents for the path graph above shows that the chromatic quasisymmetric function is \[(1+4q+q^2)m_{(1,1,1)}+qm_{(2,1)}=(1+q+q^2)e_{3}+qe_{2,1}\]

(Note that the chromatic quasisymmetric function is not always symmetric, but it is in the case of unit interval graphs. See my recent paper with Pappe and Salois that explores when the chromatic quasisymmetric function is symmetric.)

The Shareshian-Wachs Conjecture states that the coefficients of each $e_\lambda$ in the chromatic quasisymmetric function of a unit interval graph are polynomials in $q$ with nonnegative integer coefficients. This refines the Stanley-Stembridge conjecture, and is still open.

Proof strategy via constructing a probability

Write $c_\lambda(\mathbf{e},q)$ to be the coefficient of the elementary symmetric function $e_\lambda$ in the chromatic quasisymmetric function $\chi_{\Gamma(\mathbf{e})}(\mathbf{x},q)$ where $\Gamma(\mathbf{e})$ is the unit interval graph associated to the complementary Hessenberg function $\mathbf{e}$. Let $\mathbf{e}_\lambda$ be the specific complementary Hessenberg function associated to the Dyck path that, starting from the upper right, consists of $\lambda_i$ horizontal steps followed by $\lambda_i$ vertical steps for each $i=1,2,\ldots$. Also write $|\mathbf{e}|=\mathbf{e}(1)+\mathbf{e}(2)+\cdots+ \mathbf{e}(n)$.

Then, motivated by the known identity

\[\sum_{\lambda \vdash n} q^{|\mathbf{e}|-|\mathbf{e}_\lambda|} \frac{c_\lambda(\mathbf{e},q)}{\prod_i (\lambda_i)_q! }=1,\]

Hikita recursively constructs a probability distribution $p_\lambda(\mathbf{e},q)$ for any fixed $\mathbf{e}$ and positive real number $q$, on the partitions $\lambda$ of $n$, such that

\[ p_\lambda(\mathbf{e},q) = q^{|\mathbf{e}|-|\mathbf{e}_\lambda|} \frac{c_\lambda(\mathbf{e},q)}{\prod_i (\lambda_i)_q! }.\]

Since the denominator is a polynomial in $q$ with positive integer coefficients, setting $q=1$ will imply the Stanley-Stembridge conjecture.

To define $p_\lambda$, one first defines a probability distribution $p_T(\mathbf{e},q)$ for any fixed $\mathbf{e}$ and $q$, where $T$ ranges over all standard Young tableaux (SYT’s) of size $n$, and then defines

\[ p_\lambda = \sum_{T\in \mathrm{SYT}(\lambda)} p_T \]

where $\mathrm{SYT}(\lambda)$ is the set of all standard Young tableaux of shape $\lambda$.

Below is an example of an SYT of shape $(14,10,9,6,2,1)$, whose boxes is filled with the numbers $1,2,\ldots,42$ in such a way that every row and column is increasing going right and up (this is the French convention for Young diagrams).

New tableaux from old

To recursively define $p_T(\mathbf{e},q)$, we start with the empty tableau and set $p_\emptyset(\emptyset,q)=1$ for all $q\ge 0$. Then for a tableau $T’$ of size $n+1$, consider the corner square labeled $n+1$ and let $T$ be the tableau formed by deleting it. Let $\mathbf{e}’$ be a complementary Hessenberg function of length $n+1$, and let $r=\mathbf{e}’(n+1)$. Color all of the squares of $T$ whose label is strictly greater than $r$ red. For instance, for $T$ as above and $r=36$ and $n=42$, we have the coloring:

The boxes marked by dots above are the possible locations of $n+1=43$ in $T’$. However, only some of these boxes are “valid” locations, namely the ones just to the right of a consecutive run of columns whose top square is red, as shown below with the squares marked $\ast$:

If the $n+1$ in $T’$ is instead located on one of the non-$\ast$ corner squares above, then we define $p_{T’}(\mathbf{e}’,q)=0$. Otherwise, if we label the columns containing $\ast$ by $0,1,\ldots,k$ from left to right, we define

\[p_{T’}(\mathbf{e}’,q)=\varphi^{(r)}_i(T,q) p_T(\mathbf{e},q)\]

where $\varphi^{(r)}_i(T,q)$ is a multiplier defined for $i=0,1,\ldots,k$ which we now define in a slightly more visual way than Hikita (see Hikita’s $\delta$ sequences of $0$’s and $1$’s, which we translate into a combinatorial count on the tableau diagram). Let $C$ be the $i$-th column from the left that contains a $\ast$ (where we zero-index these columns). We call a column red if it contains a red square and blue otherwise.

Let $b$ be the number of blue columns to the left of column $C$. Then, we read the columns to the left of column $C$ from right to left, and let $r_1$ be the length of the rightmost run of red columns to the left of $C$, and $b_1$ the rightmost run of blue columns, then $r_2$ the length of the next run of red columns, and so on. Similarly let $b_1’, r_2’, b_2’,r_2’,\ldots$ be the lengths of the runs of blue and red columns weakly to the right of column $C$. Then we define

\[\varphi^{(r)}_i(T,q)=q^d \frac{(r_1)_q}{(r_1+b_1)_q}\frac{(r_1+b_1+r_2)_q}{(r_1+b_1+r_2+b_2)_q}\cdots \cdot \frac{(b’_1)_q}{(b’_1+r’_1)_q}\frac{(b’_1+r’_1+b’_2)_q}{(b’_1+r’_1+b’_2+r’_2)_q}\cdots\]

where the $q$-number $(n)_q$ is the standard $q$-analog $1+q+q^2+\cdots+q^{n-1}$. For instance, in the example above, we have

\[\varphi^{(36)}_2(T;q)= q^4 \frac{(1)_q}{(4)_q}\frac{(5)_q}{(6)_q}\cdot \frac{(1)_q}{(3)_q}\frac{(6)_q}{(8)_q} \]

where the numbers appearing in the numerator and denominator correspond to the lengths from column $C$ to the ends of the red and blue runs, at left of the $\ast$ and then weakly right of the $\ast$ shown below:

The tableau $T’$ in this case is formed by placing a box labeled $43$ in place of the $\ast$.

Since all of the numerators and denominators are polynomials in $q$ with positive integer coefficients, these transition probabilities $\varphi^{(r)}_i(T,q)$ are indeed positive real numbers for all $q\ge 0$, and hence so are the values $p_T(\mathbf{e},q)$.

Example

Consider the complementary Hessenberg function for the path graph on three vertices shown at the top of this document; the Hessenberg function is $h=(2,3,3)$, so $\mathbf{e}=(0,0,1)$. We can build up the probability distribution for this vector recursively starting from the empty tableau with $p_\emptyset(\emptyset,q)=1$ as follows. For $r=\mathbf{e}(1)=0$, we have nothing colored, so we put a star in the lower left corner of the empty tableau and that is where we must place the box $1$; the transition probability $\varphi^0_0(\emptyset;q)$ is the empty product, which is $1$, so

\[p_{\boxed{1}}((0),q)=1\]

Then, our next value of $r$ is $r=\mathbf{e}(2)=0$, which colors the box $1$ red, and so we must add the $2$ to the right of the $1$ rather than on top, again with transition probability $1$:

We can now focus on the horizontal domino since the vertical domino has probability $0$. For the last step, we have $r=\mathbf{e}(3)=1$, so we only color the $2$ red and there are two valid places to put the $3$:

For the first position, we calculate $\varphi_0=\frac{(1)_q}{(2)_q}=\frac{1}{1+q}$, and for the second, we calculate $\varphi_1=q\frac{(1)_q}{(2)_q}=\frac{q}{1+q}$. This forms a probability distribution on all tableaux of size $3$, and adding them up we find

\[p_{(2,1)}((0,0,1),q)=\frac{1}{1+q} \hspace{1cm} p_{(3)}((0,0,1),q)=\frac{q}{1+q} \]

We can check that this matches the coefficients of the elementary symmetric function expansion of the chromatic quasisymmetric function of the path graph calculated above; indeed, we had the coefficients $c_{(3)}=1+q+q^2$ and $c_{(2,1)}=q$. We have $|\mathbf{e}_{(3)}|=0$ and $|\mathbf{e}_{(2,1)}|=2$, so for the partition $(2,1)$ we have

\[q^{|\mathbf{e}|-|\mathbf{e}_{(2,1)}|}\frac{c_{(2,1)}}{(2)_q!(1)_q!}=q^{1-2}\frac{q}{1+q}=\frac{1}{1+q}\]

and for the partition (3) we have

\[q^{|\mathbf{e}|-|\mathbf{e}_{(3)}|}\frac{c_{(3)}}{(3)_q!}=q^{1-0}\frac{1+q+q^2}{(1+q)(1+q+q^2)}=\frac{q}{1+q}\]

which matches the probabilities constructed above.

Why does this work?

The proof that these probabilities match the desired scaled coefficients relies on the modular law due to Abreu-Nigro, which allows one to reduce the computation to the case where the complementary Hessenberg function is of the form $\mathbf{e}_\lambda$ for some $\lambda$. From there, it is a messy algebraic computation and induction to get everything to work! I went through it and it looks correct; assuming Hikita’s referee agrees, the Stanley-Stembridge conjecture has been proven!