The Pachner graph and the simplification of 3-sphere triangulations

Abstract

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 handful of local modifications. If true in general, these extremely surprising results would have significant implications for decision algorithms and the study of triangulations in 3-manifold topology. The algorithms behind these experiments are interesting in their own right. Key techniques include the isomorph-free generation of all 3-manifold triangulations of a given size, polynomial-time computable signatures that identify triangulations uniquely up to isomorphism, and parallel algorithms for studying finite level sets in the infinite Pachner graph.

17 pages, 4 figures, 4 tables; v2: incorporate connectedness into Theorem 4, other minor revisions; to appear in SoCG 2011

References in corpus (6)

• Finite covers of random 3-manifolds
• Enumeration of non-orientable 3-manifolds using face pairing graphs and union-find
• The complexity of the normal surface solution space
• Face pairing graphs and 3-manifold enumeration
• Optimizing the double description method for normal surface enumeration
• Simplifying triangulations of S^3

Cited by in corpus (13)

• A census of tetrahedral hyperbolic manifolds
• Computing the crosscap number of a knot using integer programming and normal surfaces
• Simple crystallizations of 4-manifolds
• 4-colored graphs and knot/link complements
• Computing trisections of 4-manifolds
• Detecting genus in vertex links for the fast enumeration of 3-manifold triangulations
• Finding Hexahedrizations for Small Quadrangulations of the Sphere
• A census of hyperbolic platonic manifolds and augmented knotted trivalent graphs
• Hyperbolic 3-manifolds of low cusp volume
• Computationally proving triangulated 4-manifolds to be diffeomorphic
• Constructing Infinitely Many Geometric Triangulations Of The Figure Eight Knot Complement
• Learning 3-Manifold Triangulations
• Mutations and faces of the Thurston norm ball dynamically represented by multiple distinct flows