Random Discrete Morse Theory and a New Library of Triangulations

Abstract

We introduce random discrete Morse theory as a computational scheme to measure the complexity of a triangulation. The idea is to try to quantify the frequency of discrete Morse matchings with few critical cells. Our measure will depend on the topology of the space, but also on how nicely the space is triangulated. The scheme we propose looks for optimal discrete Morse functions with an elementary random heuristic. Despite its naiveté, this approach turns out to be very successful even in the case of huge inputs. In our view, the existing libraries of examples in computational topology are “too easy” for testing algorithms based on discrete Morse theory. We propose a new library containing more complicated (and thus more meaningful) test examples.

2000 AMS Subject Classification:

• 57Q15
• 57Q05
• 57M25
• 57N10
• 57N13
• 52B70
• 52B05
• 52B22
• 55N35

Keywords:

• random discrete Morse theory
• collapsibility
• shellability
• knots in triangulations
• library of triangulations

Acknowledgments

Thanks to Karim Adiprasito, Herbert Edelsbrunner, Alex Engström, Michael Joswig, Roy Meshulam, Konstantin Mischaikow, Vidit Nanda, and John M. Sullivan for helpful discussions and remarks.

Funding

Bruno Benedetti’s research was supported by the Swedish Research Council, grant “Triangulerade Mångfalder, Knutteori i diskrete Morseteori,” and the DFG Collaborative Research Center TRR 109, “Discretization in Geometry and DynamicsÍ.” Frank H. Lutz’s research was supported by the DFG Research Group “Polyhedral Surfaces,” by VILLUM FONDEN through the Experimental Mathematics Network, and by the Danish National Research Foundation (DNRF) through the Centre for Symmetry and Deformation.

Notes

¹Available respectively at chomp.rutgers.edu , redhom.ii.uj.edu.pl , math.rutgers.edu/vidit/perseus.html.

²The library of examples can be found online at http://page.math.tu-berlin.de/ lutz/stellar/library_of_triangulations/.

³BISTELLAR is available at http://page.math.tu-berlin.de/∼lutz/stellar/ BISTELLAR.

⁴An implementation is available at http://page.math.tu-berlin.de/lutz/stellar/FundamentalGroup.