MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.
share|cite|improve this question
By "non-empty subsets" you mean "non-empty intervals"? – darij grinberg May 26 '13 at 17:03
Oh yeah sure. I will correct that. – Johannes Hahn May 26 '13 at 17:33
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$. – Mark Wildon May 26 '13 at 23:27
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\}$. – Mark Wildon May 26 '13 at 23:34
Another typo. I will correct that. Thanks to you too, Mark. – Johannes Hahn May 27 '13 at 14:33
up vote 10 down vote accepted

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

share|cite|improve this answer
Thank you. In other words: I should have looked at more examples... Next time. :-) – Johannes Hahn May 27 '13 at 14:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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