Computational Topology

Lecturers: Francis Lazarus and Arnaud de Mesmay

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:

  1. Planar graphs: Jordan theorem, Euler relation, forbidden minors, Tutte embedding.

  2. Classification of surfaces and surface-embedded graphs, Euler characteristic, canonical systems of loops. Homotopy and homology, greedy generators. Homotopy test, intersection numbers.

  3. Elementary 3-dimensional topology: triangulations, knots, knot diagrams, Reidemeister moves. Normal surfaces and algorithm to test knot triviality.

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

  5. Persistent homology and applications to topological data analysis.

Course notes: we will post the notes as the course advances

Homework: is due Friday, December 9 (before the end of the class). You are supposed to work alone! Solutions may be typed or handwritten, in French or English. Note that in the third exercise, the contractibility test refers to an algorithm that decides, when input a combinatorial surface with nonempty boundary and a closed walk in its graph, if the closed walk can be continuously deformed to a point.


Suggested reading:

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.

Oral presentation: You have to select one project in this list. We recommend that you choose a partner and work by pairs on a project. Each project should be chosen by at most one pair. Try to avoid conflict by discussing your choice with the whole class. The presentation should last 20 mn followed by questions and a short discussion. You may use your own laptop or bring your presentation on a usb key. In this latter case, we ask you to use a pdf file. Each member of a pair should speak approximately the same amount of time. The rough idea is to present the main ideas in the chosen article(s), give some details and say one proof that you find worth be presented. We will take into account that some papers are simpler or shorter than others and adapt our expectation accordingly. Some papers are only accessible via your institution. We nonetheless link each paper to a public version so that you get an idea of the content. When indicated, you should download the final version in the end. Please, send us an email if you have any problem to download a paper.

  1. Minimum cycle and homology bases of surface embedded graphs (Erin W. Chambers, Glencora Borradaile, Kyle Fox and Amir Nayyeri)
  2. Testing homotopy for paths in the plane (Sergio Cabello, Yuanxin Liu, Andrea Mantler and Jack Snoeyink)
  3. Testing Isotopy of Graphs on Surfaces (Eric Colin de Verdière and Arnaud de Mesmay)
  4. Optimally cutting a surface into a disk (Jeff Erickson and Sariel Har-Peled)
  5. Untangling planar curves (Hsien-Chih Chang and Jeff Erickson)
  6. Computing the Geometric Intersection Number of Curves (Vincent Despré and Francis Lazarus)
  7. Homology flows, cohomology cuts (Erin W. Chambers, Jeff Erickson and Amir Nayyeri)
  8. Algorithms for normal curves on surfaces (Marcus Schaefer, Eric Sedgwick and Daniel Stefankovic)
  9. The computational complexity of knot genus and spanning area (Ian Agol, Joel Hass and William P. Thurston)
  10. Linkless and flat embeddings in 3 space and the unknot problem (Ken-Ichi Kawarabayashi, Stephan Kreutzer and Bojan Mohar). Final version.
  11. Hardness of embedding simplicial complexes into R^d (Jirí Matousek, Martin Tancer and Uli Wagner)
  12. Optimal Homologous Cycles, Total Unimodularity, and Linear Programming (Tamal K. Dey, Anil N. Hirani and Bala Krishnamoorty)
  13. Quantifying Homology Classes (Chen, C. & Freedman, D.)
  14. Proximity of Persistence Modules and their Diagrams (Chazal, F.; Cohen-Steiner, D.; Glisse, M.; Guibas, L. & Oudot, S.) and
    Stability of Persistence Diagrams (Cohen-Steiner, D.; Edelsbrunner, H. & Harer, J.) Final version
  15. User's Guide to Discrete Morse Theory (R. A. Forman)
Advanced topics: the following articles are significantly harder, pick them only if you are interested and/or you want to impress us.
  1. Computing all maps into a sphere (Martin Cadek, Marek Krcal, Jiri Matousek, Francis Sergeraert, Lukas Vokrinek, Uli Wagner)
  2. Embeddability in the 3-sphere is decidable (Jiri Matousek, Eric Sedgwick, Martin Tancer and Uli Wagner)