Jean-Baptiste Gouéré

Le problème d'Ulam porte sur la longueur de la plus longue sous-suite décroissante d'une permutation aléatoire des entiers entre 1 et n. Cette longueur est également le nombre minimal de sous-suites croissantes nécessaires pour partitionner la suite des n entiers permutés. Elle est également liée à un système de particules en interaction. L'étude de ce problème a été initié par Hammersley en 1972. Dans cet exposé, je présenterai quelques résultats classiques sur ce sujet puis je m’intéresserai à une généralisation dans laquelle nous estimons non pas le nombre minimal de suites croissantes mais le nombre minimal d'arbres croissants nécessaires pour partitionner la suite des n entiers permutés. Travail en collaboration avec A.-L. Basdevant, L. Gerin et A. Singh.