Anne-Laure Basdevant (LPSM, Sorbonne Université)
Problème d'Ulam et lignes d'Hammersley
Un des problèmes posés par S. Ulam concerne l’asymptotique de la longueur de la plus longue sous suite croissante d’une permutation aléatoire de taille n. De nombreux chercheurs ont étudié ce problème et ont proposé différentes preuves montrant que celle-ci est d’ordre 2\sqrt{n}. Nous expliquerons dans cet exposé l’une d’elle qui fait intervenir un système de lignes aléatoires, appelées « lignes d’Hammersley ». Nous verrons que cette approche peut aussi s’adapter à d’autres problèmes, en espace discret par exemple, ou sur des arbres.
