I am trying to compute the decomposition of the conjugacy representation of some small symmetric groups. Perhaps someone has undertaken a similar calculation.
My own calculations are quite slow, even for $n = 8$. I suppose my question is how large could one expect to scale this computation, if one desires an explicit decomposition.
I am aware there are estimates of the parameters known for large $n$ (e.g. see http://www.maths.qmul.ac.uk/~twm/ConjRep.pdf).
The multiplicity of the irreducible character of $S_n$ indexed by the partition $\lambda$ of $n$ in the action of $S_n$ on itself by conjugation is the coefficient of the Schur function $s_\lambda$ in the Schur function expansion of $1/(1-p_1)(1-p_2)(1-p_3)\cdots$, where $p_i$ is a power sum symmetric function. (This is an exercise in Chapter 7 of Enumerative Combinatorics, vol. 2.) This makes it very easy to compute the decomposition of the conjugacy action using Stembridge's SF package for Maple. For instance, I computed on my laptop the entire decomposition for $n=20$ in a couple of seconds.
Note added 1/10/14: Originally I inadvertently wrote $1/(1-p_1-p_2-p_3-\cdots)$ instead of $1/(1-p_1)(1-p_2)(1-p_3)\cdots$. This has been corrected. The "incorrect" symmetric function $1/(1-p_1-p_2-p_3-\cdots)$ is also interesting. It is equal to $$ \frac{\sum_{n\geq 0}h_n}{1-\sum_{n\geq 1}(n-1)h_n}. $$ See for instance http://www.math.miami.edu/~wachs/papers/chrom.pdf and let $t\to 1$.
Just some remarks which might be of interest.
1) Functions on every conjugacy class are subrepresentation (highly reducible typically). For S_n both conjugacy class and irreps are parametrized by Young diagrams.
Lemma: functions on conjugacy class contain corresponding irrep. ("Corresponding" means conjugacy class and irrep parametrized by same diagram).
We come to it some time ago, but it might be known to experts. (See some motivation for this question below).
2) Quite an amazing claim was discovered by A.Frumkin and R. Adin: "The conjugacy character of $S_n$ tends to be regular". They prove that in certain sense:
the characters of regular and conjugacy representations are almost the same for large "n".
More precise quantitative results in this direction were obtained in:
Y. Roichman, Decomposition of the conjugacy representation of the symmetric groups, Israel J. Math. 97 (1997), 305–316.
and in recent paper (already quoted by OP):
Here is some speculative motivation for interest in such a question:
Conjugacy classes are known to be in bijection with irreps for all groups. Can we construct at least for some groups such bijection in some "good" way ? It sounds like orbit method. (Where functions on orbit more or less give desired irrep). However in orbit method one takes COadjoint orbits, not the adjoint ones, while conjugacy classes can be seen as exponentials of adjoint orbits. So we need kind of metric to identify adjoint and coadjoint orbits - for reductive groups over C we have Killing form. $S_n$ is reductive group $GL(F_1)$ - "field with one element". So may be some "Killing form" also exists ? The lemma above fits to this picture.
Well, it is extremely speculative. There is orbit method for finite groups, but it works for nilpotent groups, not for groups like $GL(F_q)$, and, of course, $F_1$ is speculation by itself.
