Random collapsibility and 3-sphere recognition,

João Paixão and Jonathan Spreer

Abstract

A triangulation of a 3-manifold can be shown to be homeomorphic to the 3-sphere by describing a discrete Morse function on it with only two critical faces, that is, a sequence of elementary collapses from the triangulation with one tetrahedron removed down to a single vertex. Unfortunately, deciding whether such a sequence exist is believed to be very difficult in general. In this article we present a method, based on uniform spanning trees, to estimate how difficult it is to collapse a given 3-sphere triangulation after removing a tetrahedron. In addition we show that out of all 3-sphere triangulations with eight vertices or less, exactly 22 admit a non-collapsing sequence onto a contractible non-collapsible 2-complex. As a side product we classify all minimal triangulations of the dunce hat, and all contractible non-collapsible 2-complexes with at most 18 triangles. This is complemented by large scale experiments on the collapsing difficulty of 9- and 10-vertex spheres. Finally, we propose an easy-to-compute characterisation of 3-sphere triangulations which experimentally exhibit a low proportion of collapsing sequences, leading to a heuristic to produce 3-sphere triangulations with difficult combinatorial properties.

AMS Subject Classification: Primary 57Q15; secondary 57N12, 57M15, 90C59.