Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userAlgorithms in 3-manifold theory
166
0
0.0
(
0
)
Authors
Marc Lackenby
Ask ChatGPT about the research
No Arabic abstract
This survey focuses on the computational complexity of some of the fundamental decision problems in 3-manifold theory. The article discusses the wide variety of tools that are used to tackle these problems, including normal and almost surfaces, hierarchies, homomorphisms to finite groups, and hyperbolic structures.
rate research
Read More
We prove foundational results about the set of homomorphisms from a finitely generated group to the collection of all fundamental groups of compact 3-manifolds and answer questions of Reid-Wang-Zhou and Agol-Liu.
We produce a rational homology 3-sphere that does not smoothly bound either a positive or negative definite 4-manifold. Such a 3-manifold necessarily cannot be rational homology cobordant to a Seifert fibered space or any 3-manifold obtained by Dehn surgery on a knot. The proof requires an analysis of short characteristic covectors in bimodular lattices.
A typical census of 3-manifolds contains all manifolds (under various constraints) that can be triangulated with at most n tetrahedra. Al- though censuses are useful resources for mathematicians, constructing them is difficult: the best algorithms to date have not gone beyond n = 12. The underlying algorithms essentially (i) enumerate all relevant 4-regular multigraphs on n nodes, and then (ii) for each multigraph G they enumerate possible 3-manifold triangulations with G as their dual 1-skeleton, of which there could be exponentially many. In practice, a small number of multigraphs often dominate the running times of census algorithms: for example, in a typical census on 10 tetrahedra, almost half of the running time is spent on just 0.3% of the graphs. Here we present a new algorithm for stage (ii), which is the computational bottleneck in this process. The key idea is to build triangulations by recursively constructing neighbourhoods of edges, in contrast to traditional algorithms which recursively glue together pairs of tetrahedron faces. We implement this algorithm, and find experimentally that whilst the overall performance is mixed, the new algorithm runs significantly faster on those pathological multigraphs for which existing methods are extremely slow. In this way the old and new algorithms complement one another, and together can yield significant performance improvements over either method alone.
We show that the problem of determining the genus of a knot in a fixed compact, orientable three-dimensional manifold lies in NP. This answers a question asked by Agol, Hass, and Thurston in 2002. Previously, this was known for rational homology three-spheres, by the work of the first author.
A key result in computational 3-manifold topology is that any two triangulations of the same 3-manifold are connected by a finite sequence of bistellar flips, also known as Pachner moves. One limitation of this result is that little is known about the structure of this sequences; knowing more about the structure could help both proofs and algorithms. Motivated by this, we show that there must be a sequence that satisfies a rigid property that we call semi-monotonicity. We also study this result empirically: we implement an algorithm to find such semi-monotonic sequences, and compare their characteristics to less structured sequences, in order to better understand the practical and theoretical utility of this result.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
