Participation at the event is free of charge, but registration is compulsory.

BGSMATH: Stallings Automata and Applications

Sign in
Advanced course / School
From January 17, 2023
to February 16, 2023

Schedule:

17th January - 16th Februrary

Tuesdays and Thursdays, from 16h to 18h.

Registration deadline 12 / 01 / 2023

🖥️ via ZOOM

🗓️ Tuesdays and Thursdays, from January 17 to February 16, 2023

🕘 16h – 18h (CET), UTC +1

course description

lecturers

Enric Ventura | UPC
Jordi Delgado | UPC
Pascal Weil | Laboratoire bordelais de recherche en informatique (LaBRI), Université Bordeaux I

organizer

SYLLABUS

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. 

BIBLIOGRAPHY

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

Name Institution
mohamed byari Abdelmalek Essaâdi University, Faculty of Sciences and Techniques of Tangier
Swarnadeep Choudhury Tripura University (A Central University)
Soumya Dey Krea University
Kaan Doganay Mimar Sinan University
Yves Stalder Université Clermont Auvergne
Wenhao Wang Steklov Mathematical Institute
Joan Galobart UPC
Qing Shen University of Technology, Sydney
Lucas Henrique Rocha de Souza None
Nicolas Bitar Université Paris-Saclay
Katie Vokes University of Luxembourg
Jean-Eric Pin CNRS
Rubén Ballester Universitat de Barcelona
Miquel Saucedo Universitat Autònoma de Barcelona
Francesc Bars Cortina Universitat Autònoma de Barcelona
Kristina Oganesyan Universitat Autònoma de Barcelona
Juan Jose Rué Universitat Politècnica de Catalunya
Paloma López Larios Universitat Politècnica de Catalunya
Lluis Vena Cros Universitat Politècnica de Catalunya
Mallika Roy  Universitat Politècnica de Catalunya
María Cumplido Cabello Universidad de Sevilla
Marcos Escartin Ferrer Universidad de Zaragoza
Henrique Souza Universidad Autónoma de Madrid
Pablo Sánchez Peralta Universidad Autónoma de Madrid
Alejandra Garrido Universidad Autónoma de Madrid
Ignat Soroko University of North Texas
Greyson Meyer University of California
Kasia Jankiewicz University of California
Karel Dekimpe Katholieke Universiteit Leuven
Lore De Weerdt Katholieke Universiteit Leuven
Lukas Vandeputte Katholieke Universiteit Leuven
Joren Matthys Katholieke Universiteit Leuven
Lisa Sasso Katholieke Universiteit Leuven
Douglas Vilela de Paiva Silva Federal University of Minas Gerais
Ado Dalla Costa Federal University of Santa Catarina
Max Gheorghiu University of British Columbia
Anders Cornect Memorial University of Newfoundland
Eric Pope Memorial University of Newfoundland
Eduardo Silva École normale supérieure - Paris
Leon Pernak Saarland University
Emmanuel Rauzy Saarland University
Ioannis Papavasileiou National and Kapodistrian University of Athens
Alex Lubotzky Hebrew University of Jerusalem
Michael Chapman Hebrew University of Jerusalem
Niv Levhari Tel Aviv University
Alberto Cassella University of Milan - Bicocca
Xiaobing Sheng University of Tokyo
André Carvalho University of Porto
António Malheiro Universidade Nova de Lisboa
Georgii Veprev University of Geneva
Letizia Issini University of Geneva
Megan Howarth University of Geneva
Corentin Bodart University of Geneva
Joseph MacManus University of Oxford
Panagiotis Tselekidis University of Oxford
Dario Ascari University of Oxford
Yongsheng Jia University of Manchester
Haoyang He University of Manchester
Jon Merladet Urigüen University of Southampton
Lucia Asencio Martin Newcastle University
Islam Foniqi University of East Anglia
Gemma Crowe Heriot-Watt University
Pubo Huang University of Wisconsin–Madison
Genevieve Walsh Tufts University
Yanlong Hao University of Illinois at Chicago
Audrey Goodnight University of Nebraska–Lincoln
Petra Lynn Vanderhei University of Nebraska–Lincoln
Ash DeClerk University of Nebraska–Lincoln
Jake Murphy Louisiana State University - Baton Rouge
Andy Moawad Miami University
Jennifer Beck University of North Carolina at Greensboro
Niyaz Tokmagambetov Centre de Recerca Matemàtica
Iván Chércoles Cuesta ICMAT
Xabier Legaspi ICMAT
Dominik Francoeur ICMAT
Oorna Mitra Indian Statistical Institute

 For inquiries about this event please contact the research programs coordinator Ms. Núria Hernández at nhernandez@crm.cat​​