Lucas Gerin: Plus longue sous-suite croissante dans une multi-permutation

par Lucas Gerin (CMAP, Ecole Polytechnique)

jeudi 4 avr. 2024, 11:00 → 12:00 Europe/Paris

IHP

Le problème d'Ulam (ou Ulam-Hammersley, ou Ulam-Hammersley-Versik-Kerov, ou...) consiste à étudier la longueur de la plus longue sous-suite croissante dans une permutation aléatoire uniforme. Apparu dans les années 60, ce problème a été souvent revisité en mélangeant combinatoire algébrique, calcul des variations, matrices aléatoires, processus aléatoires,... Le but de cet exposé est de rappeler le problème historique et de présenter l'approche "processus" pour le problème d'Ulam sur des k-multipermutations : il s'agit de mots dans lesquels chaque lettre parmi 1,...,n apparaît exactement k fois.
Référence : L.Gerin. The Ulam-Hammersley problem for multiset permutations (preprint, 2023).