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
k t
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
as follows: it defines a measure n on Pn through
in which Qn is chosen so that n is a probability measure on Pn. Assuming that the series
F (x)=
n 0
converges for x[0,x0), a probability measure x is then defined on P as follows:
Qn xn n

One derives the following facts easily: Though the Plancherel measure does not fall in the class of multiplicative measures, most important ones do belong to it.

1   Examples

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 tan 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 tan when n + from the convergence of tax 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.


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 (Zrich, 1994). pp. 1384--1394. -- Birkhuser, Basel, 1995.

This document was translated from LATEX by HEVEA.