Simplification Strategies and Extremal
Examples of Simplicial Complexes
vorgelegt von
M. Sc.
Davide Lofano
von der Fakult¨at II - Mathematik und Naturwissenschaften
der Technischen Universit¨at Berlin
zur Erlangung des akademischen Grades
Doktor der Naturwissenschaften
Dr.rer.nat.
genehmigte Dissertation
Promotionsausschuss:
Vorsitzender: Prof. Dr. Wilhelm Stannat
Gutachter: Priv.-Doz. Dr. Frank H. Lutz
Gutachter: Prof. Dr. Michael Joswig
Gutachter: Professor Pawe l D lotko
Tag der wissenschaftlichen Aussprache: 7. April 2022
Berlin 2022
ii
Acknowledgements
Moving to Berlin has not been easy. Moving to a different country, with a different
language and different customs means that it takes times to get used to it and to
start enjoying it. If it was not enough, after a year and a half, when I thought
that I was well settled, Covid and the first of many lockdowns started. Needless to
say life has changed a lot for me like for everyone else and I probably would be a
very different person if the pandemic never hit. However the experience has been
amazing and even with a rough start I fell in love with the city and I don’t plan to
move out anytime soon. For this I have to really say thanks to all my friends that
have made my years here, even with all the chaos happening all around, some of
the best years of my life.
I am indebted to my supervisor Frank who has always been helpful, encouraging
me all the time and always ready to answer questions. It has been a pleasure to
work together and hopefully we will be able to continue still in the future.
Thanks to my parents that have always been supportive and never questioned
my decision to move to Berlin and pursue a Ph.D.
Thanks to Eli who has definitely made the second lockdown a very pleasant ex-
perience instead of a depressing one and who has always been at my side especially
in the last stressfull months.
iii
iv
Abstract
Since the beginning of Topology, one of the most used approaches to study a ge-
ometric object has been to triangulate it. Many invariants to distinguish between
different objects have been introduced over the years, the two most important
surely being homology and the fundamental group. However, the direct computa-
tion of the fundamental group is infeasible and even homology computations could
become computationally very expensive for triangulations with a large number of
faces without proper preprocessing. This is why methods to reduce the number of
faces of a complex, without changing its homology and homotopy type, are par-
ticularly of interest. In this thesis, we will focus on these simplification strategies
and on explicit extremal examples.
The first problem tackled is that of sphere recognition. It is known that 3-
sphere recognition lies in NP and in co-NP, and that d-sphere recognition is un-
decidable for d≥5. However, the sphere recognition problem does not go away
simply because it is algorithmically intractable. To the contrary, it appears nat-
urally in the context of manifold recognition so there is a clear need to find good
heuristics to process the examples. Here, we describe an heuristic procedure and
its implementation in polymake that is able to recognize quite easily sphericity of
even fairly large simplicial complexes. At the same time we show experimentally
where the horizons for our heuristic lies, in particular for discrete Morse compu-
tations, which has implications for homology computations.
Discrete Morse theory generalizes the concept of collapsibility, but even for a
simple object like a single simplex one could get stuck during a random collapsing
process before reaching a vertex. We show that for a simplex on nvertices, n≥8,
there is a collapsing sequence that gets stuck on a d-dimensional simplicial complex
on nvertices, for all d /∈ {1, n −3, n −2, n −1}. In contrast, for n≤7 and d
arbitrary or narbitrary and d∈ {1, n −3, n −2, n −1}it is not possible to find a
collapsing sequence for the simplex on nvertices that gets stuck at dimension d.
Equivalently, and in the language of high-dimensional generalizations of trees, we
construct hypertrees that are anticollapsible, but not collapsible.
As for a second heuristic for space recognition, we worked on an algorithmic im-
plementation of simple-homotopy theory, introduced by Whitehead in 1939, where
v
Loading more pages...