Joint Mathematics-Computer Science colloquium
Date: Wednesday, 2nd March, 2022
Time: 10:30 am to 11:45 am
Seminar Hall (this talk will be held in the hybrid mode)
The technique of Stallings graphs
Universitat Politècnica de Catalunya, Spain.
This talk will be about free groups $F_n$. Globally, the lattice of subgroups of a free group is very complicated, but Stallings popularized a graphical technique very useful to understand it, and to effectively work on it. I will remind the (combinatorial) construction of the free group $F_n$, will introduce Stallings graphs, and will explain how are they related to the lattice of subgroups of $F_n$. Then, we'll use these techniques to solve several classical algorithmic problems in free groups: the membership problem, the intersection problem, etc. We'll finish the talk by briefly explaining the main ideas behind a recent new result using Stallings graphs: given a finitely generated subgroup $H\leq F_n$ and an element $w\in F_n$ one can decide whether $w$ is the solution of some non-trivial equation with coefficients in $H$ and, in the affirmative case, find them all.