BGSMATH: Stallings Autòmats i Aplicacions

17/1/23 (2h): Introducció: Grups lliures. Introduirem els grups lliures (des de diversos punts de vista, algebraic, combinatori i categòric) i les seves primeres propietats algebraiques. Presentarem algunes preguntes naturals i exemples que motiven el curs.

19/1/23 (2h): Autòmats i llenguatges. Establirem la connexió entre autòmats (és a dir, gràfics amb determinades decoracions), llenguatges i (subgrups de) el grup lliure. Això inclou diverses definicions rellevants (teòriques de gràfics) juntament amb la prova d'uns quants lemes tècnics crucials per establir aquesta connexió.

24/1/23 (2h): La bijecció de Stallings. Aquesta sessió està dedicada al resultat central de la teoria de Stallings: hi ha una bijecció entre un determinat tipus d'autòmats i la xarxa de subgrups del grup lliure. Insistirem en la computabilitat d'aquest mapa quan estigui restringit a subgrups finits generats (corresponent a gràfics finits). Com a corol·lari, obtenim el Nielsen-Schreier i la computabilitat de bases, entre altres resultats.

26/1/23 (2h): Primeres aplicacions. En aquesta sessió considerarem les primeres aplicacions naturals de la bijecció de Stallings: el problema de pertinença (incloent la reescriptura explícita en termes dels generadors donats) i el problema de conjugació per a subgrups. Destacarem algunes similituds i algunes (grans) diferències entre el comportament de la xarxa de subgrups del grup lliure, la xarxa de subespais d'un espai vectorial.

31/1/23 (2h): Índex i teorema de Marshall Hall. Explicarem la relació entre els vèrtexs dels autòmats i les classes del subgrup. Obtindrem una caracterització gràfica per a subgrups d'índexs finits, i la fórmula d'índex de Schreier relacionant índex i rang. Com a corol·lari també obtenim una demostració del teorema de Marshall Hall, i de la finitud residual dels grups lliures.

2/2/23 (2h) Intersecció de subgrups. Introduïm el producte dels autòmats i veiem la relació amb la intersecció de subgrups. Això ens permetrà deduir la propietat de Howson per a grups lliures (les interseccions de subgrups generats de manera finita sempre es generen de manera finita) i la desigualtat de Hanna-Neumann (eliminar el coeficient 2 ha estat un famós problema resolt recentment amb l'ajuda d'altres tècniques de l'abast d'aquest curs). En el camí, podrem calcular una base per a la intersecció de dos subgrups finits generats. Gairebé al mateix preu, podrem calcular interseccions de classes i entendre la malnormalitat.

7/2/23 (2h) Extensions algebraiques i quocients d'autòmats. Definim la noció d'extensió algebraica entre subgrups d'un grup lliure i demostrem (una versió moderna de) el teorema de Takahasi dient que els subgrups generats de manera finita tenen moltes extensions algebraiques finites, i totes són computables. D'aquest resultat, en deduirem diverses aplicacions algebraiques interessants. 

9/2/23 (2h): Comptar autòmats i comptar subgrups. Introduirem una tècnica recent desenvolupada per comptar (o estimar de manera asimptòtica) la quantitat de subgrups que satisfan determinades propietats. Això es fa comptant autòmats, que es poden veure mitjançant injeccions parcials (formen un monoide invers que generalitza el grup simètric clàssic d'una manera interessant).

14/2/23 (1h): Savi. Una breu introducció al paquet Stallings_graphs per a SageMath, un bon programari destinat a experimentar amb subgrups generats de manera finita de grups lliures (de rang finit).

14/2/23 (1h): Autòmats de Stallings enriquits I. Introduirem i descriurem breument una extensió recent dels autòmats de Stallings: decorant els autòmats amb vectors integrals d'una manera adequada, obtenim una bijecció (similar a la de Stallings) entre un determinat tipus d'autòmats enriquits i la xarxa de subgrups de $. F_n \times Z^m$, el producte directe d'un grup abelià lliure i un grup lliure. Per descomptat, les preguntes algebraiques relacionades amb la part abeliana lliure solen convertir-se en sistemes d'equacions, però la interacció entre les dues parts és interessant i de vegades altament no trivial.

16/2/23 (2h): Autòmats de Stallings enriquits II: Malgrat l'aparent semblança, les gelosies dels subgrups de $F_n$ i $F_n \times Z^m$ es comporten de manera molt diferent, especialment quan considerem les interseccions. Una gran diferència és que el segon no satisfà la propietat de Howson: admet parells de subgrups generats finitament la intersecció dels quals no es genera de manera definitiva. Mirant amb atenció la retirada dels autòmats de Stallings (enriquits), explicarem com decidir quan es genera finitament la intersecció corresponent i, si és així, com calcular un conjunt de generadors per a aquesta. 

1. L. Bartholdi i PV Silva, “Rational subsets of groups”, Capítol 23 de JE Pin “Handbook on automata theory”, EMS Publishing House (2021), 1608 pàgines. Disponible a arXiv:1012.1532.
2. J. Delgado, E. Ventura, “Autòmats de Stallings, un camí d'anada i tornada” (en català). A comparecer al Butlletí de la Societat Catalana de Matemàtiques. Disponible a https://arxiv.org/pdf/2202.07642.pdf
3. J. Delgado i E.Ventura, “Stallings autòmats per a grups abelians de temps lliure: interseccions i índex”. 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. Disponible a https://arxiv.org/pdf/2109.01268.pdf
5. I. Kapovich i A. Myasnikov. “Plegaments de parades i subgrups de grups lliures”. Journal of Algebra 248.2 (febrer de 2002), pàgs. 608–668.
6. A. Miasnikov, E. Ventura i P. Weil. “Extensions algebraiques en grups lliures”. A: Teoria de grups geomètrics. Ed. per GN Arzhantseva, J. Burillo, L. Bartholdi i E.Ventura. Tendències en matemàtiques. Birkhäuser Basilea, gener de 2007, pàgs. 225–253.
7. JR Stallings. “Topologia de gràfics finits”. Inventiones Mathematicae 71 (març. 1983), pàgs. 551–565.
8. NWM Touikan, "Un algorisme ràpid per al procés de plegat de Stallings". International Journal of Algebra and Computation 16(06) (desembre 2006), pàgs. 1031–1045.