Version française / Séminaires
Séminaire MODAL'X : Delphin Sénizergues (Modal'X)
Publié le 8 octobre 2025
–
Mis à jour le 20 octobre 2025
Plus grand sous-arbre induit positif dans un grand arbre binaire uniforme p-signé
Date(s)
le 23 octobre 2025
14h00 - 15h00
Lieu(x)
Résumé : Pour un entier n donné, on considère un arbre T_n choisi uniformément au hasard parmi les arbres binaires à n feuilles et on étiquette chacun de ses noeud internes par un signe +/ -, choisis de manière i.i.d. avec probabilité p / (1-p). On s'intéresse à la variable aléatoire X_n associée qui compte la taille du plus grand sous-ensemble de feuilles qui induit dans T_n un sous-arbre n'a que des signes + sur ses noeuds. Le problème original vient du fait que l'arbre T_n encode en fait une permutation aléatoire et le X_n considéré compte la longueur de la plus grande sous-suite croissante de cette permutation.
On montrera que quand n est grand, X_n se comporte comme n^\alpha avec un exposant \alpha=\alpha(p) et on discutera plus précisément de la valeur de \alpha(p).
(Travail en commun avec Arka Adhikari, Jacopo Borga, Thomas Budzinski et William Da Silva, arXiv:2506.19123)
On montrera que quand n est grand, X_n se comporte comme n^\alpha avec un exposant \alpha=\alpha(p) et on discutera plus précisément de la valeur de \alpha(p).
(Travail en commun avec Arka Adhikari, Jacopo Borga, Thomas Budzinski et William Da Silva, arXiv:2506.19123)
Mis à jour le 20 octobre 2025