Seitenflächenverbände orientierter Matroide

Hochstättler, Winfried (1992) Seitenflächenverbände orientierter Matroide. PhD thesis.

Abstract

In dieser Arbeit wollen wir uns vor allem mit verbandstheoretischen Zusammenhängen zwischen Matroiden und orientierten Matroiden beschäftigen. Nach den Kapiteln, die Problemstellungen untersuchen, die nicht direkt aus der Anwendung motiviert sind, möchten wir anhand zweier Beispiele aufzeigen, daß es sehr wohl gelingt, mit Hilfe der Abstraktion auf orientierte Matroide anwendungsorientierte Probleme zu lösen. Die Arbeit ist wie folgt gegliedert: Mit dem zweiten Kapitel wollen wir dem Leser das Nachschlagen in diversen Standardwerken ersparen und die verwendeten Notationen einführen. Im darauffolgenden Kapitel wollen wir die für diese Arbeit nötigen Grundlagen der (orientierten) Matroidtheorie entwickeln. Mit einigen Beweisen möchten wir aufzeigen, daß manche Sachverhalte in orientierten Matroiden leichter zu verifizieren sind, wenn man die zugrundeliegende unorientierte Struktur ausnützt. Die Thematik des vierten Kapitels war für uns der Einstiegspunkt in die Arbeit mit orientierten Matroiden. Wir hatten die bis dahin unveröffentlichte Schälbarkeit der orientierten Matroide wiederentdeckt. Die in jener Arbeit benutzten Definitionen sind aber umständlich und unklassisch. Deshalb halten wir uns in dieser Arbeit in der Darstellung weitestgehend an den von A. Björner vorgeschlagenen Zugang. Nach Bereitstellung der nötigsten Grundlagen aus der algebraischen Topologie werden wir im Laufe dieses Kapitels den Beweis des Darstellungssatzes (Folkmann, Lawrence, Edmonds, Mandel) orientierter Matroide skizzieren. Im nächsten Teil der Arbeit entwickeln wir eine verbandstheoretische Axiomatisierung orientierter Matroide. Allerdings handelt es sich hierbei nicht um eine Charakterisierung mittels Verbandsgleichungen. Vielmehr nutzen wir die einfache Charakterisierung geometrischer Verbände (Matroide) mittels Verbandsgleichungen aus und studieren, wann eine Abbildung eines Verbands in einen geometrischen Verband die Nullabbildung eines orientierten Matroids ist. Mit Hilfe dieser Charakterisierung geben wir im sechsten Kapitel zunächst einen neuen Beweis für die Axiomatisierung orientierter Matroide als Sphärensysteme nach Edmonds-Mandel. Hierbei verzichten wir direkt auf das dritte (Ball-) Axiom, dessen Redundanz Mandel zeigen konnte. Im darauffolgenden Paragraphen schwächen wir das zweite Axiom ab, ohne Struktur zu verlieren. Die so gewonnene Charakterisierung läßt sich nun zu einer, der oben erwähnten ähnlichen, weiteren verbandstheoretischen Charakterisierung nutzen. In den abschließenden beiden Kapiteln geben wir zwei Beispiele für Anwendungen der Theorie orientierter Matroide. Zunächst gewinnen wir einen kleinen Satz aus der Polyedertheorie, mit dessen Hilfe wir ein Problem lösen konnten, das im Matroidworkshop der ARIDAM VII vorgestellt wurde. Die zweite Anwendung stammt aus dem Bereich der Computational Geometry. Hier gelang es uns, den Beweis des schwachen Zonensatzes für Pseudo-Hyperebenen Arrangements vom 3-dimensionalen auf beliebige Dimension zu verallgemeinern. Dafür skizzieren wir zunächst, wie man aus einem Pseudo-Hyperebenen Arrangement ein orientiertes Matroid erhält. (Uns ist dafür kein ausgeführter Beweis bekannt.)


Actions:
Download: [img] Postscript - Accepted Version
Download (802kB) | Preview
Editorial actions: View Item View Item (Login required)
Deposit Information:
ZAIK Number: zpr92-117
Depositing User: Winfried Hochstättler
Date Deposited: 02 Apr 2001 00:00
Last Modified: 19 Dec 2011 09:45
URI: http://e-archive.informatik.uni-koeln.de/id/eprint/117