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)

Tentative title: Two-dimensional computational topology

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:

  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

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

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)

To be announced
To be announced

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)

Constructing homotopies of least complexity
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.

Moira Chas (Stony Brooke University, USA)

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 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.

Francis Lazarus (CNRS, Gipsa-Lab, France)

From Isometric embeddings to $C^1$ fractals
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)

To be announced
To be announced

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.

Uli Wagner (IST Austria)

To be announced
To be announced

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