Participation at the event is free of charge, but registration is compulsory.
BGSMATH: Stallings Automata and ApplicationsSign in
to February 16, 2023
17th January - 16th Februrary
Tuesdays and Thursdays, from 16h to 18h.
🖥️ via ZOOM
🗓️ Tuesdays and Thursdays, from January 17 to February 16, 2023
🕘 16h – 18h (CET), UTC +1
Enric Ventura | UPC
17/1/23 (2h): Introduction: Free groups. We will introduce free groups (from several points of view, algebraic, combinatorial, and categoric) and its first algebraic properties. We will present some natural questions and examples motivating the course.
19/1/23 (2h): Automata and languages. We will set up the connection between automata (i.e., graphs with certain decorations), languages, and (subgroups of) the free group. This includes several relevant (graph-theoretical) definitions together with the proof of a few technical lemmas crucial to establish this connection.
24/1/23 (2h): The Stallings bijection. This session is devoted to the central result in Stallings theory: there is a bijection between a certain kind of automata and the lattice of subgroups of the free group. We will stress the computability of this map when restricted to finitely generated subgroups (corresponding to finite graphs). As a corollary, we obtain the Nielsen-Schreier and the computabity of bases, among other results.
26/1/23 (2h): First applications. In this session we will consider the first natural applications of the Stallings bijection: the membership problem (including explicit rewriting in terms of the given generators) and the conjugacy problem for subgroups. We will stress some similarities and some (big) differences between the behaviour of the lattice of subgroups of the free group, the lattice of subspaces of a vector space.
31/1/23 (2h): Index and Marshall Hall Theorem. We will explain the relation between vertices of the automata and cosets of the subgroup. We will obtain a graphical characterization for finite index subgroups, and the Schreier index formula relating index and rank. As a corollary we obtain also a proof of Marshall Hall Theorem, and the residual finiteness of free groups.
2/2/23 (2h) Intersection of subgroups. We introduce the product of automata and see the relation with the intersection of subgroups. This will allow us to deduce the Howson property for free groups (intersections of finitely generated subgroups are always finitely generated), and the Hanna-Neumann inequality (removing the coefficient 2 has been a famous problem solved recently with the help of other techniques out of the scope of this course). On the way, we will be able to compute a basis for the intersection of two finitely generated subgroups. Almost at the same price, we will be able to compute intersections of cosets, and understand malnormality.
7/2/23 (2h) Algebraic extensions and quotients of automata. We define the notion of algebraic extension between subgroups of a free group and prove (a modern version of) Takahasi’s Theorem saying that finitely generated subgroups have finitely many algebraic extensions, and they are all computable. From this result, we will deduce several interesting algebraic applications.
9/2/23 (2h): Counting automata and counting subgroups. We’ll introduce a recent technique developed to count (or asymptotically estimate) the amount of subgroups satisfying certain properties. This is done by counting automata, which can be seen via partial injections (they form an inverse monoid generalizing the classical symmetric group in an interesting way).
14/2/23 (1h): Sage. A brief introduction to the Stallings_graphs package for SageMath, a nice piece of software meant to experiment with finitely generated subgroups of (finite rank) free groups.
14/2/23 (1h): Enriched Stallings automata I. We will introduce and briefly describe a recent extension of Stallings automata: by decorating the automata with integral vectors in an appropriate way, we obtain a bijection (similar to the Stallings one) between a certain kind of enriched automata and the lattice of subgroups of $F_n \times Z^m$, the direct product of a free and a free abelian group. Of course, the algebraic questions related to the free abelian part usually become systems of equations, but the interplay between the two parts is interesting and sometimes highly non-trivial.
16/2/23 (2h): Enriched Stallings automata II: Despite the apparent similarity, the lattices of subgroups of $F_n$ and $F_n \times Z^m$ behave very differently, especially when we consider intersections. A big difference is that the second one does not satisfy the Howson property: it admits pairs of finitely generated subgroups whose intersection is not fnitely generated. By looking carefully at the pull-back of (enriched) Stallings automata, we’ll explain how to decide when the corresponding intersection is finitely generated and, if so, how to compute a set of generators for it.
1. L. Bartholdi and P.V. Silva, “Rational subsets of groups”, Chapter 23 from J.E. Pin “Handbook on automata theory”, EMS Publishing House (2021), 1608 pages. Available at arXiv:1012.1532.
2. J. Delgado, E. Ventura, “Autòmats de Stallings, un camí d’anada i tornada” (in catalan). To appear at Butlletí de la Societat Catalana de Matemàtiques. Available at https://arxiv.org/pdf/2202.07642.pdf
3. J. Delgado and E.Ventura, “Stallings automata for free-times-abelian groups: intersections and index”. Publicacions Matemàtiques 66 (2022), 789–830.
4. J. Delgado, E. Ventura, “A list of applications of Stallings automata”, Transactions on Combinatorics 11(3) (2022), 181—235. Available at https://arxiv.org/pdf/2109.01268.pdf
5. I. Kapovich and A. Myasnikov. “Stallings foldings and subgroups of free groups”. Journal of Algebra 248.2 (Feb. 2002), pp. 608–668.
6. A. Miasnikov, E. Ventura, and P. Weil. “Algebraic extensions in free groups”. In: Geometric Group Theory. Ed. by G.N. Arzhantseva, J. Burillo, L. Bartholdi, and E.Ventura. Trends in Mathematics. Birkhäuser Basel, Jan. 2007, pp. 225–253.
7. J.R. Stallings. “Topology of finite graphs”. Inventiones Mathematicae 71 (Mar. 1983), pp. 551–565.
8. N.W.M. Touikan, “A fast algorithm for Stallings’ folding process”. International Journal of Algebra and Computation 16(06) (Dec. 2006), pp. 1031–1045.
LIST OF PARTICIPANTS
|Juan Jose Rue Perna||Universitat Politècnica de Catalunya|
|Swarnadeep Choudhury||Tripura University (A Central University)|
|Paloma López Larios||Universitat Politècnica de Catalunya|
|Ignat Soroko||University of North Texas|
|Yanlong Hao||University of Illinois at Chicago|
|Pubo Huang||University of Wisconsin–Madison|
|Corentin Bodart||University of Geneva|
|Kasia Jankiewicz||University of California|
|André Carvalho||University of Porto|
|Soumya Dey||Krea University|
|Kaan Doganay||Mimar Sinan University|
|Ioannis Papavasileiou||National and Kapodistrian University of Athens|
|Georgii Veprev||University of Geneva|
|Letizia Issini||University of Geneva|
|Megan Howarth||University of Geneva|
|Eduardo Silva||École normale supérieure - Paris|
|Gemma Crowe||Heriot-Watt University|
|Karel Dekimpe||Katholieke Universiteit Leuven|
|Yves Stalder||Université Clermont Auvergne|
|Eric Pope||Memorial University of Newfoundland|
|Joseph MacManus||University of Oxford|
|Greyson Meyer||University of California|
|Alberto Cassella||University of Milan - Bicocca|
|Anders Cornect||Memorial University of Newfoundland|
|Iván Chércoles Cuesta||ICMAT|
|Douglas Vilela de Paiva Silva||Federal University of Minas Gerais|
|Niyaz Tokmagambetov||Centre de Recerca Matemàtica|
|Wenhao Wang||Steklov Mathematical Institute|
|Panagiotis Tselekidis||University of Oxford|
|Lucía Asencio Martín||Newcastle University|
|Jennifer Beck||University of North Carolina at Greensboro|
|Miquel Saucedo||Centre de Recerca Matemàtica|
|Andy Moawad||Miami University|
|Max Gheorghiu||University of British Columbia|
|Dario Ascari||University of Oxford|
|Kristina Oganesyan||Universitat Autònoma de Barcelona|
|Audrey Goodnight||University of Nebraska–Lincoln|
|Petra Lynn Vanderhei||University of Nebraska–Lincoln|
|Qing Shen||University of Technology, Sydney|
|Lucas Henrique Rocha de Souza||None|
|Nicolas Bitar||Université Paris-Saclay|
|Xiaobing Sheng||University of Tokyo|
|Jake Murphy||Louisiana State University - Baton Rouge|
|Niv Levhari||Tel Aviv University|
|António Malheiro||Universidade Nova de Lisboa|
|Ash DeClerk||University of Nebraska–Lincoln|
|Katie Vokes||University of Luxembourg|
|Jon Merladet Urigüen||University of Southampton|
|Pablo Sánchez Peralta||Universidad Autónoma de Madrid|
|Leon Pernak||Saarland University|
|Emmanuel Rauzy||Saarland University|
|Joren Matthys||Katholieke Universiteit Leuven|
|Alejandra Garrido||Universidad Autónoma de Madrid|
|Marcos Escartin Ferrer||Universidad de Zaragoza|
|Ado Dalla Costa||Federal University of Santa Catarina|
|Henrique Souza||Universidad Autónoma de Madrid|
|Haoyang He||University of Manchester|
|Lisa Sasso||Katholieke Universiteit Leuven|
|Islam Foniqi||University of East Anglia|
|Lore De Weerdt||Katholieke Universiteit Leuven|
|Yongsheng Jia||University of Manchester|
|Lukas Vandeputte||Katholieke Universiteit Leuven|
|Mallika Roy||Universitat Politècnica de Catalunya|
|Michael Chapman||Hebrew University of Jerusalem|
|Alex Lubotzky||Hebrew University of Jerusalem|
|Lluis Vena Cros||Universitat Politècnica de Catalunya|
|Oorna Mitra||Indian Statistical Institute|
|Genevieve Walsh||Tufts University|