Loading…
Simplification strategies and extremal examples of simplicial complexes
Lofano, Davide
Since the beginning of Topology, one of the most used approaches to study a geometric 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 computation 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 particularly 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 undecidable for d > 4. However, the sphere recognition problem does not go away simply because it is algorithmically intractable. To the contrary, it appears naturally 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 computations, 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 n vertices, n > 7, there is a collapsing sequence that gets stuck on a d-dimensional simplicial complex on n vertices, for all d not in {1, n - 3, n - 2, n - 1}. 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 implementation of simple-homotopy theory, introduced by Whitehead in 1939, where not only collapsing moves but also anticollapsing ones are allowed. This provides an alternative to discrete Morse theory for getting rid of local obstructions. We implement a specific simple-homotopy theory heuristic using the mathematical software polymake. This implementation has the double advantage that we remain in the realm of simplicial complexes throughout the reduction; and at the same time, theoretically, we keep the possibility to reduce any contractible complex to a single point. The heuristic algorithm can be used, in particular, to study simply-connected complexes, or, more generally, complexes whose fundamental group has no Whitehead torsion. We shall see that in several contractible examples the heuristic works very well. The heuristic is also of interest when applied to manifolds or complexes of arbitrary topology. Among the many test examples, we describe an explicit 15-vertex triangulation of the Abalone, and more generally, (14k+1)-vertex triangulations of Bing's houses with k rooms.
One of the classes of examples on which we run the heuristic are the 3-dimensional lens spaces, which are known to have torsion in their first homology. Using this examples (minus a facet), we managed to find 2-dimensional simplicial complexes with torsion and few vertices. Studying them we constructed sequences of complexes with huge torsion on few vertices. In particular, using Hadamard matrices we were able to give a quadratic time construction of a series of 2-dimensional simplicial complexes on 5n-1 vertices and torsion of size 2^{n \log(n)}.
Our explicit series of 2-dimensional simplicial complexes improves a previous construction by Speyer, narrowing the gap to the highest possible asymptotic torsion growth proved by Kalai via a probabilistic argument.
Seit den Anfängen der Topologie besteht einer der am häufigsten verwendeten Ansätze zur Untersuchung eines geometrischen Objekts darin, es zu triangulieren. Im Laufe der Jahre wurden viele Invarianten zur Unterscheidung zwischen verschiedenen Objekten eingeführt, die beiden wichtigsten dabei sind sicherlich die Homologie und die Fundamentalgruppe. Die direkte Berechnung der Fundamentalgruppe ist jedoch algorithmisch nicht durchführbar, und selbst Homologieberechnungen können bei Triangulationen mit einer großen Anzahl von Seiten ohne geeignete Vorverarbeitung sehr rechenintensiv werden. Aus diesem Grund sind Methoden zur Reduzierung der Anzahl der Seiten eines Komplexes, ohne dessen Homologie und Homotopietyp zu verändern, von besonderem Interesse. In dieser Arbeit werden wir uns auf diese Vereinfachungsstrategien und auf explizite Extremalbeispiele konzentrieren.
Das erste Problem, das wir angehen, ist das der Sphärenerkennung. Es ist bekannt, dass die 3-Sphärenerkennung in NP und in co-NP liegt, und dass die d-Sphärenerkennung für d > 4 unentscheidbar ist. Das Problem der Sphärenerkennung verschwindet jedoch nicht einfach, nur weil es algorithmisch unlösbar ist. Im Gegenteil, es taucht ganz natürlich im Zusammenhang mit der Erkennung von Mannigfaltigkeiten auf, so dass ein klarer Bedarf besteht, gute Heuristiken zur Verarbeitung der Beispiele zu finden. Hier beschreiben wir ein heuristisches Verfahren und seine Implementierung in polymake, das in der Lage ist, die Sphärizität selbst großer Komplexe recht einfach zu erkennen. Gleichzeitig zeigen wir experimentell, wo die Grenzen für unsere Heuristik liegen, insbesondere für diskrete Morseberechnungen, was Auswirkungen auf Homologieberechnungen hat.
Die diskrete Morse-Theorie verallgemeinert das Konzept der Kollabierbarkeit, aber selbst für ein einfaches Objekt, wie z.B. für ein einzelnes Simplex, kann man während eines zufälligen Kollaps-Prozesses steckenbleiben, bevor man eine finale Ecke erreicht. Wir zeigen, dass es für ein Simplex auf n Ecken, n > 7, eine kollabierende Sequenz gibt, die auf einem d-dimensionalen simpliziellen Komplex auf n Ecken stecken bleibt, für alle d nicht in {1, n - 3, n - 2, n - 1}. Äquivalent dazu, und in der Sprache der hochdimensionalen Verallgemeinerungen von Bäumen ausgedrückt, konstruieren wir Hypertrees, die antikollabierbar, aber nicht kollabierbar sind.
Was eine zweite Heuristik zur topologische Typerkennung betrifft, so haben wir an einer algorithmischen Implementierung der 1939 von Whitehead eingeführten Simple-Homotopy-Theory gearbeitet, bei der nicht nur kollabierende, sondern auch antikollabierende Züge erlaubt sind. Dies bietet eine Alternative zur diskreten Morse-Theorie, um lokale Hindernisse zu beseitigen. Konkret haben wir eine spezialle Fassung der einfachen Homotopietheorie unter Verwendung der mathematischen Software polymake implementiert. Diese Implementierung hat den doppelten Vorteil, dass wir während der gesamten Reduktion im Bereich der simplizialen Komplexe bleiben; und gleichzeitig behalten wir theoretisch die Möglichkeit, jeden zusammenziehbaren Komplex auf einen einzigen Punkt zu reduzieren. Der heuristische Algorithmus kann insbesondere dazu verwendet werden, einfach zusammenhängende Komplexe zu untersuchen, oder, allgemeiner, Komplexe, deren Fundamentalgruppe keine Whitehead-Torsion haben. Wir werden sehen, dass die Heuristik in einen Vielzahl von kontrahierbaren Beispielen sehr gut funktioniert. Die Heuristik ist auch von Interesse, wenn sie auf Mannigfaltigkeiten oder Komplexe beliebiger Topologie angewendet wird. Unter den vielen Testbeispielen beschreiben wir eine explizite 15-Vertex-Triangulation der Abalone und, allgemeiner, (14k+1)-Vertex-Triangulationen von Bing-Häusern mit k Zimmern.
Eine der Klassen von Beispielen, auf die wir die Heuristik anwenden, sind die 3-dimensionalen Linsenräume, von denen bekannt ist, dass sie Torsion in ihrer ersten Homologie haben. Unter Verwendung von Triangulierungen von Linsenräumen (minus eine Facette) ist es uns gellungen, 2-dimensionale simplizialen Komplexe mit Torsion und wenigen Ecken zu finden. Denen Untersuchung erlaubte es uns, Serien von Komplexen mit großer Torsion und einer kleinen Eckenanzahl zu konstruieren. Insbesondere konnten wir unter Verwendung von Hadamard-Matrizen eine Serie 2-dimensionale simplizialen Komplexe mit 5n-1 Ecken und einer Torsion der Größe 2^{n \log(n)} in quadratischer Zeit konstruieren.
Unsere explizite Serie 2-dimensionaler simplizialer Komplexe verbessert eine frühere Konstruktion von Speyer, indem sie die Lücke zum höchstmöglichen asymptotischen Torsionswachstum verkleinert, das von Kalai über ein probabilistisches Argument nachgewiesen wurde.
