October 27, 2011
It is important to have effective methods for simplifying 3-manifold triangulations without losing any topological information. In theory this is difficult: we might need to make a triangulation super-exponentially more complex before we can make it smaller than its original size. Here we present experimental work that suggests the reality is far different: for an exhaustive census of 81,800,394 one-vertex triangulations that span 1,901 distinct closed orientable 3-manifolds, we never need to add more than two extra tetrahedra, we never need more than a handful of Pachner moves (or bistellar flips), and the average number of Pachner moves decreases as the number of tetrahedra grows. If they generalise, these extremely surprising results would have significant implications for decision algorithms and the study of triangulations in 3-manifold topology. Key techniques include polynomial-time computable signatures that identify triangulations up to isomorphism, the isomorph-free generation of non-minimal triangulations, theoretical operations to reduce sequences of Pachner moves, and parallel algorithms for studying finite level sets in the infinite Pachner graph.
Similar papers 1
November 18, 2010
It is important to have fast and effective methods for simplifying 3-manifold triangulations without losing any topological information. In theory this is difficult: we might need to make a triangulation super-exponentially more complex before we can make it smaller than its original size. Here we present experimental work suggesting that for 3-sphere triangulations the reality is far different: we never need to add more than two tetrahedra, and we never need more than a hand...
December 4, 2020
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 a...
March 11, 2023
We often rely on censuses of triangulations to guide our intuition in $3$-manifold topology. However, this can lead to misplaced faith in conjectures if the smallest counterexamples are too large to appear in our census. Since the number of triangulations increases super-exponentially with size, there is no way to expand a census beyond relatively small triangulations; the current census only goes up to $10$ tetrahedra. Here, we show that it is feasible to search for large an...
August 15, 2000
In this paper we describe a procedure to simplify any given triangulation of the 3-sphere using Pachner moves. We obtain an explicit exponential-type bound on the number of Pachner moves needed for this process. This leads to a new recognition algorithm for the 3-sphere.
May 30, 2016
Matveev and Piergallini independently showed that, with a small number of known exceptions, any triangulation of a three-manifold can be transformed into any other triangulation of the same three-manifold with the same number of vertices, via a sequence of 2-3 and 3-2 moves. We can interpret this as showing that the Pachner graph of such triangulations is connected. In this paper, we extend this result to show that (again with a small number of known exceptions), the subgraph...
July 30, 2003
The face pairing graph of a 3-manifold triangulation is a 4-valent graph denoting which tetrahedron faces are identified with which others. We present a series of properties that must be satisfied by the face pairing graph of a closed minimal P^2-irreducible triangulation. In addition we present constraints upon the combinatorial structure of such a triangulation that can be deduced from its face pairing graph. These results are then applied to the enumeration of closed minim...
November 7, 2003
We explicitly construct small triangulations for a number of well-known 3-dimensional manifolds and give a brief outline of some aspects of the underlying theory of 3-manifolds and its historical development.
June 19, 2005
In this survey on combinatorial properties of triangulated manifolds we discuss various lower bounds on the number of vertices of simplicial and combinatorial manifolds. Moreover, we give a list of all known examples of vertex-minimal triangulations.
November 7, 2003
A census is presented of all closed non-orientable 3-manifold triangulations formed from at most seven tetrahedra satisfying the additional constraints of minimality and P^2-irreducibility. The eight different 3-manifolds represented by these 41 different triangulations are identified and described in detail, with particular attention paid to the recurring combinatorial structures that are shared amongst the different triangulations. Using these recurring structures, the resu...
December 5, 2014
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 ...