Computing the topological type, or homology, of a given a simplicial complex is straight forward, but not always computationally feasible. The bottleneck is in computing the Smith Normal Form, which is a polynomial time algorithm [Kannan-Bachem], but still too slow on large examples (about cubic).
Discrete Morse theory [Whitehead, Forman] provides a tool set which can be used to find reasonable upper bounds. A randomized search for small discrete Morse vectors was introduced by Benedetti and Lutz, which we implemented as a client for the topological software package polymake.
I gave a workshop on
Random_Discrete_Morse at the Homology: Theoretical and Computational Aspects (HTCA 2015) conference in Genoa, Italy.
While experimenting with
Random_Discrete_Morse, we discovered a whole family of contractible, yet non-collapsible simplicial 2-complexes. We call them the sawblade complexes. Read more about the sawblade complexes here.
- B Benedetti and FH Lutz. Random discrete Morse theory and a new library of triangulations. Exp. Math., 23:66–94, 2014.
- R Forman. A user’s guide to discrete Morse theory. Sémin. Lothar. Comb., 48:B48c, 35 p., electronic only, 2002.
- R Kannan and A Bachem. Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM J. Comput., 8(4):499–507, 1979.
- JHC Whitehead. Simplicial spaces, nuclei and m-groups. Proc. Lond. Math. Soc., II. Ser., 45:243–327, 1939.