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.