Permutations aléatoires et leurs liens avec la théorie des matrices aléatoires

Irène Ayuso

Labo. d'Analyse et de Mathématiques Appliquées, Université Gustave Eiffel

Given a random permutation from the symmetric group of order N, consider the length L(N) of its longest increasing subsequence. The Ulam-Hammersley problem consists in studying the asymptotic behavior of the expectation of L(N). The problem was first introduced by Ulam in 1961, and it is Hammersley who, in 1972, proved that L(N) is equivalent to the square root of N, up to a multiplicative constant. There are now several proofs showing that this constant is 2, and in this presentation, we will consider the one given by Kurt Johansson in 1998, involving Unitary Random Matrices. Particularly, we will explore the relationship between the Ulam-Hammersley problem and random matrix theory.