Hi everyone.

I'm pondering the following question: I have a Coxeter group $(W,S)$ of type $A_{n-1}$, i.e. the symmetric group $W=Sym(n)$ with the neighbour transpositions as generating set $S=\lbrace (1,2),(2,3),\ldots,(n-1,n)\rbrace$.

There is a natural bijection between subsets $I\subseteq S$ and decompositions $L=(L_1,\ldots,L_k)$ of $\lbrace 1,\ldots,n\rbrace$ into non-empty intervals: In one direction $I\subseteq S$ is mapped onto the decomposition into $W_I$-orbits ($W_I:=\langle I\rangle$ is the parabolic subgroup generated by $I$). In the other direction a decomposition $L_1 \coprod L_2 \coprod \ldots \coprod L_k$ is mapped to $(Sym(L_1)\times\ldots\times Sym(L_k)) \cap S$.

Now choose a partition $\mu \vdash n$ and consider the numbers $K_{\mu,I}:=\langle Res_{W_I}^W \chi^\mu, 1\rangle$ where $\chi^\mu$ is the irreducible character associated to $\mu$. These are Kostka numbers in disguise: $K_{\mu,I}$ does not depend on $I$ but only on the $W$-conjugacy class of $W_I$, i.e. it does not depend on the decomposition $L(I)$ but only the partition $\lambda(I) \vdash n$ that corresponds to the decomposition ($\lambda(I)$ only remembers the size of the chunks of the decomposition and forgets their order). So $K_{\mu,I}=K_{\mu,\lambda(I)}$.

Define the "multiplicity of $I$ in $\mu$" $m_{\mu,I}$ recursively by $m_{\mu,I} := K_{\mu,I} - \sum_{S\supseteq J\supsetneq I} m_{\mu,J}$. In other words $K_{\mu,I} = \sum_{J\supseteq I} m_{\mu,J}$.

I know that the Kostka numbers are notoriously hard to understand but I have the hope that the $m_{\mu,I}$ are a lot simpler. My question is this:

Is it true that for all $n\in\mathbb{N}_{\geq 1}$, $\mu \vdash n$ and $I\subseteq \lbrace 1,\ldots,n-1\rbrace$ the multiplicity $m_{\mu,I}$ is always 0 or 1 ?

It is true for $n\leq 7$. I checked this with a GAP program.

Some notes:

  • Although an almost identical question for arbitrary Coxeter groups makes sense, the statement is false in this generality. The two five-dimensional irreducibles of $W=H_3$ have multiplicities 2 (for the set $\lbrace 2\rbrace$ and $\lbrace 1,3 \rbrace$ respectively). There are also counterexamples for $E_7$ and $E_8$ if I'm remembering correctly. I think the conjecture could maybe also be true for type $B$ but I did not check examples.
  • The question is purely combinatorial in nature but it's coming from representation theory. More precisely I'm interested in $W$-graphs. These are graphs that encode matrix representations of Hecke algebras $H(W,S)$. The vertices of these graphs are labelled with subsets of $S$ and the numbers $m_{\mu,I}$ count the vertices with label $I$ in $W$-graphs with character $\textrm{sgn}\cdot\chi^\mu$ (though the graph itself is not uniquely determined by $\mu$, these multiplicities really only depend on the character of the representation). In particular $m_{\mu,I}$ really is a non-negative integer even if it is not obvious from my definition.
  • 1
    $\begingroup$ Are you sure it is true when $n=6$? Take $\mu = (3,2,1)$ and $I = \lbrace 1,3,5 \rbrace$. Then $I$ corresponds to the partition $(2,2,2)$ and $K_{\mu, I} = 2$. The sets containing $I$ correspond to the compositions $(6)$, $(4,2)$ and $(2,4)$. Since $(4,2)$ dominates $(3,3)$ none of these contributes in the sum defining $m_{\mu,I}$. So $K_{\mu, I} = m_{\mu,I} = 2$. $\endgroup$ – Mark Wildon May 26 '13 at 23:27
  • $\begingroup$ In the question I think $I$ should be a subset of $S$, which is in bijection with $\{1,\ldots,n-1\}$, not $\{1,\ldots,n\}$. $\endgroup$ – Mark Wildon May 26 '13 at 23:34
  • $\begingroup$ Another typo. I will correct that. Thanks to you too, Mark. $\endgroup$ – Johannes Hahn May 27 '13 at 14:33

It can't be true in general that $m_{\mu,I}$ is always 0 or 1. That is because $K_{\mu,1^n}=f^\mu$, the number of standard Young tableaux of shape $\mu$. The maximum value of $f^\mu$ for $\mu\vdash n$ is approximately $\sqrt{n!}$, which is much bigger than $2^n$, the number of sets $I\subseteq\lbrace 1,\dots,n\rbrace$. In fact, this reasoning shows that for fixed $n$, we have $\log\max m_{\mu,I} =\frac 12 n\log n +O(n)$.

  • $\begingroup$ Thank you. In other words: I should have looked at more examples... Next time. :-) $\endgroup$ – Johannes Hahn May 27 '13 at 14:36
  • $\begingroup$ @JohannesHahn Well, Kostka numbers are related to problems where increasing the bounds on the computer won't help - you might find tandfonline.com/doi/full/10.1080/10586458.2017.1361367 interesting, (it is also on arxiv), with examples in the area where a naive computer search would take a [really long time] to discover. $\endgroup$ – Per Alexandersson Mar 14 '18 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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