Permutations et polymères aléatoires

 On s’intéressera dans l’exposé au problème suivant, appelé problème d’Ulam: si on prend une permutation s de {1,…,n} au hasard, uniformément parmi toutes les permutations possibles, quelle est la longueur de la plus longue sous-suite croissante de s(1), s(2),…, s(n) ?Ce problème d’apparence simple est en réalité très riche, et on verra qu’il est relié à certaines modèles de physique statistique, dont un modèle de polymère aléatoire.