# Combinatorics of index sets multiplicities in characters of symmetric groups

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

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