Combinatorial Structures in Geometric Topology

Abstract

This workshop on Combinatorial Structures in Geometric Topology will focus on computational and combinatorial challenges related to triangulations of manifolds and their secondary combinatorial structures. The goal of the workshop is to foster collaboration between researchers working in the fields of discrete and computational geometry, polytope theory, and low-dimensional topology.

Representing manifolds as triangulations is a very powerful approach to algorithmically solve fundamental problems in low-dimensional topology. They have been successfully used in mathematical software to provide practical solutions to purely theoretical problems involving manifolds. These practical solutions often feature not only the input triangulations, but also secondary combinatorial structures such as polytopes (e.g., the space of angle structures), polyhedral fans (e.g., the solution space of normal surfaces), or associahedra (e.g., flip graphs of triangulations), which are more native to the fields of discrete and computational geometry and polytope theory.

Organisers

• Benjamin A. Burton, The University of Queensland

• Jonathan Spreer, The University of Sydney

List of Abstracts

Full-length invited talks

Hidetoshi Masai, Musashino Art University

Title: Computing Bers slices and renormalized volume 

Abstract: I will discuss the renormalized volume (R-vol) of hyperbolic 3-manifolds. It is known that the derivative of the R-vol can be described in terms of Bers slices, which provide a parameterization of the Teichmueller space. I will present some visualizations and movies related to these Bers slices, obtained during a project on the numerical computation of the R-vol. This talk is based on the joint work with Ryo Matsuda.

Satoshi Murai, Waseda University

Title: Upper bounds and lower bounds of face numbers of triangulated manifolds

Abstract: The study of face numbers of simplicial complexes is a classical theme. This study is also closely related to the Stanley-Reisner theory, which give a commutative algebra technique to study such a problem. I will explain how the Stanley-Reisner theory help to study face numbers of triangulations of higher dimensional manifolds and discuss recent developments as well as open questions on this topic.

Stephan Tillmann, The University of Sydney

Title: Computing shortest curves on convex projective once-punctured tori

Abstract: The task at hand is to compute a shortest loop that cannot be contracted to a point on a surface. This is a classical problem that has been studied in different contexts, and which enjoys practical applications. In the setting of hyperbolic and convex projective geometry, I will describe a simple algorithm to compute the three shortest curves on a once-punctured torus and explain why it works. The algorithm uses an attractive interplay between algebra and geometry -- it is what Jane Gilman coined a "non-Euclidean Euclidean algorithm". This is joint work with Sepher Saryazdi.

Anastasiia Tsvietkova, Rutgers University

Title: Some algorithmically easy and hard problems in knot theory

Abstract: Many knot theory problems that have been studied by mathematicians and physicists for decades and even centuries can be formulated as decision problems. In the last twenty years or so, many results appeared concerning upper bounds on their algorithmic complexity beyond just being decidable: quite a few are known to lie in NP or co-NP by now, with additional problems being placed in these classes every year. At the same time, only a few knot theory problems are known to be NP-hard, and even fewer of non-trivial knot theory problems are known to have a polynomial algorithm. Some time ago, jointly with Dale Koenig, we proved that unlinking and splitting numbers, as well as detecting an alternating sublink and some other natural problems, are NP-hard. More recently, with Jaeyun Bae, we established that diagrammatic unknotting number is NP-hard. At the same time, with Touseef Haider, we proved that alternating link equivalence has a polynomial algorithm. These results use classical topological tools, often mixing them with complexity theory and graph theory: Wirtinger presentation of a link group, Seifert surfaces and signature, the machinery from the proof of Tait flyping conjecture. We will discuss an interplay of historical results and new developments in this topic, and include some open problems concerning lower bounds on algorithmic complexity in knot theory.

Contributed talks

Eric Samperton, Purdue University

Title: Towards complexity dichotomies for TQFT invariants of 3-manifolds

Abstract: Every (2+1)-dimensional TQFT gives rise to invariants of orientable 3-manifolds that are explicitly and algorithmically definable from triangulations.  However, the naive algorithms to compute these invariants require exponential time in the size of the triangulation.  A interesting problem is to understand which TQFTs admit better algorithms, i.e. with sub-exponential running time.  Resolving this question will be helpful for both practical computational topology, as well as applications to fault tolerant quantum computation.  In this talk, I’ll give an overview of the precise computational problems associated to TQFTs, the motivations from quantum computation, and a conjectural picture for how TQFT’s can be classified according to the computational complexity of their associated 3-manifold invariants.  Along the way, I will compare and contrast with the following analogous “classical” problem: for a given fixed finite group G (which plays the role of a TQFT), how hard is it to count the number of homomorphisms from an input finitely presented group (analogous to a triangulation) to G?

Clément Maria, INRIA Sophia-Antipolis

Title: Hardness of computation of quantum invariants on 3-manifolds with restricted topology

Abstract: Quantum invariants in low dimensional topology offer a wide variety of valuable invariants of knots and 3-manifolds, presented by explicit formulas that are readily computable. Their computational complexity has been actively studied and is tightly connected to topological quantum computing. In this talk, we prove that for any 3-manifold quantum invariant in the Reshetikhin-Turaev model, there is a deterministic polynomial time algorithm that, given as input an arbitrary closed 3-manifold M, outputs a closed 3-manifold M' with same quantum invariant, such that M' is hyperbolic, contains no low genus embedded incompressible surface, and is presented by a strongly irreducible Heegaard diagram. Our construction relies on properties of Heegaard splittings and the Hempel distance. At the level of computational complexity, this proves that the hardness of computing a given quantum invariant of 3-manifolds is preserved even when severely restricting the topology and the combinatorics of the input. This is joint work with Henrique Ennes.

Manuel Radons, Bundesdruckerei Germany

Title: Topological features for author attribution

Abstract: Authorship attribution - in particular, for LLM vs. human write texts - remains critical for curbing misinformation, enforcing intellectual-property rights, and safeguarding trust in high-stakes documents. A well-known technique in this context is to employ the persistent homology dimension of the embedding point cloud of a text as a discerning feature. We explore ways to make use of the full persistence diagram information as a feature, before its compression into a single scalar. We present preliminary results, account for the challenges and discuss next steps.