Séminaire du 26 mars 07, Samuel Vidal, Université de sciences et technologies de Lille.
Sur le dénombrement et la génération exhaustive des cartes triangulaires.
Nous classifions d'abord les sous-groupes et les classes de conjugaison de sous-groupes, dans le produit libre de deux groupes cycliques ou plus, au moyens d'invariants combinatoires : diverses sortes de diagrammes. Les exemples les plus standards de tels groupes sont les groupes libres à n-générateurs, les groupes cartographiques, le groupe modulaire PSL2(Z). Fort de cette classification nous obtenons ensuite un dénombrement utilisant la théorie des espèces combinatoires de Joyal, de ces divers sous-groupes et surtout de leurs classes de conjugaison. Ces dénombrements ne sont pas tous nouveaux. En effet, pour les groupes libres, le nombre de sous-groupes et de leurs classes de conjugaison était connu. Pour le groupe modulaire et le groupe cartographique le nombre de sous-groupes était connu, mais pas le nombre de leurs classes de conjugaison. C'est un dénombrement non étiqueté qui nécessite l'emploi de séries de Joyal-Pólya. Dans cette situation, celles-ci ont le bon goût de se factoriser un peu miraculeusement ce qui permet un calcul rapide des coefficients. La méthode doit se généraliser sans peine.
Je complèterai éventuellement mon exposé en expliquant l'algorithme qui engendre les diagrammes en temps amortis constant. J'insisterai avant tout sur l'aspect "Cartes Combinatoires".
Virginie Collette
Last modified: Mon May 23 18:32:54 CEST 2005