Algorithmic Group Theory

BGSMath graduate course, fall 2015.

• Lecturers: Enric Ventura (UPC) and Pep Burillo (UPC).
  
• Schedule:  Monday and Friday 12h-14h, from Oct. 5 2015.
  
• Location: Room 102, Facultat de Matemàtiques i Estadística, (UPC)
  
• Summary:  In this course we propose a trip through modern infinite group theory with a special emphasis on algorithmic issues. Assuming only general mathematical knowledge, we want to bring participants close to the edge of the current research in this area. We start with the modern graphical solutions to many algorithmic problems about free groups. We continue by studying the Word Problem and its special behaviour in the world of hyperbolic groups. Finally, we end the course stablishing some classical unsolvability theorems, and visiting also some modern negative results of this kind: there exists no algorithm to solve such and such problem about groups.
• Material: Slides for Stallings graphs (version 4)
  
• Contents:
  • 1- Stallings graphs and free groups. Introduction to the free group. Stallings graphs. The bijection between core graphs and subgroups. Algorithms based on Stallings graphs: membership, index of a subgroup, Marshall Hall’s theorem, residual properties, the Howson property, computation of intersections, decomposition of automorphisms, Takahasi’s theorem and algebraic extensions.
  • 2- The Word Problem. Introduction to the Word Problem and elementary solutions: abelian groups, the free group. Residually finite groups. Normal forms. Examples: braid groups, Thompson’s groups, automatic groups. Van-Kampen diagrams, area and Dehn functions. Recursive Dehn functions. Groups with very high Dehn functions (exponential, superexponential, the Ackermann functions). Hyperbolic Groups. High-genus surface groups and their embeddings in the hyperbolic plane. Dehn’s algorithm to solve the Word Problem in surface groups.
  • 3- Hyperbolic groups in the sense of Gromov. Different definitions and equivalences.The triangle conditions, thin triangles, comparison triangles. Generalization of Dehn’s algorithm to any hyperbolic group. The fundamental characterization theorem: a finitely presented group is hyperbolic if and only if its Dehn function is linear and if and only if it admits a Dehn-like algorithm for the solution of its Word Problem.
  • 4- Unsolvability results. Novikov and Boone: groups with unsolvable Word Problem, finitely presented examples. Many other unsolvability results: isomorphism problem, Markov properties, etc. The Conjugacy Problem, C.F. Miller’s negative examples. The Mihailova construction, F2 x F2 and its pathological subgroups. Twisted Conjugacy Problem and the short exact sequence theorem. Orbit Decidability Problem. The free- (or free abelian-) -by-cyclic and -by-free cases.
    
• Bibliography:
  • O. Bogopolski, A. Martino, and E. Ventura. Orbit decidability and the conjugacy problem for some extensions of groups. Trans. Amer. Math. Soc., 362(4):2003–2036, 2010.
  • Will Dison and Timothy R. Riley. Hydra groups. Comment. Math. Helv., 88(3):507–540, 2013.
  • David B. A. Epstein, James W. Cannon, Derek F. Holt, Silvio V. F. Levy, Michael S. Paterson, and William P. Thurston. Word processing in groups. Jones and Bartlett Publishers, Boston, MA, 1992.
  • Étienne Ghys and Pierre de la Harpe. Sur les groupes hyperboliques d’après Mikhael Gromov (Bern, 1988), volume 83 of Progr. Math. Birkhäuser Boston, Boston, MA, 1990.
  • M. Gromov. Hyperbolic groups. In Essays in group theory, volume 8 of Math. Sci. Res. Inst. Publ., pages 75–263. Springer, New York, 1987.
  • Roger C. Lyndon and Paul E. Schupp. Combinatorial group theory. Classics in Mathematics. Springer-Verlag, Berlin, 2001. Reprint of the 1977 edition.
  • Alexei Miasnikov, Enric Ventura, and Pascal Weil. Algebraic extensions in free groups. In Geometric group theory, Trends Math., pages 225–253. Birkhäuser,Basel, 2007.
  • Charles F. Miller, III. On group-theoretic decision problems and their classification. Princeton University Press, Princeton, N.J.; University of Tokyo Press, Tokyo, 1971. Annals of Mathematics Studies, No. 68.
  • Charles F. Miller, III. Decision problems for groups —survey and reflections. In Algorithms and classification in combinatorial group theory (Berkeley, CA, 1989), volume 23 of Math. Sci. Res. Inst. Publ., pages 1–59. Springer, New York, 1992.
  • Joseph J. Rotman. An introduction to the theory of groups, volume 148 of Graduate Texts in Mathematics. Springer-Verlag, New York, fourth edition, 1995.
  • John R. Stallings. Topology of finite graphs. Invent. Math., 71(3):551–565,1983.

© Enric Ventura Capell, 1999

Retorn pàgina principal.