Random Simple-Homotopy Theory

We next discuss in more detail how the pure elementary expansions are selected and why Algorithm RSHT has a tendency to simplify simplicial complexes to yield small or even vertex-minimal triangulations. First, we note that RSHT, apart from temporarily adding $(d+1)$-faces in the pure elementary expansion steps (E), never increases the dimension of the complex.

As outlined in the introduction, for any $d$-facet of a $d$-dimensional complex $K$, chosen uniformly at random, we can check for all neighboring $d$-facets whether the induced subcomplexes on the combined $d+2$ vertices are pure $d$-dimensional. From the collection of all available such pure induced $d$-balls on $d+2$ vertices, we pick one uniformly at random for a pure elementary $d$-expansion step (E). However, in general, such pure induced $d$-balls on $d+2$ vertices need not exist. For example, in the case of neighborly triangulations of surfaces, the induced subcomplexes on the four vertices of two adjacent triangles are the two triangles plus the opposite diagonal edge; such subcomplexes are not contractible. In such a case, the only possible pure elementary expansion is by picking a facet (uniformly at random) as a pure $d$-ball and initiating a subdivision (S). An example of a triangulated $3$-sphere on $16$ vertices that allows no bistellar flips (apart from subdivisions of tetrahedra) is given in [DFM04].

In the case of triangulations of $S^{2}$ with $n>4$ vertices, there always are admissible edge flips, and thus Algorithm RSHT never adds a vertex in a subdivision step (S). A vertex can get removed in the reversal of a subdivision once the current triangulation has a vertex of degree $3$. However, the boundary of the octahedron has all of its vertices of degree $4$; in fact, there are infinitely many triangulations of $S^{2}$ with all vertex degrees at least four. In any such example, the removal of a vertex is not immediately possible. But after a suitably long sequence of random edge flips, eventually vertices of degree $3$ show up, and the three incident triangles to such a vertex have the chance to get chosen for an induced pure $2$-ball to remove the vertex of degree $3$.

Similarly, general complexes $K$ are simplified and reduced in size by collapsing away collapsible parts and by reversing subdivisions to reduce the number of vertices—but without a universal guarantee for success (as contractibility is undecidable).

The Dunce Hat [Zee64] is the most famous example of a contractible, but non-collapsible complex; compare [BL13a]. It is obtained by glueing together the three edges of a single triangle in a non-coherent way. The Dunce Hat can be triangulated as a simplicial complex with eight vertices (see Figure 3(a)); and eight vertices is fewest possible, as every contractible simplicial complex on seven vertices is collapsible [BD05]. No triangulation of the Dunce Hat is collapsible, since there are no free edges to start with.

The Dunce Hat of Figure 3(a) admits two anticollapsing moves, the addition of the tetrahedron 1245 or alternatively the addition of the tetrahedron 1367. In Figure 3(b) we added 1367. All of the triangles in 1367 are free, since this is now the only tetrahedron present. If we collapse away the triangle 367, we recover the initial complex of Figure 3(a). If instead we choose to delete the free triangle 136, we obtain the triangulation displayed in Figure 3(c). This triangulation has a free edge, 16, that allows us to get rid of the triangle 167. After this elementary collapse, the edge 17 becomes free, allowing us to remove the triangle 137. But now the edge 13 is free, and it can easily be seen that the deletion of the triangle 138 paves the way to a full collapse down to a single vertex.

In $10^{4}$ runs, RSHT used on average 2.4145 pure elementary $3$-expansions to reduce the $8$-vertex Dunce Hat to a point; see Section 6.1 and Table 1.

The Abalone [HAM93], sometimes called Bing’s House with one room, is another example of a contractible but non-collapsible complex. We are not aware of any triangulation of this space in the literature, so we present one, Abalone, with 15 vertices:

Figure 4 displays this triangulation, although some diagonals have been omitted for reasons of pictorial clarity. Essentially, the triangulation consists of a membrane (in dark) from which two prismatic tunnels (in light) originate at the two empty triangles $1\,2\,3$ and $4\,5\,6$; and the tunnels are separated by the highlighted triangle 8 12 13. The Abalone is contractible as can be seen by filling in the two tunnels.

RSHT can reduce the Abalone to a point using only three expansions. One way to do so is to free the edge $8\,9$ of Figure 4 by first adding the three tetrahedra $8\,9\,12\,13$, $9\,12\,13\,14$, and $9\,13\,14\,15$, in this order, as anticollapsing moves. The resulting complex is then collapsible. This can either be verified by hand, or via the random_discrete_morse algorithm implemented in polymake [BL14]: The three tetrahedra fill in the prism between the triangle $8\,12\,13$ and the (formerly empty) triangle $9\,14\,15$. By collapsing away this prism, the edge $8\,9$ becomes free so that the (dark) membrane around the empty triangle $4\,5\,6$ can be collapsed away, which frees the tunnel originating at this empty triangle. Its removal then allows to collapse the remaining disk.

We can interpret the anticollapsing moves followed by collapses as operations that move the walls of the tunnel so that eventually the obstruction to collapsibility vanishes.

Bing’s House with two rooms [Bin64] is an early example of a contractible space no triangulation of which is collapsible. For our purposes, we triangulate Bing’s House as a triangular prism with two floors, two tunnels to reach the floors, and all rectangular walls subdivided into two triangles each. Figure 4 displays the following (small) triangulation $BH$ with $f=(19,65,47)$ (with the list of facets also available online as example BH at [BL21]):

RSHT is able to reduce Bing’s house to a point by means of five (successive) expansions (in the upper room, each followed by collapses so that the outer walls of Bing’s house are moved towards the upper tunnel). Here is a possible strategy. By successively adding five tetrahedra in the upper room of our Bing’s House triangulation, we fill in a cubical prism between the horizontal square 7–8–11–10 of the medium floor and the square 14–15–18–17 of the ceiling. The first two tetrahedra 7 8 11 15 and 11 15 17 18 can be added independently, and their addition are proper anticollapsing steps. The third tetrahedron 7 11 15 17 is a pure expansion, and the addition of the two final tetrahedra 7 10 11 17 and 7 14 15 17 are again anticollapsing steps. The newly introduced cubical prism connects the outer vertical square 7–8–15–14 with the vertical square 10–11–18–17 of the upper tunnel. The resulting complex is collapsible; an explicit collapsing sequence proving this claim is detailed below.

We start from the outside, by perforating the back square 7–8–15–14. Then we entirely remove the interior of the cubical prism along with the two triangles 7 8 15 and 7 14 15 of the back square and the two triangles 14 15 17 and 15 17 18 of the top square. The result is an indented Bing’s House triangulation with two new side triangles 7 10 17 and 7 14 17. But now the edge 1 7 18 has been freed, and we can use it to collapse away the subdivided squares of the triangulation one by one. First the square 10–11–18–17 is collapsed away, which frees the edge 10 11. This edge in turn can be used to remove the horizontal square 7–8–11–10, thus freeing the edge 78. Next, we remove the squares 1–2–8–7, 2–3–9–8, 1–3–9–7, the vertical wall 3–4–13–9, then all triangles of the lower floor, then the lower tunnel, to end up with the indented upper room with empty triangle 10 12 13. This remaining complex is a triangulated disc and thus collapsible.

A recent example of a non-collapsible, contractible complex is Bing’s House with three rooms (and thin walls) by Tancer [Tan16]. He introduced the example as a gadget to prove that the problem of recognizing collapsible complexes is NP-complete. The basic layout of the example can be found in [Tan16]. Here, we give an explicit triangulation $BH(3)$; and extend this construction to $k$ rooms, $BH(k)$, $k\geq 3$.

The starting point for the construction of $BH(3)$ is to have a ground floor with three triangular holes as depicted in Figure 5. The floor has the following triangles:

Onto the ground floor, we glue three rooms in a coherent way. Room $R_{1}$ is glued onto the two regions A and B and uses nine additional vertices from $17$ to $25$. Room $R_{2}$, depicted in Figure 5, is glued onto the regions B and C and uses the nine vertices from $26$ to $34$. Finally, room $R_{3}$ is glued onto the regions C and A with further nine vertices ranging from $35$ to $43$. The rooms $R_{2}$ and $R_{3}$ are cyclic copies of the room $R_{1}$, where $9$ and $18$ are added to the vertex-labels $17$ to $25$ of room $R_{1}$, respectively. Concretely, the triangles of room $R_{1}$ are

The three rooms $R_{1}$, $R_{2}$, and $R_{3}$ are then all glued to the upper side of the ground floor. Since the vertices of the upper layer of a room are distinct from the vertices of the upper layers of the other two rooms, there is no conflict for the chosen gluing to the same side. To enter the interior of a room, one has to first pass through the tunnel from above of the room to the left, before the room itself can be entered from below through the lower left empty triangle.

The previous construction can be generalized to create Bing’s Houses $BH(k)$ with $k$ rooms, $k\geq 3$. Instead of just three regions, start with $k$ regions that have a triangular hole each, cyclically arranged around a central vertex $1$ on the ground floor, and attach to it $k$ rooms, $R_{1},\ldots,R_{k}$, in a coherent way, as before. The resulting triangulation has face vector

A C++-implementation  BH_k.cc  by Lofano to generate the examples $BH(k)$ along with explicit triangulations BH_3, BH_4, and BH_5 can be found online at [BL21].

Our next result highlights that in terms of simple-homotopy theory, $BH(k)$ is easy to understand.

How does this compare with the experimental results? In $10^{4}$ runs, RSHT was always able to reduce Bing’s house with three rooms, $BH(3)$, to a point, using on average about $148$ additional tetrahedra. In the “best run”, only $12$ additional tetrahedra were used. For Bing’s house with $k$ rooms, $BH(k)$, $4\leq k\leq 7$, in $10^{4}$ runs, even in the best case, RSHT tends to perform a growing number of expansions; see Table 1. This growing number of used tetrahedra is not surprising, due to the probabilistic model that we used: When selecting from more rooms, the number of options for possible expansions gets larger. So if we keep the number of rounds fixed, the chances to pick the cleverest sequence of pure expansions will get thinner.

Table 1 lists the number of expansions used for the Dunce Hat and Bing’s Houses described in the previous section, as well as for the contractible complex two_optima of [ABL17] and for some knotted balls [Lut04, BL13b]. Furch’s knotted $3$-ball is the only example in this set for which the runtime is not negligible. In fact, due to the large number of expansions required, it took an average of 85 seconds to complete one round of the algorithm for this $3$-ball.

The explanation of Table 2 is as follows. If one starts with a single $d$-simplex, with $8\leq d\leq 15$, and one tries to collapse it down to a point, sometimes one gets stuck in contractible, non-collapsible complexes of intermediate dimension [LN21]. For each initial $d$-simplex we recorded $10$ such examples, and on each one of these 10 examples we let RSHT run for $10^{3}$ rounds. In each of the rounds, RSHT was able to reduce the respective examples to a point: In columns three and four of Table 2, we recorded the minimal and average numbers of expansions used. With the increase of the dimension, the runtime started to become an issue. For the largest examples, with $d=15$, it took on average around 25 seconds to complete one round.

If we remove a facet from a triangulation of the $d$-dimensional sphere $S^{d}$, the resulting simplicial complex is a triangulated $d$-ball, and thus has the simple-homotopy type of a point by Whitehead’s Theorem 2.1. In case the initial $d$-manifold $M^{d}$ is not a sphere, the removal of a simplex from a triangulation yields a simplicial complex that, depending on $M^{d}$, may deform to a submanifold or to a non-manifold substructure in $M^{d}$. Table 3 provides results for some classical examples:

Starting with the vertex-minimal triangulation of $\mathbb{R}P^{3}$ with $11$ vertices, and removing a facet, in $10^{4}$ runs of RSHT it took on average $25.2510$ expansions to reach the $6$-vertex triangulation of $\mathbb{R}P^{2}$. From $\mathbb{R}P^{4}$ to $\mathbb{R}P^{3}$ it took $885.5957$ expansions. From $\mathbb{C}P^{2}$ to $S^{2}$ no expansions were used around half of the times; the average number of expansions needed was $2.3543$. Finally, it took $30.0784$ expansions to reach $S^{4}$ from $\mathbb{H}P^{2}$. For the Poincaré homology 3-sphere [BL00], the RSHT algorithm found a 2-dimensional $\mathbb{Z}$-acyclic 2-complex on 10 vertices (the boundary of the identified dodecahedron) using 2031.732 expansions in less than two minutes per run.

The $3$-dimensional lens spaces $L(p,q)$, introduced by Tietze [Tie08], are well-known topological spaces with torsion in homology. Starting from triangulations of the $3$-manifolds $L(p,1)$ [BS93, Lut03a] for $p\geq 3$, we aimed for small triangulations of $2$-dimensional simplicial complexes that still have $p$-torsion. (The case $p=2$ has been already considered, since $L(2,1)=\mathbb{R}P^{3}$.) The table in the top left of Figure 6 gives the $f$-vectors of these smaller complexes; Figure 6 (a)–(c) shows resulting small triangulations d2_n8_3torsion, d2_n8_4torsion, and d2_n8_5torsion (with facets lists available at [BL21]) with torsion $\mathbb{Z}_{3}$, $\mathbb{Z}_{4}$, and $\mathbb{Z}_{5}$, respectively. The example d2_n8_3torsion has the combinatorial symmetry $(2,3)(4,8)(6,7)$; the example d2_n8_4torsion has symmetry $(1,2)(4,6)(7,8)$. In (b), the obtained complex is the union of an $8$-vertex triangulation of the projective plane and a Möbius band. The complex d2_n8_5torsion origins from a triangulated disk by identifications highlighted in blue and red.

The following natural problem is open for $p\geq 3$:

An earlier construction of a 2-dimensional simplicial complex with 3-torsion as a sum complex on eight vertices is by Linial, Meshulam and Rosenthal [LMR10]. Their example is based on the following collection of subsets of $\mathbb{Z}_{8}$:

This complex has complete $1$-skeleton and face vector $f=(8,28,21)$. Three edges of the complex are free, and after collapsing the respective triangles we reach a $2$-complex with $f=(8,25,18)$, which still has one triangle and one edge more than the example d2_n8_3torsion. By runninng RSHT on the triangulation with $18$ triangles repeatedly, we again reach d2_n8_3torsion—or a second non-isomorphic triangulation with the same $f$-vector that is obtained from d2_n8_3torsion by flipping the edge $1$–$5$.

In the description of the torus $S^{1}\times S^{1}$ as a square with opposite edges identified, the removal of the interior of the identified square yields the wedge product $S^{1}\vee S^{1}$ of two circles $S^{1}$ that are glued together at a point. In general, if we remove a facet from a triangulation of a sphere product, the resulting complex is simple-homotopy equivalent to the wedge product of the constituting spheres. In the case of $S^{2}\times S^{1}$, the wedge product $S^{2}\vee S^{1}$ is of mixed dimension. Since in the implementation of RSHT our focus is on the top-dimensional faces, RSHT is not further touching lower-dimensional parts once these are reached via collapses. Thus, the resulting triangulations of $S^{2}\vee S^{1}$ are of the form $\partial\Delta_{3}\cup K^{1}$, consisting of the vertex-minimal triangulation of $S^{2}$ as the boundary complex $\partial\Delta_{3}$ of a $3$-simplex $\Delta_{3}$ union a $1$-dimensional complex $K^{1}$.

Depending on the intersection of $K^{1}$ with $\partial\Delta_{3}$, $K^{1}$ either is a path (a $1$-dimensional ball) or a loop (a $1$-sphere $S^{1}$). For a unified description in Table 4, we write $K^{1}(4.5382)$ to point out that $K^{1}$ has (in $10^{4}$ runs of RSHT) on average $4.5382$ edges. Table 4 gives results for further sphere products, where for the lower-dimensional parts the average number of facets are listed. The initial triangulations of the sphere products in Table 4 are produced via product triangulations of boundaries of simplices [Lut03b].

In a separate experiment, we started with a triangulation of $S^{1}$ with $10$ vertices and with a triangulation of $S^{2}$ with $100$ vertices as the boundary complex of a random simplicial $3$-polytope, for which $100$ points on the round $2$-dimensional sphere were chosen randomly via the rand_sphere client of the software system polymake [GJ00]). The initial triangulation of $S^{2}\times S^{1}$ has face-vector $f=(1000,6880,11760,5880)$. It took RSHT an average of $1108.23$ expansions, in $10^{2}$ runs, to reduce the triangulation (minus a facet) to a triangulation $\partial\Delta_{3}\cup K^{1}(21.76)$ of the wedge product $S^{2}\vee S^{1}$. We repeated the same experiment, but this time applying $200,000$ preliminary random bistellar edge flips to the $100$-vertex triangulation of $S^{2}$, before taking the sphere product. The results of this experiment are similar to the one before (though with a slightly higher average number of expansions). This suggests that RSHT may be reliable even for larger complexes.

“Finding meaningful low-dimensional structures hidden in their high-dimensional observations” [TDSL00] is a major theme in analyzing higher-dimensional data of various origins. Usually, the data is given as a finite set of points in some Euclidean or metric space and is then often transformed to (higher-dimensional) simplicial complexes via taking Čech complexes or Vietoris–Rips complexes. Here, we did not start with explicit data sets, but instead “hid” a (closed) surface in a higher-dimensional product as another model to test RSHT on.

Starting with the standard $7$-vertex triangulation $T$ of the torus, we first took connected sums of $T$ to create surfaces of higher genus $g_{k}$, $k\geq 2$. Then we took the cross product $g_{k}\times I$ of $g_{k}$ with an interval (subdivided into 10 edges on 11 vertices), and reduced the resulting triangulation of the cross product with RSHT. In every single one out of $10^{2}$ runs, the product $g_{k}\times I$ gets reduced back to a small or even vertex-minimal triangulation of the original surface of genus $g_{k}$, as displayed in Table 5. In a second experiment, we performed $200,000$ random edge flips to “randomize” the surfaces $g_{k}$; then, we took cross products with the $10$-edge interval $I$. Again, in $10^{2}$ runs of RSHT, we always achieved the respective $f$-vectors of Table 5.

In a final experiment, we started with the triangulation of the surface $g_{50}$ from before, but this time we added $100$ vertices in subdivision steps before performing the $200,000$ random edge flips. We then took again the cross product with the interval $I$ to get a randomized triangulation of $g_{50}\times I$ with $f=(2728,24278,42212,20760)$. We then took another cross product of this $3$-manifold with boundary with the $4$-simplex $\Delta_{4}$. The resulting complex is $7$-dimensional with around $34$ million faces and face vector

In less than an hour and by using a few thousand expansions, in each out of $10^{2}$ runs of RSHT, we were able to reduce this complex back to a triangulation of the $2$-dimensional orientable surface of genus $50$ with fewer than $60$ vertices. In some cases we were even able to reach the same $f$-vector with $51$ vertices as in Table 6(c). Due to memory constraints that come from the computation of the Hasse diagram of the starting complex (requiring around 10 GB of RAM for this example), this was the largest complex that we were able to study.

As stated early on, contractibility is, in general, undecidable. However, it takes considerable effort to pose challenges to RSHT. A notoriously hard series of complexes is given by the triangulations of the Akbulut–Kirby $4$-dimensional spheres [TL13]. These PL-triangulated standard $4$-dimensional spheres are built in an intricate way via non-trivial presentations of the trivial group as their fundamental group [AK85]. By Pachner’s theorem, these examples are bistellarly equivalent to the boundary of the $5$-simplex, and by Whitehead’s theorem, the examples minus a facet are simple-homotopy equivalent to a single vertex. However, establishing connecting sequences of bistellar flips failed in [TL13], beyond the first easy examples of the series. Indeed, here RSHT made no progress either, even when we set max_step = 1,000,000 and waited for a total runtime of 60 hours.