Algorithmic group theory

Enric Ventura (UPC) and Pep Burillo (UPC)
 Mon-Fri 12h-14h, from Oct. 5 2015
Room 102, Facultat de Matemàtiques i Estadística, UPC

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

  • 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.
  • 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. 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.
  • 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.
  1. 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.
  2. Will Dison and Timothy R. Riley. Hydra groups. Comment. Math. Helv., 88(3):507–540, 2013.
  3. 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.
  4. É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.
  5. M. Gromov. Hyperbolic groups. In Essays in group theory, volume 8 of Math. Sci. Res. Inst. Publ., pages 75–263. Springer, New York, 1987.
  6. Roger C. Lyndon and Paul E. Schupp. Combinatorial group theory. Classics in Mathematics. Springer-Verlag, Berlin, 2001. Reprint of the 1977 edition.
  7. 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.
  8. 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.
  9. 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.
  10. Joseph J. Rotman. An introduction to the theory of groups, volume 148 of Graduate Texts in Mathematics. Springer-Verlag, New York, fourth edition, 1995.
  11. John R. Stallings. Topology of finite graphs. Invent. Math., 71(3):551–565,1983.