Des lignes d'Hammersley aux arbres d'Hammersley

par Anne-Laure Basdevant (Université Paris Ouest)

jeudi 7 avr. 2016, 14:00 → 15:00 Europe/Paris

Fokko du Cloux, 1er étage bât. Braconnier, UCBL - La Doua (ICJ)

Le problème d'Ulam consiste à estimer la longueur de la plus longue sous-suite décroissante d'une permutation aléatoire de taille n. En 1972, Hammersley fut le premier à s’intéresser à cette question et à remarquer que cette longueur correspond aussi au nombre minimal de sous-suites croissantes requises pour partitionner les n entiers de la permutation. Dans cet exposé, je rappellerai les différents résultats connus sur cette question puis je m’intéresserai à une généralisation de ce problème dans laquelle nous estimons non pas le nombre minimal de suites croissantes mais le nombre minimal d'arbres croissants requis pour partitionner les n entiers de la permutation. Travail en collaboration avec L. Gerin, J.-B. Gouéré et A. Singh.