Problème d’Ulam et lignes d’Hammersley

vendredi 18 novembre 2022, 11h00 - 12h00

Salle du conseil, espace Turing

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.