Tentative abstract: This series of lectures will describe
recent and not-so-recent works in computational topology of
curves in the plane and on surfaces. Combinatorial and
algorithmic aspects will be discussed.
Tentative lecture plan:
Historical roots of computational topology
topological invariants, combinatorial encodings, and
algorithms
angle sums, rotation numbers, regular homotopy
winding numbers, signed area, point-in-polygon
graphs and Euler tours
Gauss/Dowker code planarity
Homotopy testing
definitions
polygons with holes: crossing sequence reduction
combinatorial surfaces
tree-cotree decomposition
Euler and discrete Gauss-Bonnet
universal cover
Dehn’s algorithms (classical and modern)
passing mention of Gromov hyperbolicity, CAT(0)
spaces
Shortest paths and cycles
Dijkstra’s algorithm
tree-cotree decompositions again
pivots and slack
multiple-source shortest paths
shortest nontrivial cycles
combinatorial vs. Riemannian systole bounds
Maximum flows and minimum cuts
definitions
flow-cut duality, graph duality, Poincaré duality
planar minimum cuts via MSSP
$\ZZ_2$-homology
$\ZZ_2$-homology cover
surface mincut via MSSP in homology cover
planar flows via shortest-path pivoting
surface flows via implicit homology-LP
Curve simplification
homotopy moves
loops and bigons (Steinitz, Hass and Scott)
plane: $\Omega(n^{3/2})$ via defect
plane: $O(n^{3/2})$ via tangles and depth
surface: $\Omega(n^2)$ via winding distance
surface: $O(n^4)$ via singular bigons and graph
moves
Joel Hass
(University of California at Davis, USA)
Title: 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.
Tentative lecture plan:
Introduction: Algorithmic procedures to study Knots and 3-Manifolds
Initial attempts based on Reidemeister moves and monotonic
simplifications
Kneser’s Normal curves and normal surfaces and their
relationship to minimal surfaces
Normalization rpocedures for curves and surfaces
Optional: Kneser’s Theorem on connect sums
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
3-sphere Recognition
Index one minimal surfaces and almost normal surfaces
Almost normal surfaces and recognizing the 3-sphere
Issues of Computational complexity
The classes P, NP, coNP, (and perhaps EXP, PSPACE)
The complexity of unknotting
3-MANIFOLD KNOT GENUS is NP complete
Some other complexity results
Lower bound questions: Unknotted polygons requiring
exponentially many triangles
Bounding Reidemeister moves
Random models: how to choose knots and 3-manifolds at
random
Discrete Morse theory is a combinatorial tool to
simplify a given triangulation, while maintaining its homotopy type. We
sketch the basics of this theory and explore the connection with classical
Morse theory.
Topological measures of similarity (for curves on surfaces, mostly)
The question of how to measure similarity between curves in various settings has received much attention recently, motivated by applications in GIS data analysis, medical imaging, and computer graphics. Geometric measures such as Hausdorff and Fréchet distance have efficient algorithms, but often are not desirable since they do force any deformation based on them to move continuously in the ambient space. In this talk, we'll consider measures that instead are based on homotopy or homology. Such deformations will generally look to minimize some quantity associated with the homotopy or homology, such as total area swept or longest intermediate curve. We will survey several measures (both geometric and topological) which have been introduced and studied in recent years, giving structural properties as well as considering the complexity of the problem or known algorithms to compute it. We will also give an overview of the many remaining open questions connected to this area.
Can we replace a homotopy of curves on a surface with an isotopy of curves without increasing lengths? Can we replace an isotopy of curves with one composed of pairwise disjoint curves also without increasing lengths? If we have a map between finite simplicial complexes of Lipschitz constant $L$, and if this map is null-homotopic, then what is the minimal Lipschitz constant of a null-homotopy? All of these questions seek to understand the minimal geometric or topological complexity of a homotopy under constraints. In addition to discussing the solutions to these problems, I will describe some applications to bounding the complexity of null-cobordisms, and to proving the existence of minimal surfaces in noncompact manifolds. This talk will contain work with Regina Rotman, Yevgeny Liokumovich, Shmuel Weinberger, Fedor Manin, Dominic Dotterrer, Erin Chambers, Tim Ophelders, and Arnaud de Mesmay.
Computer driven questions, pre-theorems and theorems in geometry.
Several numbers can be associated to free homotopy class $X$ of closed curves on a surface $S$ with negative Euler characteristic. Among these,
the self-intersection number of $X$
the word length of $X$
the length of the geodesic corresponding to $X$
the number of free homotopy classes of a given word length the mapping class group orbit of $X$.
The interrelations of these numbers exhibit many patterns when explicitly determined or approximated by running a variety of algorithms in a computer.
We will discuss how these computations lead to counterexamples to existing conjectures and to the discovery of new patterns. Some of these new patterns, so intricate and unlikely that they are certainly true (even if not proven yet), are "pre-theorems". Many of these pre-theorems later became theorems. An example of such a theorem states that the distribution of the self-intersection of free homotopy classes of closed curves on a surface, appropriately normalized, sampling among given word length, approaches a Gaussian when the word length goes to infinity. An example of a counterexample (no pun untended!) is that there exists pairs of length equivalent free homotopy classes of curves on a surface $S$ that have different self-intersection number. (Two free homotopy classes $X$ and $Y$ are length equivalent if for every hyperbolic metric $M$ on $S$, $M(X)=M(Y)$).
This talk will be accessible to grad and advanced undergrad students.
It is well known that spheres are rigid as convex
surfaces, even without any regularity assumption (Pogorelov, 1973). But
spheres are also rigid as $C^2$ surfaces as follows from the celebrated
Gauss's theorema egregium. One of the unbelievable consequences of the work
of Nash (1954) and Kuiper (1955) is that removing the convexity and $C^2$
assumptions, spheres become flexible $C^1$ surfaces. In other words, the
standard Euclidean sphere admits isometric deformations with a tangent
plane everywhere. In the handbook of convex geometry (1993), Connelly
admits: "I know of no explicit construction of such a flex or even of an
explicit $C^1$ embedding [of the sphere] other than the original sphere." I
will describe how the HEVEA team succeeded to produce such an explicit
embedding.
Quantifying the sparseness of simple geodesics on
hyperbolic surfaces
The set of simple closed geodesics on a hyperbolic surface has been studied from multiple perspectives. In particular, a classical result of Birman and Series states that for a given surface, the set of points that lie on any of its simple closed geodesics is Hausdorff dimension 1. In particular this means that simple closed geodesics are nowhere dense on the surface. This is in stark contrast to what happens with flat tori or with the set of closed (but not necessarily simple) geodesics which is dense in the unit tangent bundle for hyperbolic surfaces.
Together with P. Buser, we’ve produced quantitive versions of this non-density. More specifically, in a given region of the surface, we show the existence of closed disks disjoint from all simple complete geodesics and with a radius that depends only on the topology of the surface. The methods are quite combinatorial in nature and include ways of encoding the set of simple closed geodesics.
We show that the following problems are NP-hard: a)
the TRIVIAL SUBLINK PROBLEM, the problem of deciding whether a link in
the 3-sphere has an n component trivial sub-link, and b) the UNLINKING
PROBLEM, the problem of deciding whether a link in the 3-sphere can be
made trivial by changing n crossings. This work is related to the
authors' recent result that EMBED2->3, the problem of deciding whether a
2-complex embeds in 3-space, is NP-hard.
Joint work with: Arnaud de Mesmay, Yo'av Rieck and Martin Tancer.
Geometric and topological data analysis for graphs
Graphs form one of the most important types of data in various applications across science and engineering. They could be geometric in nature, such as road networks in GIS, or relational and abstract, such as protein-protein interaction networks. In this talk, I will give three examples where topological and geometric ideas can be used to analyze various forms of graph data. In particular, we will discuss the reconstruction of hidden geometric graphs from density data, the recovery of graph metrics from noisy observation, and the comparison of metric graphs. In each of the case, we aim to also provide theoretical understanding and guarantees. Through these topics, I hope to illustrate how geometric and topological ideas can be very useful in the (qualitative) analysis of graphs.
Acknowledgments. This school is funded by the
Bézout Labex.
We also gratefully acknowledge support from
Institut Henri Poincaré.
The image at the top of this page is a Chen Gackstatter surface
created with
3D-Xplormath.