Résumé : À chaque sous-groupe H du groupe libre, on peut associer un unique graphe, dit graphe de Stallings de H, qui a des propriétés remarquables : il est fini si H est finiment engendré, calculable en temps presque linéaire à partir d'un ensemble de générateurs de H, et il permet de résoudre élégamment et efficacement un grand nombre de problèmes algorithmiques : calcul du rang et d'une base de H, calcul de l'index de H, calcul de l'intersection de deux sous-groupes, résolution du problème de l'appartenance uniforme… Des choses plus exotiques aussi, comme le calcul de la clôture pro-p de H ou de sa clôture algébrique. Comme ce graphe fini est assez contraint, on peut utiliser la combinatoire pour énumérer les graphes de Stallings et donc les sous-groupes, les générer aléatoirement, et aborder des questions asymptotiques : quelle est l'espérance du rang d'un sous-groupe du groupe libre, quelle est la probabilité qu'il soit d'indice fini, etc… On peut aussi évaluer la complexité en moyenne du problème de l'appartenance uniforme. La notion de graphe de Stallings peut être étendue aux sous-groupes quasi-convexes des groupes hyperboliques, et à des classes un peu plus larges. On y conserve la calculabilité. On peut par exemple étendre au groupe modulaire certains résultats algorithmiques et asymptotiques sur le groupe libre. Ma présentation sera appuyée sur la littérature classique (à commencer par Stallings 1983) et sur mes travaux, menés pour l'essentiel avec Frédérique Bassino et Cyril Nicaud.

Dernière modification : Thursday 21 November 2024

Contact pour cette page : Cyril.Banderier at lipn.univ-paris13.fr