Applications of Topology, Combinatorics and Algorithms to Discrete Geometry

In Chapter 1, we show upper bounds to the Grünbaum–Hadwiger–Ramos problem. We give new proofs for almost all known upper bounds and improve the following cases: Let d,n,k be natural number with d >= 2^n(1 + 2^(k-1)). For any 2^(n+1) masses on R^d there are k affine hyperplanes that induce a partition of R^d into 2^k pieces of equal size w.r.t. all masses. In Chapter 2, we use similar methods for a similar problem. k hyperplanes split R^d into up to 2^k non-empty chambers. Similar to a chess board we color the chambers with black and white. Given 2^a(2h + 1) + l masses in R^(2^a + l). We show that there exist 2h + 1 hyperplanes that that split into a black and a white part of equal size w.r.t. to all masses. In Chapter 3, we discuss a new memory-efficient depth-first algorithm and its implementation that iterates over all elements of a finite locally branched lattice. This algorithm can be applied to face lattices of polyhedra and to various generalizations such as finite polyhedral complexes and subdivisions of manifolds, extended tight spans and closed sets of matroids. Its practical implementation is very fast compared to state-of-the-art implementations of previously considered algorithms. Based on recent work of Bruns, García-Sánchez, O’Neill and Wilburne, we apply this algorithm to prove Wilf ’s conjecture for all numerical semigroups of multiplicity 19 by iterating through the faces of the Kunz cone and identifying the possible bad faces and then checking that these do not yield counterexamples to Wilf’s conjecture. In Chapter 4, we provide an algorithm that verifies the optimal colored Tverberg problem for 10 points in the plane: Every 10 points in the plane in color classes of size at most 3 can be partitioned in 4 rainbow pieces such that their convex hulls intersect in a common point. This is achieved by translating the problem to k-partite graphs and using a new algorithm to verify that those graphs do not have a k-clique.In Kapitel 1 zeigen wir obere Schranken des Grünbaum–Hadwiger–Ramos-Problems. Wir geben einen neuen Beweis für fast alle vorhandenen Schranken und zeigen außerdem eine Verbesserung für folgende Fälle: Seien d, n, k natürliche Zahlen mit d ≥ 2 n (1 + 2 k−1 ) und seien 2 n+1 Maße in R d beliebig gegeben. Es gibt k affine Hyperebenen, die R d in 2 k Teile teilen, so dass alle Teile bzgl. aller Maße die gleiche Größe haben. Im Kapitel 2 benutzen wir ähnliche Methoden für ein ähnliches Problem. Der Raum R d wird durch k affine Hyperebenen in bis zu 2 k nicht-leere Kammern geteilt. Wie bei einem Schachbrett gibt es genau zwei Arten die (nicht-leeren) Kammern mit 2 Farben zu färben, so dass Kammern mit gemeinsamer Wand (der Dimension d − 1) verschiedene Farben haben. Auf diese Art teilen k-Hyperebenen den Raum in 2 Teile: einen schwarzen und einen a weißen. Gegeben 2 a (2h + 1) + Maße in R^(2^a + l) . Wir zeigen, dass es stets 2h + 1 Hyperebenen gibt, so dass die Aufteilung in schwarz und weiß eine Halbierung bzgl. aller Maße ist. In Kapitel 3 entwickeln wir einen schnellen und speichereffizienten Algorithmus zum Iterieren über die Seiten von Polytopen und ähnlichen Objekten. Diesen Algorithmus können wir verwenden um eine zahlentheoretische Vermutung bis zu einem Schwellwert zu überprüfen: Eine numerische Halbgruppe ist eine Teilmenge der nicht-negativen ganzen Zahlen, die 0 enthält, die bzgl. Addition abgeschlossen ist und die alle bis auf endlich viele positiven ganzen Zahlen enhält. Für einige ihrer Invarianten wird eine Ungleichung vermutet (Wilf-Vermutung). Wir weisen diese Vermutung nach, sofern das kleinste nicht-Null Element 19 ist. Dafür iterieren wir über die Seiten eines großen Polyeders. Im letzten Abschnitt, in Kapitel 4 weisen wir nach, dass es für 10 gefärbte Punkte in der Ebene – mit maximal 3 Punkten je Farbe – stets eine Tverberg Partition gibt, so dass kein Teil zwei Ecken derselben Farbe enthält. Das ist der erste unbekannte Fall der optimal colored Tverberg Conjecture. Dafür reduzieren wir das Problem auf die Suche nach k-Cliquen in k-partiten Graphen (Verallgemeinerung von bipartit) und entwickeln einen neuen Algorithmus, um zeigen zu können, dass unsere Graphen keine solchen Cliquen haben