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

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 =(l₁,l₂, ...,l_N) of a nonnegative integer n=n(l)=å_i=1^Nl_i, the summands l_i are in decreasing order, and r_k(l) denotes the multiplicity of k, i.e. r_k(l)=#{j|l_j=k}. Let P_n denote the set of partitions of the integer n, and set P=È_n P_n.

One of the questions addressed by this talk is to scale the associated Young diagram j_l(t) defined on [0,+¥] by

(t)=

k³ t

r_k(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 ( F_k)_{k³ 1} of generating functions

_k(x)=

r³ 0

s_k(r)x^r,

as follows: it defines a measure µⁿ on P_n through

µⁿ(l)=Q_n^-1

s_k(r_k(l))=Q_n^-1F(l),

in which Q_n is chosen so that µⁿ is a probability measure on P_n. Assuming that the series

(x)=

n³ 0

Q_nxⁿ

converges for xÎ[0,x₀), a probability measure µ_x is then defined on P as follows:

µ_x=

Q_n xⁿ µⁿ

F(x)

One derives the following facts easily:

F(x)=Õ_{k³ 1} F_k(x^k);
according to the measure µ_x, the r_k's are independent random variables;
the conditional law of a partition l, given that lÎ P_n, is µⁿ.

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 P_n. Let µⁿ(l)=p(n)^-1, in which p(n)=# P_n is the Euler function, F_k(x)=1/(1-x) does not depend on k, and as expected:

F (x)=

Õ

k³ 1

1

1-x^k
;
Uniform statistics on partitions with different summands. F_k(x)=1+x, giving

µ_x(l)=x

n(l)

+¥

Õ

k=1
(1+x^k)^-1;
Bell's statistics. Here µⁿ can be seen as the law of the projection on P_n of a random partition of a set with n elements, giving:

µⁿ(l)=

1

Õ

k
r_k(l)! (k!)

r_k(l)

, F_k(x)=e^y/k!, F (x)=e

e^x-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
r_k(l)! k

r_k(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]ⁿ= q(q+1)···(q+n-1).

2 Limit Shapes and Scaling

For a sequence a=(a_n)_{n³ 0}, let t_al denote the scaled Young diagram t|®a_n(l)j_l(a_n(l)t)/n(l), and for any measure µ on P, let t_aµ denote the image of µ under t_a. Ergodicity occurs when there exists a normalizing sequence a, such that t_aµⁿ 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 t_aµⁿ when n® +¥ from the convergence of t_aµ_x when x® x₀, the latter convergence being easier to prove owing to the independence of r_k'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

[1]: 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.
[2]: 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 L^AT_EX by H^EV^EA.