Plus longue sous-suite commune de permutations aléatoires (en ligne)

Mercredi 22 avril 14:00-15:00 - Mohamed-Slim Kammoun - Laboratoire Paul Painlevé, Université de Lille

Résumé : Bukh et Zhou ont conjecturé que pour deux permutations i.i.d, l’espérance de la longueur de la plus longue sous-suite commune est minorée par $\sqrtn$. Ce problème peut se ramener à la compréhension de la plus longue sous-suite croissante de permutations aléatoires. On détaillera le cas où la loi de la permutation est stable sous conjugaison qui peut être traité à l’aide de la compréhension de la structure en cycle de la composée de deux permutations indépendantes.

Plus longue sous-suite commune de permutations aléatoires (en ligne)  Version PDF