Topology – the area of mathematics concerned with the study of shape – has always been interspersed with combinatorial ideas, therefore it is not surprising that many of its fundamental questions call for an algorithmic solution. This is particularly the case in 3-dimensions, where problems such as UNKNOT RECOGNITION (i.e., deciding whether a closed polygonal loop embedded in the Euclidean 3-space is knotted) and 3-SPHERE RECOGNITION (i.e., deciding whether a given triangulation describes the 3-dimensional sphere) have been driven research for over a century.
In this talk we first revisit the historical connection between topology and theoretical computer science. Then we discuss some fixed-parameter tractable algorithms that can efficiently solve hard problems about 3-manifolds, provided the input triangulation is sufficiently « thin. » Finally, we elaborate on the quantitative relationship between the combinatorial parameter that quantifies the « width » of a triangulation, and classical topological invariants of the underlying 3-manifold.
Joint work with Jonathan Spreer and Uli Wagner.
Salle de séminaire 4B125 (bâtiment Copernic)
5 Boulevard Descartes 77420 Champs-sur-Marne