Joel Hass - Lecture 2 - Algorithms and complexity in the theory of knots and manifolds - 19/06/18

School on Low-Dimensional Geometry and Topology: Discrete and Algorithmic Aspects (http://geomschool2018.univ-mlv.fr/) Joel Hass (University of California at Davis, USA) Algorithms and complexity in the theory of knots and manifolds Abstract: These lectures will introduce algorithmic procedures to study Knots and 3-dimensional manifolds. Algorithmic questions have been part of the study of manifolds since the time of Dehn, and are finding increasing practicality as algorithms and hardware improve. The study of algorithmic procedures often points the way to interesting directions in the theoretical study of manifolds. We’ll begin by reviewing an easy algorithm to classify 2-manifolds, and then outline Markov's argument for the undecidability of 4-manifold recognition. We’ll then turn to 3-dimensions and and study the Unknotting Problem. Using Haken’s ideas on normal surfaces, we’ll describe algorithms that resolve this and related 3-manifold problems. Normal surfaces turn out to have many similarities to minimal surfaces, and we’ll see how this connection leads to an algorithm to recognize the 3-sphere. Finally we’ll discuss the complexity of topological algorithms, allowing us to connect their difficulty to that of problems in numerous other areas, and to get an idea of which problems are compuationally feasible. 2. - From Topology to Algorithms - The undecidability of recognizing 4-manifolds - Normal surfaces as integer vectors - Haken’s equations for normal surfaces - Euler characteristic and Haken sums - Solving integer linear equations – Hilbert’s basis theorem - Fundamental solutions - What algorithms can be derived this way? - Unknotting - Split Link - Knot genus - Constructing hierarchies ---------------------------------- Vous pouvez nous rejoindre sur les réseaux sociaux pour suivre nos actualités. Facebook : https://www.facebook.com/InstitutHenriPoincare/ Twitter : https://twitter.com/InHenriPoincare Instagram : https://www.instagram.com/instituthenripoincare/ LinkedIn : https://www.linkedin.com/company-beta/11054846/