Tentative abstract: This series of lectures will describe
recent and not-so-recent works in computational topology of
curves and graphs in the plane and on surfaces. Combinatorial and
algorithmic aspects will be discussed.
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
The Classification of homotopy classes of bounded curvature paths: Towards a metric knot theory
In 1887 Andrey Markov introduced the concept of bounded curvature path while studying optimality problems associated with the construction of the Trans-Siberian railway. In 1957 Lester Dubins introduced the first mathematical results in the study of bounded curvature paths. Subsequently, in 1961 Dubins proposed a program on the classification of the homotopy classes in spaces of these paths. In this talk, I will describe how this classification was achieved, and how the techniques developed can be applied in the study of physical knots.
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.
The tabulation of all prime knots up to a certain number of crossings was one of the founding problems of knot theory in the 1800s, and continues to be of interest today. Here we take a tour through the many and varied software challenges required to tabulate all 350 million prime knots up to 19 crossings (a task which was finished just last month). Sights along the way include combinatorial, algebraic and geometric computations, along with a mix of theoretical algorithm design and practical algorithm engineering.
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.
Is the hemisphere a minimal isometric filling of its
boundary circle, or can it be replaced by a Riemannian surface of smaller
area without reducing the distance between any boundary points? Gromov
posed the question and proved the strict minimality of the Euclidean
hemisphere among surfaces homeomorphic to a disk. Ivanov considered more
general Finsler metrics and proved that the Euclidean hemisphere is still
minimal among disks, but there are many other Finsler disks that
isometrically fill the circle and have the same area. In this talk I will
present a discrete version of the problem: Can a cycle graph of length $2n$
be filled isometrically with a square-celled combinatorial surface made of
less than $n(n-1)/2$ cells? (The filling is said isometric if the distance
between each pair of boundary vertices, measured along the 1-skeleton graph
of the filling surface, is not smaller than the distance along the boundary
cycle.) This discrete question is equivalent (!) to the continuous problem
for self-reverse Finsler metrics, and is related to some known problems and
structures, including: pseudo-line arrangements, minimizing the number of
crossings between curves on surfaces, discrete differential forms, posets
(including permutations with the Bruhat order), integral polygons, CAT(0)
cubical complexes, integer linear programming, electrical networks and
plabic graphs.
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.
Singular euclidean structures on surfaces are a key tool in the study of the mapping class group, of Teichmüller space, and of kleinian three-manifolds. François Guéritaud, while studying work of Ian Agol, gave a powerful technique for turning a singular euclidean structure (on a surface) into a triangulation (of a three-manifold). We will give an exposition of some of this work from the point of view of Delaunay triangulations for the $L^\infty$ metric. We will review the definitions in a relaxed fashion, discuss the technique, and then present applications to the study of strata in the space of singular euclidean structures. If time permits, we will also discuss the naturally occurring algorithmic questions.
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.
When we view a knot $K$ in the $3$-sphere
$\mathbb{S}^3$, things happening in the $4$-ball $\mathbb{B}^4$ bounded
by $\mathbb{S}^3$ can give us information on $K$.
A classical example is Joel Hass's characterization of ribbon knots on
$\mathbb{S}^3$ using minimal disks in the $4$-ball, minimal surfaces
being the mathematical formulation for soap bubbles (I will recall the
exact definition). Also, torus knots are associated to singularities of
complex curves in $\mathbb{C}^2$, e.g. the cusp $z_1^2+z_2^3=0$ in
$\mathbb{B}^4$ is bounded by the trefoil knot ($(2,3)$ torus knot) in
$\mathbb{S}^3$.
This generalizes to minimal disks in $\mathbb{R}^4$ with an isolated singularity at the origin: intersecting such disks with the $3$-sphere gives rise to a new class of knots, called minimal knots, and the building blocks of these knots are the Lissajous toric knots. In a torus knot, a point goes around a vertical circle $C$ while $C$ rotates around the vertical axis; in a Lissajous toric knot, $C$ is replaced by a Lissajous curve. I will describe Lissajous toric knots, relying mostly on their braid representation (I will recall what braids are). I will conclude with an open question: what are minimal knots in general? Joint work with Marc Soret.
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.
listes
univ-mlv