Algorithmic Topology and Groups

Lecturers: FranÁois Dahmani and Francis Lazarus

Where and when: Room 14 at Institut Fourier, on Wednesday.

Prerequisites: Nothing strictly required.

Objective: Describing objects by discrete structures has many advantages, but makes all the more clear the limits of our understanding. For instance, one can compute easily presentations of fundamental groups of simplicial complexes, but in general, determining whether this group is trivial is impossible (undecidable). This course proposes an algorithmic approach to treat, in favorable cases, some fundamental problems in topology, often interpreted in terms of problems in fundamental groups. These problems are the homotopy between curves, the existence of homeomorphisms between spaces, and the triviality of a knot. The case of surface groups will be important to us.

The first part will be dedicated to basics notions on algorithms and complexity and on combinatorial group theory. The viewpoint will remain elementary and will be motivated by topological and algorithmic problems on graphs and surfaces.

Tentative plan for this part:
  1. What is an algorithm: Turing machines, halting problem, complexity...

  2. Algebraic topology for graphs and combinatorial surfaces.

  3. What we cannot compute: how the undecidability of the Word problem impacts computational topology.

Course notes:
  •  Prelude Exercise sheet 1
  •  Topology of Graphs Exercise sheet 2
Exercise sheet 3
  •  Topology of Surfaces Exercise sheet 4
  •  Testing Curve Homotopy on Surfaces Exercise sheet 5
  •  Undecidability in Topology Exercise sheet 6

Suggested reading:

Validation: Midterm and final exam.