Asymptotic Combinatorics and Representations of Infinite Symmetric Groups (a Survey)

Anatoly Vershik

IHES, Bures-sur-Yvette

Algorithms Seminar

March 8, 1999

[summary by Philippe Chassaing]

A properly typeset version of this document is available in postscript and in pdf.

If some fonts do not look right on your screen, this might be fixed by configuring your browser (see the documentation here).

## Introduction: Multiplicative Measures

In a partition l =(l1,l2, ...,lN) of a nonnegative integer n=n(l)=åi=1Nli, the summands li are in decreasing order, and rk(l) denotes the multiplicity of k, i.e. rk(l)=#{j|lj=k}. Let Pn denote the set of partitions of the integer n, and set P=Èn Pn.

One of the questions addressed by this talk is to scale the associated Young diagram jl(t) defined on [0,+¥] by
j
 l
(t)=
 å k³ t
rk(l)
in order to obtain nontrivial limit shapes, for the family of multiplicative measures on P. A multiplicative measure on P is defined by a sequence ( Fk)k³ 1 of generating functions
F k(x)=
 å r³ 0
sk(r)xr,
as follows: it defines a measure µn on Pn through
µn(l)=Qn-1
 Õ k
sk(rk(l))=Qn-1F(l),
in which Qn is chosen so that µn is a probability measure on Pn. Assuming that the series
F (x)=
 å n³ 0
Qnxn
converges for xÎ[0,x0), a probability measure µx is then defined on P as follows:
µx=
 å n
Qn xn µn
F(x)
.

One derives the following facts easily:
• F(x)=Õk³ 1 Fk(xk);
• according to the measure µx, the rk's are independent random variables;
• the conditional law of a partition l, given that lÎ Pn, is µn.
Though the Plancherel measure does not fall in the class of multiplicative measures, most important ones do belong to it.

## 1   Examples

• Uniform statistics on Pn. Let µn(l)=p(n)-1, in which p(n)=# Pn is the Euler function, Fk(x)=1/(1-x) does not depend on k, and as expected:
F (x)=  Õ k³ 1
1
1-xk
;
• Uniform statistics on partitions with different summands. Fk(x)=1+x, giving
µx(l)=x  n(l)
 +¥ Õ k=1
(1+xk)-1;
• Bell's statistics. Here µn can be seen as the law of the projection on Pn of a random partition of a set with n elements, giving:
µn(l)=
1
 Õ k
rk(l)! (k!)  rk(l)
,     Fk(x)=ey/k!,     F (x)=e  ex-1
;
• Haar's statistics and Poisson-Dirichlet measures. This example is a family µx,q of multiplicative measures. The case q=1 is the partition structure derived from the cycles of a random permutation. The general case arises in various applications in graph theory, or also in genetics under the name of Ewens sampling formula:
µ  n q
(l)=
q  #l
[q]  n(l)
 Õ k
rk(l)! k  rk(l)
,     F k(x)=e  q y/k
,     F (x)=(1-x)  -q
,
in which #l stands for the number of summands of l, and [q]n= q(q+1)···(q+n-1).

## 2   Limit Shapes and Scaling

For a sequence a=(an)n³ 0, let tal denote the scaled Young diagram t|®an(l)jl(an(l)t)/n(l), and for any measure µ on P, let taµ denote the image of µ under ta. Ergodicity occurs when there exists a normalizing sequence a, such that taµn converges weakly to a Dirac mass at a given limit shape. The Plancherel measure, as well as the first cases above, are ergodic, but not the last case, where the weak limit is nondegenerate, and can be expressed in terms of the Poisson-Dirichlet distribution with parameter q. Among the possible tools, a method analog to the saddle-point method allows to derive convergence of taµn when n® +¥ from the convergence of taµx when x® x0, the latter convergence being easier to prove owing to the independence of rk's.

The author also developed on heap problems, roof and entropy, on the Young graph, Kingman problem (partition structures), Ulam problem (length of the longest increasing sequence in a sequence of n numbers) and its connection with the spectrum of Gaussian matrices.

## References


Vershik (A. M.). -- Statistical mechanics of combinatorial partitions, and their limit configurations. Rossiiskaya Akademiya Nauk. Funktsional'nyi Analiz i ego Prilozheniya, vol. 30, n°2, 1996, pp. 19--39.


Vershik (Anatoly M.). -- Asymptotic combinatorics and algebraic analysis. In Proceedings of the International Congress of Mathematicians (Zürich, 1994). pp. 1384--1394. -- Birkhäuser, Basel, 1995.

This document was translated from LATEX by HEVEA.