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)

Bâtiment Maurice Allais (G)

Entresol, salle Modal'X (E-27)
Plan d'accès
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)

Mis à jour le 20 octobre 2025