Algorithms for 3-manifolds using crushing

Abstract

For any fixed compact 3-manifold M, there are infinitely many ways to triangulate M. So given two 3-manifold triangulations, how can we algorithmically decide whether or not they triangulate the same 3-manifold? This is the 3-manifold homeomorphism problem, which is (to say the least) very hard. Nevertheless, we might hope that one day, we can eventually develop an algorithm for the homeomorphism problem that is "practical" in the sense that someone can actually run the algorithm and expect a (correct) answer within a reasonable amount of time.

We will see in this talk that building towards this long-term goal is first and foremost a mathematical challenge: we need to develop the "right" theory and techniques before we can begin to consider designing an algorithm, and subsequently translating into software. I will give a quick review of canonical decompositions of 3-manifolds, and then explain how the theory of crushing normal surfaces has evolved over the years to tackle increasingly challenging computational problems in 3-manifold topology. If time permits, this story will culminate in a pair of recent algorithms, developed in joint work with Eric Sedgwick and Jonathan Spreer, for computing the prime factorisation of knots, and for recognising bounded orientable Seifert fibred spaces.