Home Register Student support Abstracts Program Participants Local information

School on
Low-Dimensional Geometry and Topology:
Discrete and Algorithmic Aspects

poster minimal surface Institut Henri Poincare

List of abstracts

Main lectures

Jeff Erickson (University of Illinois at Urbana-Champaign, USA)

Title: One-dimensional computational topology

Slides: Lecture 1 (Gauss), lecture 2 (Dehn), lecture 3 (MSSP), lecture 4 (cuts and flows), lecture 5 (untangling).

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:

  1. Historical roots of computational topology
  2. Homotopy testing
  3. Shortest paths and cycles
  4. Maximum flows and minimum cuts
  5. Curve simplification

Joel Hass (University of California at Davis, USA)

Title: Algorithms and complexity in the theory of knots and manifolds

Slides: Lecture 1, lecture 2, lecture 3, lecture 4, lecture 5.

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:

Other invited presentations

Jose Ayala (University of Melbourne, Australia)


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.

Bruno Benedetti (University of Miami, USA)

Discrete Morse Theory: An Introduction
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.

Benjamin Burton (University of Queensland, Australia)

Knot tabulation: a software odyssey
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.

Erin Chambers (Saint Louis University, USA)

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.

Gregory Chambers (Rice University, USA) (cancelled)

Moira Chas (Stony Brooke University, USA) (cancelled)

Marcos Cossarini (IMPA, Brazil)

Discrete geometry of surfaces towards the filling area conjecture


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.

Francis Lazarus (CNRS, Gipsa-Lab, France)

From Isometric embeddings to $C^1$ fractals

Slides, video, project.

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.

Hugo Parlier (University of Luxembourg)

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.

Saul Schleimer (University of Warwick, UK)

An introduction to veering triangulations
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.

Eric Sedgwick (DePaul University, USA)


Hard problems in 3-manifold topology
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.

Marina Ville (CNRS, University of Tours, France)

Knots in the $3$-sphere bounding minimal surfaces in the $4$-ball


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.

Uli Wagner (IST Austria) (cancelled)

Yusu Wang (Ohio State University, USA)

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.

Contact. geomschool2018sep2listessep1univ-mlvsep1fr.

Labex Bezout    Institut Henri Poincare