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
Jordi Delgado | UPC
Pascal Weil | Laboratoire bordelais de recherche en informatique (LaBRI), Université Bordeaux I
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
|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|
|Qing Shen||University of Technology, Sydney|
|Lucas Henrique Rocha de Souza||None|
|Nicolas Bitar||Université Paris-Saclay|
|Katie Vokes||University of Luxembourg|
|Kristina Oganesyan||Universitat Autònoma de Barcelona|
|Mallika Roy||Universitat Politècnica de Catalunya|
|Lluis Vena Cros||Universitat Politècnica de Catalunya|
|Paloma López Larios||Universitat Politècnica de Catalunya|
|Juan Jose Rué||Universitat Politècnica de Catalunya|
|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|
|Kasia Jankiewicz||University of California|
|Greyson Meyer||University of California|
|Karel Dekimpe||Katholieke Universiteit Leuven|
|Joren Matthys||Katholieke Universiteit Leuven|
|Lisa Sasso||Katholieke Universiteit Leuven|
|Lore De Weerdt||Katholieke Universiteit Leuven|
|Lukas Vandeputte||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|
|Michael Chapman||Hebrew University of Jerusalem|
|Alex Lubotzky||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|
|Haoyang He||University of Manchester|
|Yongsheng Jia||University of Manchester|
|Jon Merladet Urigüen||University of Southampton|
|Lucía Asencio Martín||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|
|Ash DeClerk||University of Nebraska–Lincoln|
|Audrey Goodnight||University of Nebraska–Lincoln|
|Petra Lynn Vanderhei||University of Nebraska–Lincoln|
|Jake Murphy||Louisiana State University - Baton Rouge|
|Andy Moawad||Miami University|
|Jennifer Beck||University of North Carolina at Greensboro|
|Miquel Saucedo||Centre de Recerca Matemàtica|
|Niyaz Tokmagambetov||Centre de Recerca Matemàtica|
|Iván Chércoles Cuesta||ICMAT|
|Oorna Mitra||Indian Statistical Institute|
For inquiries about this event please contact the research programs coordinator Ms. Núria Hernández at firstname.lastname@example.org