The $q,t$-Kostka polynomials $K_{\lambda,\mu}(q,t)$ appear as the change of basis coefficients between Macdonald polynomials $H_\mu(x;q,t)$ and Schur functions $s_\lambda(x)$: $$H_\mu(x;q,t)=\sum_{\lambda\vdash|\mu|}K_{\lambda,\mu}(q,t)s_\lambda(x)$$ Macdonald conjectured that $K(q,t)\in\mathbb{N}[q,t]$ and this was proved by Haiman as a consequence of his proof of the $n!$ Conjecture. However, this did not provide a combinatorial formula for $K_{\lambda,\mu}(q,t)$.

If $q$ is set equal to $0$ then you get the one-variable Kostka polynomial $K_{\lambda,\mu}(t)$ (it says this on p. 7 of A lot is known about $K_{\lambda,\mu}(t)$, for example, they come up in describing the cohomology rings of Springer fibers, and they have a closed formula in terms of a statistic called the charge on tableaux on $\lambda$ of weight $\mu$, as explained in another MO post here: How does the grading on the cohomology of a flag variety break up the regular representation of W?.

The charge statistic is easy to describe and compute (Disclaimer!!: maybe what I will write isn't exactly right, like maybe it gives the formula for a transpose of $\mu$ or $\lambda$ and/or multiplies the correct poly by a power of $t^{-1}$... sorry, I only first heard of the charge this weekend over a few glasses of wine and then I tried to remember the algorithm with the aid of some googling to make it give the right answer when $q$ is set equal to $0$ in the matrices that appear here: You put a semistandard Young tableau of weight $\mu=(\mu_1,\mu_2,...,\mu_k)$ on $\lambda$, so fill the boxes of the Young diagram of $\lambda$ with $\mu_1$ $1$'s, $\mu_2$ $2$'s,...,$\mu_k$ $k$'s, in such a way that the entries are nondecreasing in rows and strictly increasing down columns (drawing the Young diagram in the way where the rows get smaller as you go down). Then write a word $w$ which is the sequence of integers you get by reading left to right across each row starting from the bottom row and ending with the top row. So if $\lambda=(3,1)$ and $\mu=(1,1,1,1)$ then there are three possible tableaux $T$ depending on whether you put 4, 3, or 2 in the leg of $\lambda$, and these tableaux give words $w$ that are 4123, 3124, and 2134 respectively. Then to compute the charge of the tableau $T$, you can write $w$ clockwise in a circle and put a dash in between the first letter and last letter of $w$, then starting from the first letter of $w$, going around clockwise, find the first sequence $1,...,k$ in this cyclically written $w$ and remove it from $w$, but in this process, whenever you cross the dash you add $k-j$ to the charge where $j$ was the last letter you plucked out before crossing the dash. Now you have a smaller word $w'$, rinse and repeat on $w'$ but with $k'$ replacing $k$ where $k'$ is the biggest letter of $w'$. And so on. This process ends with the empty word and the charge of $T$. The formula found by Lascoux and Schuetzenberger for $K_{\lambda,\mu}(t)$ is that $$K_{\lambda,\mu}(t)=\sum_{T\hbox{ a semistandard tableau on }\lambda\hbox{ of weight }\mu}t^{\mathrm{charge}(T)}$$ So for $\lambda=(3,1)$ and $\mu=(1^4)$ this produces $K_{\lambda,\mu}(t)=t+t^2+t^3$.

So my first question is, is there really no conjectural formula for $K_{\lambda,\mu}(q,t)$ which looks like a natural generalization of the Lascoux-Schuetzenberger formula for $K_{\lambda,\mu}(t)$? All I can find are statements like that finding a formula for $K_{\lambda,\mu}(q,t)$ is an open problem. The best I found was that there are formulas that work when one partition is a hook or the other partition has at most two columns, but that these formulas are wrong in general (see Conj 5.5 for exactly how quickly they are supposed to go wrong). Also it seems like there was basically no progress on this topic in the last decade. Is that correct? Recently Carlsson and Mellit proved the Shuffle Conjecture, which refines the combinatorial description of the Frobenius character of the diagonal coinvariant ring. This doesn't seem directly related, but according to, at root of both problems are something called LLT polynomials -- is it possible one can work backwards from Carlsson-Mellit, Mellit's works to give a combinatorial description of LLT polynomials and from there to settling the question of a combinatorial description of $K_{\lambda,\mu}(q,t)$? Also, if you look at the tables of Kostka matrices like here, you notice that in any column all the entries have the same number of terms, equal to dimension of $\lambda$ -- in fact this was proved by Macdonald, VI.8.18 in Symmetric Functions and Hall Polynomials -- which suggests that maybe the correct formula should be a sum over standard Young tableaux on $\lambda$, but with statistics to give exponents of $q$ and $t$ which depend somehow on $\mu$. Did anyone find a conjectural formula like that? Is it too naive to think the answer would look like that? Surely people tried and there's just no pattern to be found??

My second question is, besides as the Schur coefficients of Macdonald polynomials, is there anywhere else that the $q,t$-Kostka polynomials indepedently have arisen, without reference to Macdonald polynomials, like how the $t$-Kostka polynomials appeared in cohomology of Springer fibers?

  • 2
    This paper might interest you: As far as I know, it would be a huge breakthrough to even give a conjectural combinatorial formula for the Kostka polynomials (but I am by no means an expert in this area/don't follow it closely, so take that with a grain of salt). – Sam Hopkins Aug 16 '17 at 13:09
  • +1 for the username. – darij grinberg Aug 16 '17 at 14:20
  • 3
    Luc Lapointe gave a wonderful lecture at FPSAC 2017 on some ideas that he and his collaborators have been pursuing. At a very high level, the idea is to refine the Kostka numbers more and more until you finally have a "multiplicity-free" formula, which in effect tells you what the Kostka polynomials are counting. Unfortunately I don't think his talk was recorded but one paper in this direction is As Sam Hopkins said, I don't think that anyone has even a conjectural combinatorial interpretation at the moment. – Timothy Chow Aug 16 '17 at 20:03

To answer some of your questions - note that it suffices to find the Schur-expansion of certain LLT polynomials, in order to figure out the $qt$-Kostka polynomials. There IS a combinatorial description of LLT polynomials, it is quite easy in fact. However, from the definition, it is not clear that they are Schur positive (only monomial and with some easy work, Gessel positive).

Together with G. Panova, in a recent preprint, we connect the LLT polynomials with an open conjecture regarding the $e$-expansion of chromatic symmetric functions (this is also related to the Carlson-Mellit paper).

Now, I have an unpublished, explicit conjecture on the $e$-expansion of (vertical-strip) LLT polynomials, with a straightforward combinatorial statistic. This of course gives the Schur expansion, but there is a slight twist to the problem which introduces signs. My intuition is therefore the following: The Schur-expansion of LLT's is hard, because in reality, the coefficients arise AFTER cancellations in a signed sum (the terms in the sum are easy combinatorial objects).

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.