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.



Combinatorics of index sets multiplicities in characters of symmetric groups
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)$. 


