Signotopes and Convex Drawings

Abstract

In this thesis we investigate sign mappings, which for a fixed rank r map subsets of {1,...,n} of size r to one of the two signs + and -, while avoiding sign patterns on induced substructures. Particular focus will be on signotopes and generalized signotopes which originate from pseudohyperplane arrangements and simple drawings. Using those combinatorial encodings for topological objects, we prove classic results in a more general setting.

We consider Levi's extension lemma for pseudoline arrangements and prove that it generalizes to signotopes of odd rank r. Levi showed in 1926 that every pseudoline arrangement can be extended by an additional pseudoline going through two prescribed points. A generalization to dimension 3 fails as Goodman and Pollack (1981) provided an example of pseudoplane arrangements and three prescribed points which is not extendable even though for hyperplane arrangements an extension through d points in dimension d is trivial. Later Richter-Gebert (1993) showed that even an extension through two prescribed points is not possible in dimension 3. We show that signotopes, a subclass of pseudohyperplane arrangements, admit an extension theorem for all even dimensions, that is if the rank r is odd. Moreover, we provide signotopes which are not extendable for rank 4, 6, 8, 10 and 12.

Next, we focus on theorems from convex geometry such as Carathéodory's, Helly's and Kirchberger's theorem and study them in the more general setting of simple drawings of the complete graph. In particular we determine in which layer of the convexity hierarchy introduced by Arroyo et al. (2022) the statements hold, and in which layer there are counterexamples. The convexity hierarchy describes several layers between point sets in the plane and simple drawings using a generalized notion of convexity. For the proof of Kirchberger's theorem generalized signotopes, which encode the triangle orientations of simple drawings in the plane, played an essential role. Additionally to the mentioned theorems we introduce the notion of holes in the setting of simple drawings, which are classically considered in point sets. We show that convex drawings behave similarly to point sets in the sense that every sufficiently large convex drawing contains a 6-hole while there are arbitrarily large drawings without 7-holes.

Moreover, we show that Rafla's conjecture (1988) is true for convex drawings. The conjecture states that every simple drawing of the complete graph admits a plane Hamiltonian cycle. The best known partial results are plane paths of length $\Omega(log(n)/ log log(n))$ (Suk, Zeng and Aichholzer et al. 2022) and plane matchings of size $\Omega(\sqrt{n})$ (Aichholzer et al. 2022). We investigate several variations and strengthenings of this conjecture. In particular we prove that every convex drawing admits a plane substructure consisting of a plane Hamiltonian cycle and additional n-2 additional edges.

In dieser Arbeit untersuchen wir Vorzeichenabbildungen, die für einen festen Rang r Teilmengen von {1,...,n} der Mächtigkeit r auf eines der beiden Vorzeichen + und -$abbilden, wobei Vorzeichenmuster auf induzierten Teilstrukturen vermieden werden. Insbesondere betrachten wir Signotope und verallgemeinerte Signotope, die aus Pseudohyperebenen Arrangements und einfachen Zeichnungen hervorgehen. Unter Verwendung dieser kombinatorischen Kodierungen für topologische Objekte beweisen wir verallgemeinerte Aussagen klassischer Ergebnisse.

Wir betrachten Levis Erweiterungslemma für Pseudogeraden Arrangements und beweisen, dass es sich auf Signotope ungeraden Ranges r verallgemeinern lässt. Levi zeigte 1926, dass jedes Pseudogeraden Arrangement durch eine zusätzliche Pseudogerade erweitert werden kann, welche zwei vorgeschriebene Punkte enthält. Eine Verallgemeinerung auf die Dimension 3 ist nicht möglich. Goodman und Pollack entdeckten 1981 ein Beispiel eines Pseudoebenen Arrangements und drei vorgeschriebene Punkte, das nicht erweiterbar ist, obwohl es eine Erweiterung durch d Punkte für Hyperebenen Arrangements in Dimension d gibt. Später zeigte Richter-Gebert (1993), dass sogar eine Erweiterung durch zwei vorgeschriebene Punkte in Dimension 3 nicht möglich ist. Wir zeigen, dass für Signotope, die eine Teilklasse von Pseudohyperebenen Arrangements bilden, ein Erweiterungssatz in geraden Dimensionen (ungerader Rang r) gilt. Außerdem geben wir Signotope von Rang 4, 6, 8, 10 und 12 an, welche nicht erweiterbar sind.

Zudem betrachten wir klassische Ergebnisse der konvexen Geometrie wie beispielsweise den Satz von Carathéodory, Helly und Kirchberger und untersuchen diese im Kontext einfacher Zeichnungen des vollständigen Graphen. Insbesondere bestimmen wir, in welcher Ebene der von Arroyo et al. (2022) eingeführten Konvexitätshierarchie die Aussagen gelten und ab welcher Ebene es Gegenbeispiele gibt. Die Konvexitätshierarchie beschreibt mehrere Teilklassen von Zeichnungen zwischen Punktmengen in der Ebene und einfachen Zeichnungen unter Verwendung eines verallgemeinerten Konvexitätsbegriffs. Für den Beweis des Satzes von Kirchberger spielen verallgemeinerte Signotope eine wesentliche Rolle. Diese kodieren die Dreiecksorientierungen von einfachen Zeichnungen. Zusätzlich zu den genannten Sätzen betrachten und definieren wir Löcher im Rahmen einfacher Zeichnungen ein. Löcher werden klassischer Weise in der Forschung von Punktmengen betrachtet. Wir zeigen, dass sich konvexe Zeichnungen ähnlich wie Punktmengen verhalten, da jede hinreichend große konvexe Zeichnung ein 6-Loch enthält, während es beliebig große Zeichnungen ohne 7-Löcher gibt.

Zu guter Letzt zeigen wir, dass die Vermutung von Rafla (1988) für konvexe Zeichnungen wahr ist. Die Vermutung besagt, dass jede einfache Zeichnung des vollständigen Graphen einen planaren Hamiltonkreis enthält. Bis jetzt ist nur die Existenz von planaren Pfaden der Länge $\Omega(log(n) / log log(n))$ (Suk, Zeng und Aichholzer et al. 2022) und planaren Matchings der Größe $\Omega(\sqrt{n})$ (Aichholzer et al. 2022) bekannt. Wir untersuchen Variationen und Verallgemeinerungen dieser Vermutung. Insbesondere beweisen wir, dass jede konvexe Zeichnung eine planare Teilstruktur zulässt, die aus einem planaren Hamiltonkreis und zusätzlichen n-2 Kanten besteht.