**Where and when:** See timetables.

**Prerequisites:** Nothing strictly required. Basics in graph theory and algorithms will help, as well as a certain taste for mathematics.

**Objective:**
Computational topology is primarily concerned with the development of efficient algorithms for solving topological problems. This course is an introduction to the main tools and concepts in the field. While topology is an old and mature mathematical field, the study of its effective
aspects has only started to flourish in the last decades. We will start with graph theory using planar and surface-embedded graphs to introduce fundamental topological notions as we progress. We then increase the dimension progressively and finish with persistence theory, a blooming topological tool in the analysis of big data.

**Tentative plan:**

- Planar graphs: Jordan theorem, Euler relation, forbidden minors, Tutte embedding.
- Classification of surfaces and surface-embedded graphs, Euler characteristic, canonical systems of loops. Homotopy and homology, greedy generators. Homotopy test, intersection numbers.
- Elementary 3-dimensional topology: triangulations, knots, knot diagrams, Reidemeister moves. Normal surfaces and algorithm to test knot triviality.
- Simplicial complexes and limits of computational topology in high dimensions: Undecidability of the word problem, and therefore undecidability of computations in the fundamental group of a 2-complex, and undecidability of 4-manifold homeomorphism or 5-sphere recognition.
- Persistent homology and applications to topological data analysis.

**Course notes:**

- Introductory course
- Planar graphs,
**Exercise sheet number 1**,**Exercise sheet number 2** - Surfaces
- Homotopy test
- Minimum weight Bases
- Knots and 3-dimensional computational topology
- Undecidability in topology
- Homology computation
- Persistent homology

**Suggested reading:**

- John Stillwell. Classical Topology and Combinatorial Group Theory. Springer, 1995.
- Jonathan L. Gross and Thomas W. Tucker. Topological Graph Theory. Dover Publications, 2001.
- Bojan Mohar and Carsten Thomassen. Graphs on Surfaces. Johns Hopkins University Press, 2001.
- Joel Hass, Jeffrey C. Lagarias, Nicholas Pippenger. The Computational Complexity of Knot and Link Problems. Journal of the ACM (JACM), 46(2), 185-211.
- Herbert Edelsbrunner and John Harer. Persistent homology-a survey. Contemporary mathematics, 2008.

There are also good lecture notes available for a few other courses on Computational Topology. In particular, we recommend the ones of Éric Colin de Verdière, Jeff Erickson and Herbert Edelsbrunner. They do not necessarily cover the same topics, but might provide interesting perspectives on different facets of the subject.

**Validation:** Homework, and work (written report and oral presentation) on a research article.