- Libellé inconnu,
Séminaire MODAL'X : Delphin Sénizergues (Modal'X, Université Paris Nanterre)
Publié le 3 avril 2023
–
Mis à jour le 9 juin 2023
La taille du plus grand sous-arbre commun entre deux arbres binaires à feuilles étiquetées
Date(s)
le 15 juin 2023
13h30-14h30
Lieu(x)
Résumé : On considère des arbres binaires à n feuilles, numérotées de 1 à n.
Pour t_n et t_n' deux tels arbres, on s'intéresse à la taille du plus grand sous-ensemble S de {1,2,...,n} tel que le sous-arbre engendré par les feuilles étiquetées par S dans t_n soit le même que dans t_n'.
Je présenterai des résultats qui traitent de cette quantité dans différents contextes quand n tend vers l'infini.
En particulier, dans le cas où les arbres t_n et t_n' sont tirés uniformément au hasard et de façon indépendante, nous avons montré avec Thomas Budzinski que la taille du sous-arbre commun maximal est typiquement O(n^{1/2-\epsilon}), pour un certain \epsilon>0, ce qui améliore la meilleure borne connue en O(n^{1/2}), obtenue par un argument de premier moment.
Pour t_n et t_n' deux tels arbres, on s'intéresse à la taille du plus grand sous-ensemble S de {1,2,...,n} tel que le sous-arbre engendré par les feuilles étiquetées par S dans t_n soit le même que dans t_n'.
Je présenterai des résultats qui traitent de cette quantité dans différents contextes quand n tend vers l'infini.
En particulier, dans le cas où les arbres t_n et t_n' sont tirés uniformément au hasard et de façon indépendante, nous avons montré avec Thomas Budzinski que la taille du sous-arbre commun maximal est typiquement O(n^{1/2-\epsilon}), pour un certain \epsilon>0, ce qui améliore la meilleure borne connue en O(n^{1/2}), obtenue par un argument de premier moment.
Mis à jour le 09 juin 2023