Inzidenzgraphen und unnachbarschaftliche Polytope

Die vorliegende Arbeit beschäftigt sich mit zwei Themen der Polytoptheorie: dem graphentheoretischen Zusammenhang von Inzidenzgraphen von Polytopen und verwandter geometrischer Strukturen, sowie mit kombinatorischen Eigenschaften so genannter "unnachbarschaftlicher" Polytope. Bezüglich des ersten Themengebietes wird eine nicht unerhebliche Anzahl neuer Resultate erzielt. So wird der Zusammenhang einer großen Klasse von Inzidenzgraphen von Polytopen bestimmt, was Resultate von Sallee (1967) verbessert. Eine verwandte Vermutung von Athanasiadis (2008) über Inzidenzgraphen von regulären Cohen-Macaulay Zellkomplexen wird bewiesen und sogar noch verallgemeinert. Des Weiteren werden Verlinkungen in Polytopgraphen betrachtet. Diese spielen in der reinen Graphentheorie eine wichtige Rolle in der Theorie der Minoren. Hier werden Resultate von Larman & Mani (1970) sowie Gallivan (1985) verbessert. Insbesondere wird erstmals die Verlinkung von Polytopen mit "wenigen Ecken" exakt bestimmt, und es werden Eindeutigkeitsaussagen über kombinatorische Typen extremaler Beispiele gezeigt. Unnachbarschaftliche Polytope wurden in Arbeiten von Mani (1974), McMullen (1979), und Marcus (1981, 1984) studiert. Die kombinatorische Struktur dieser Polytope ist weitgehend unerforscht. Nicht einmal die grundlegende Frage über die minimale Eckenanzahl solcher Polytope ist vollständig geklärt. Diese Frage bleibt auch in der vorliegenden Arbeit ungelöst, aber es werden wichtige Fortschritte gemacht. Sowohl untere als auch obere Schranken an die minimale Eckenanzahl unnachbarschaftlicher Polytope werden bewiesen. Die oberen Schranken werden durch Konstruktion von Beispielen, die Polytope von Mani (1974) verallgemeinern, erreicht. Diese Beispiele widerlegen eine Vermutung von Marcus (1981) über die Eckenanzahl unnachbarschaftlicher Polytope. Für die unteren Schranken wird ein Satz von Perles (ungefähr 1970, unveröffentlicht), für den ein Beweis durch Kalai (1994) vorliegt, auf verschiedene Arten und in verschiedener Allgemeinheit bewiesen. Die aus der Arbeit von Kalai abgeleiteten Schranken werden durch die hier angewandten Methoden verbessert. Ein Korollar der bewiesenen Verallgemeinerungen ist die Lösung eines Problems von Bienia & Las Vergnas (siehe Björner et al. 1993) über die Größe minimal positiv k-aufspannender Mengen in orientierten Matroiden. Dieses Problem ist über Dualität mit unnachbarschaftlichen Polytopen verwandt. Im Zusammenhang mit unnachbarschaftlichen Polytopen wird des Weiteren ein offenes Problem von Mani (1974) über die Existenz nicht-simplizialer illuminierter Polytope auf minimaler Eckenanzahl vollständig gelöst, indem für jede Dimension entweder ein solches Polytop konstruiert oder die Nichtexistenz bewiesen wird. Die Arbeit enthält zusätzlich einige kleinere Verbesserungen bekannter Resultate. Offene Probleme, Fragen, und Vermutungen, die thematisch mit der Arbeit verwandt sind, werden aufgestellt.This thesis deals with two topics from polytope theory: the graph-theoretical connectivity of incidence graphs of polytopes and related geometric structures and the combinatorial structure of so-called unneighborly polytopes. A number of results about incidence graphs are proven. We determine the connectivity of a large class of incidence graphs of polytopes, improving results by Sallee (1967). A related conjecture about incidence graphs of regular Cohen-Macaulay cell complexes that was posed by Athanasiadis (2008) is proven and generalized. We also consider linkages in polytope graphs. Linkages play a very important role in graph minor theory. We improve results by Larman & Mani (1970) and Gallivan (1970). In particular, we determine the linkedness of polytopes with "few vertices" and prove a statement about uniqueness of combinatorial types that are extremal with respect to linkedness. Unneighborly polytopes were considered by Mani (1974), McMullen (1979), and Marcus (1981, 1984). The combinatorial structure of these polytopes is not well-studied. Not even the very basic question about the minimum number of vertices that an unneighborly polytope can have has been answered so far. This question remains unsolved, however, we make considerable progress. We prove upper bounds on the minimum number of vertices of unneighborly polytopes by constructing examples based on polytopes that were discovered by Mani (1974). These examples refute a conjecture by Marcus (1981) about the number of vertices of unneighborly polytopes. Lower bounds are derived by relating the problem to a theorem of Perles (1970, unpublished), for which a proof by Kalai was published (1994). Perles' theorem is proved in various generalities and by different means. In particular, the bounds that one may derive from Kalai's proof are improved. One corollay of the generalized versions of Perles' theorem is a solution to a problem by Bienia & Las Vergnas (see Björner et al. 1993) about the size of minimal positive k-spanning sets in oriented matroids. This problem is related to unneighborly polytopes by duality. In connection with unneighborly polytopes, we solve a problem by Mani (1974) on the existence of nonsimplicial illuminated polytopes. For each dimension, we either prove the nonexistence or construct such a polytope. Furthermore, the thesis contains some small improvements to known results. Open problems, questions, and conjectures that are related to the topics considered are posed