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.
This project was joint work with Frank Lutz and Michael Joswig, with help from Benjamin Lorenz, Bruno Benedetti, and Karim Adiprasito.
- 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.