Journée-séminaire de combinatoire

(équipe CALIN du LIPN, université Paris-Nord, Villetaneuse)

Le 12 décembre 2017 à 15h00 en B107, Pascal Weil nous parlera de : A graph-based method to randomly generate subgroups of free groups

Résumé : The study of random algebraic objects sheds a different light on these objects, which complements the algebraic and the algorithmic points of view. When it comes to finitely generated subgroups of free groups, we have a remarkable graphical representation called the Stallings graph: the Stallings graph of a subgroup H is a finite labeled graph uniquely associated with H, efficiently computed from a set of generators of H (say, given as reduced words), and from which one can efficiently compute many invariants of H. I will discuss enumerating and randomly generating finitely generated subgroups of free groups, for the distribution given by Stallings graphs: for each positive integer n, one considers the finite number of subgroups whose Stallings graph has n vertices, and one considers the uniform distribution on that set. This requires understanding the combinatorial structure of Stallings graphs, which are interesting objects per se. I will also exhibit natural properties of subgroups which are `generic' for this distribution. This is joint work with F. Bassino (LIPN) and C. Nicaud (LIGM)

 [Slides.pdf] [arXiv]

Dernière modification : jeudi 09 novembre 2017 Valid HTML 4.01! Valid CSS! Contact : Cyril.Banderier at