**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.

- What is an algorithm: Turing machines, halting problem, complexity...
- Algebraic topology for graphs and combinatorial surfaces.
- What we cannot compute: how the undecidability of the Word problem impacts computational topology.

**Course notes:**

- John Stillwell. Classical Topology and Combinatorial Group Theory. Springer, 1995.
- J. Gross, T. Tucker. Topological Graph Theory. Dover Publications, Inc., Mineola, NY, 2001. xvi+361 pp. ISBN: 0-486-41741-7.
- B. Mohar, C. Thomassen. Graphs on surfaces. Johns Hopkins Studies in the Mathematical Sciences. 2001. xii+291 pp. ISBN: 0-8018-6689-8.
- N. Brady, T. Riley, H. ShortThe geometry of the word problem for finitely generated groups. Advanced Courses in Mathematics. CRM Barcelona. Birkhäuser Verlag, Basel, 2007. x+206 pp. ISBN: 978-3-7643-7949-0
- Computational topology course notes.

**Validation:** Midterm and final exam.