Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Alexei Oblomkov recently told me about the beautiful theorem of Kerov and Vershik, which says that "almost all Young diagrams look the same." More precisely: take a random irreducible representation of S_n (in Plancherel measure, which assigns a probability of (dim chi)^2 / (n!) to an irrep chi) and draw its Young diagram, normalized to have fixed area. Rotate the diagram 45 degrees and place the vertex at the origin of the Cartesian plane, so that it lies above the graph of y = |x|. Then there is a fixed curve, with equation

$$ y = \left\lbrace \begin{array}{ll} |x|, & |x| > 2 \newline \frac 2\pi \left(x \arcsin\frac x2 + \sqrt{4-x^2}\right), & |x| \leq 2 \end{array}\right.$$

such that the normalized Young diagram is very close to the curve with probability very close to 1.

My question: what asymptotic statements about irreducible characters of S_n can be "read off" the Kerov-Vershik theorem? In a sense, this isn't a question about Kerov-Virshik at all, but a question about which interesting statistics of irreducible characters can be read off the shape of the Young diagram.

There are some tautological answers: for instance, if f(chi) is the height of the first column of chi, then I guess Kerov-Virshik shows that

f(chi) / sqrt(n)

is very probably very close to 2 as n gets large (if I did this computation right -- in any event it concentrates around a fixed value.) But I don't really have in mind any representation-theoretic meaning for f(chi).

share|improve this question
add comment

3 Answers

There is a beautiful interpretation of f(chi) (that is to say, of the length of the first column of the partition), though it isn't very representation-theoretic.

One way to generate Plancherel measure on partitions is to take uniformly at random a permutation of $\{1,\dots,n\}$ and apply Robinson-Schensted-Knuth to get a pair of Young tableaux of the same shape, and then take the partition encoded by that shape.

The length of the first column in the shape corresponding to a permutation $\pi$ is the length of the longest decreasing sequence in $\pi$, while the length of the first row is the length of the longest increasing sequence in $\pi$.

So Kerov-Vershik says (among other things) that the length of the longest decreasing sequence in a random permutation of $\{1,\dots,n\}$ is $2\sqrt{n}$. For more along these lines, see Richard Stanley's 2006 ICM talk.

share|improve this answer
This is so nice that I don't mind it being non-representation-theoretic. –  JSE Dec 14 '09 at 3:00
add comment

This isn't a very general answer, but it is a convenient and significant one. You can read off the typical dimension of a random representation, by the hook length formula. Of course it is not as simple as, oh here's a formula, because you have to check whether the formula is stable. However, the hook-length formula is a factorial divided by a product of hook lengths. So you can check that the logarithm of the formula is indeed statistically stable. Up to normalization, it limits to a well-behaved integral over the Kerov-Vershik shape.

The dimension of a group representation is of course $\chi(1)$, the trace of the identity. Given the nice behavior of this statistic in a random representation, it is natural to ask about the typical value of $\chi(\sigma)$ for some other type of permutation $\sigma$. Two problems arise. First, $\sigma$ isn't really one type of permutation, but rather some natural infinite sequence of permutations. Second, the Murnaghan-Nakayama formula for $\chi(\sigma)$, and probably any fully general rule, isn't statistically stable. The Murnaghan-Nakayama rule is a recursive alternating sum; in order to apply it to a large Plancherel-random representation you would have to know a lot about the local statistics of its tableau, and not just its shape. For instance, suppose that $\sigma$ is a transposition. Then the MN rule tells you to take a certain alternating sum over rim dominos of the tableau $\lambda$. (The sign is positive for the horizontal dominos and negative for the vertical dominos.) I suspect that there is a typical value for $\chi(\sigma)$ when $\sigma$ is a transposition, or probably any permutation of fixed type that is local in the sense that a transposition is local. But this would use an elaborate refinement of the Kerov-Vershik theorem, analogous to the local central limit theorem augmented by a local difference operator, and not just the original Kerov-Vershik.

However, I did find another character limit in this spirit that is better behaved. Fomin and Lulov established a product formula for the number of $r$-rim hook tableaux, which is also $\chi(\sigma)$ when $\sigma$ is a "free" permutation consisting entirely of $r$-cycles (and no fixed points or cycle lengths that are factors of $r$). This includes the important case of fixed-point-free involutions. If $\sigma$ acts on $mr$ letters, then according to them, the number of these is $$\chi_\lambda(\sigma) = \frac{m!}{\prod_{r|h(t)} (h(t)/r)},$$ where $h(t)$ is the hook length of the hook at some position $t$ in the shape $\lambda$.

Happily, this is just a product formula and not an alternating sum or even a positive sum. To approximate the logarithm of this character with an integral, you only need a mild refinement of Kerov-Vershik, one that says that the hook length $h(t)$ of a typical position $t$ is uniformly random modulo $r$. (So this is a good asymptotic argument when $r$ is fixed or only grows slowly.)

Correction: JSE already thought of the first part of my answer, which I stated overconfidently. The estimate for $\log \chi(1)$ (and in the other cases of course) is an improper integral, I guess, so it does not follow just from the statement of Kerov-Vershik that the integral gives you an accurate estimate of the form $$\log \chi(1) = C\sqrt{n}(1+o(1)).$$ However, it looks like these issues have been swept away by later, stronger versions of the original Kerov-Vershik result. The arXiv paper Kerov's central limit theorem for the Plancherel measure on Young diagrams establishes not just a typical limit for the dimension (and other character values), but also a central limit theorem.

share|improve this answer
I thought about this last night and got a bit confused, actually. You might expect that log(dim chi)/sqrt(n) would, with probability 1, lie in a smaller and smaller band around some constant C obtained by an integral, as you say. But I'm not sure this is actually the case; in a later paper, Kerov and Vershik show this quantity is very probably bounded between c_1 and c_2, so it can't be an immediate consequence of their theorem that it approaches a limit. I think maybe the stuff near the boundary with highly negative log-hooklength causes trouble? –  JSE Dec 13 '09 at 19:34
I suppose that you're right; my answer is overconfident. My guess is that the boundary does and doesn't cause trouble. I would be surprised if the integral isn't the truth, but it may take more work to show that the fluctuations at the boundary are predictable enough for convergence. –  Greg Kuperberg Dec 13 '09 at 19:43
add comment

A good paper related to this question is P. Biane, Representations of symmetric groups and free probability , Advances in Mathematics 138, 126-181 (1998), item [4] at http://www.dma.ens.fr/~biane/publi.html.

share|improve this answer
Thanks for pointing out this reference! I'm ashamed to say I had been unaware of Biane's paper---despite the fact that it contains a lot of stuff I find fascinating! –  GS Jan 8 '10 at 14:03
add comment

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.