Springe direkt zu Inhalt

Helena Bergold:

Signotopes and Convex Drawings

Kurzbeschreibung

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.

Abschluss
PhD
Abgabedatum
19.01.2024
Homepage des Autors