Antoine Genitrini (LIP6, Paris)

L’ensemble des arbres croissants a été étudiée de façon intensive, notamment car il s’agit d’un modèle simple pour de nombreux phénomènes naturels (évolution de graphes). Nous allons nous focaliser sur certaines classes d’arbres croissants. Pour chacune de ces classes, nous mesurerons le nombre de composantes connexes obtenues après avoir supprimé l’ensemble des noeuds ayant une étiquette inférieure à une borne donnée. Cette mesure, appelée taille de coupe, permet notamment l’analyse en moyenne d’un algorithme d’étiquetage d’arbre.