Please use this identifier to cite or link to this item: http://dx.doi.org/10.14279/depositonce-2640
Main Title: Lattices and Polyhedra from Graphs
Translated Title: Verbaende und Polyeder von Graphen
Author(s): Knauer, Kolja
Advisor(s): Felsner, Stefan
Granting Institution: Technische Universität Berlin, Fakultät II - Mathematik und Naturwissenschaften
Type: Doctoral Thesis
Language: English
Language Code: en
Abstract: Diese Arbeit befasst sich mit vielfaeltigen neuen Anwendungen, Darstellungen und Charakterisierungen von upper locally distributive lattices (ULDs)''. Ein besonderes Augenmerk liegt hierbei auf der Verbindung zur Theorie konvexer Polyeder. Dieses Kapitel 1 ist ueber Verbaende. Erst geben wir eine detailliertere Einfuehrung in die Theorie endlicher Verbaende. In der zweiten Sektion zeigen wir eine neue Korrespondenz endlicher Verbaende mit Antiketten ueberdeckten Posets. Eine spezielle Anwendung davon ist eine staerkere Version eines Charakterisierungssatzes von Nourine ueber ULDs. In der dritten Sektion zeigen wir, dass drei verschieden aussehende Klassen von Objekten aequivalent sind: 1. Azyklische gerichtete Graphen mit U-Kanten-Faerbung'' und eindeutiger Quelle, 2. Jointeilverbaende der Dominanzordnung im Gitter, 3. ULDs mit einer Kettenzerlegung des Meetirreduziblenposets. In Sektion 4 praesentieren wir einen distributiven Verband auf der Menge der Delta-Tensions gerichteteter Graphen. Dieses bisher allgemeinste bekannte Modell fuer distributive Verbaende auf Graphenstrukutren verallgemeinert viele bereits bekannte Ergebnisse. Die wichtigsten drei dieser Faelle (c-Orientierungen, planare Fluesse, planare alpha-Orientierungen) werden in den Untersektionen am Ende vorgestellt. Sektion 5 befasst sich mit Chip-Firing-Games (CFGs) auf gerichteten Graphen, die von Bjoerner und Lovasz eingefuehrt wurden. Als Anwendung der Resultate der vorigen Sektionen ist es leicht zu sehen, dass CFGs zu ULDs fuehren. Wir stellen das Konzept der verallgemeinerten CFGs vor, die maechtig genug sind, um jeden ULD darzustellen. Insbesondere finden wir, dass jeder ULD als endlicher Durchschnitt von CFGs gesehen werden kann. Wir schliessen das Kapitel mit offenen Fragen. In der ersten Sektion des zweiten Kapitels fuehren wir ordnungstheoretische Konzepte ein, die wir in Verbindung mit konvexen Teilmengen der komponentenweisen Ordung des euklidischen Raums untersuche moechten. Als Grundzutaten erklaeren wir U-Polyeder und Meet-Polyeder, um danach ULD-Polyheder und D-Polyeder definieren zu koennen. Letztere bilden resspektive ULDs und distributive Teilverbaende der komponentenweisen Ordung des euklidischen Raums. In Sektion 2 finden wir die erste Charkterisierung von ULD-Polyedern in der Sprache endlichen Durchschnitte beschraenkter Halbraeume. Ausserdem praesentieren wir neue Verbindungen zur Theorie der "feasible polytopes of antimatroids" und liefern Beitraege su einem Problem, was in diesem Zusammenhang von Korte und Lovasz aufgeworfen wurde. Insbesondere zeigen wir auf, dass jedes ULD-Polyeder als Durschschnitt von CFG-Polyedern'' betrachtet werden kann. Als Konsequenz aus unserer Charakterisierung von ULD-Polyedern erhalten wir eine Charakterisierung von D-Polyedern in Sektion 3. Sie basiert auf verallgemeinerten Netzwerkmatrizen. Somit sind diese Polyeder dual zu Polyedern verallgemeinerter Fuesse eines gerichteten Graphen mit verlusstvollen'' und gewinnbringenden'' Kanten. In den folgenden Sektionen finden wir ein kombinstorisches Modell fuer die Punkte eines D-Polyeders als verallgemeinerte Tensions eines gerichteten Graphen. Fir zeigen, dass die Delta-Tensions aus Kapitel 1 als Spezialfall hiervon angesehen werden koennen und verleihen somit einer grossen Vielfalt kombinatorischer Objekte zusaetzlich eine polyedrische Struktur. Im allgemeinen Fall entwickeln wir eine Verbindung von D-Polyedern und bizirkulaeren orientierten Matroiden. Eine neue Amnwendung der Theorie ist, dass bestimmte Klassen planarer verallgemeinerter Fluesse einen distributiven Verband bilden. Wir schliessen das Kapitel mit offenen Fragen. Das dritte Kapitel ist weitestgehend unabhaengig vom Rest der Arbeit. Wir praesentieren einen Algorithmus, der in kubischer Zeit entscheidet, ob ein gegebener Graph der Cocircuitgraph eines orientierten Matroides ist. Das verbessert einen Algorithmus von Babson, Finschi und Fukuda. Ausserdem finden wir eine staerkere Version einer Charakterisierung von Cocircuitgraphen orientierter Matroide von Montellano-Ballesteros und Strausz.
The title Lattices and Polyhedra from Graphs'' of this thesis is general though describes quite well the aim of this thesis. Among the most important objects of this work are distributive lattices and upper locally distributive lattices. While distributive lattices certainly are one of the most studied lattice classes, also upper locally distributive lattices enjoy frequent reappearance in combinatorial order theory under many different names. Upper locally distributive lattices correspond to antimatroids and abstract convex geometries -- objects of major importance in combinatorics. Besides results of a purely lattice or order theoretic kind we present new characterizations of (upper locally) distributive lattices in terms of antichain-covers of posets, arc-colorings of digraphs, point sets in the grid, vector addition languages, chip-firing games, and vertex and (integer) point sets of polyhedra. We exhibit links to a wide range of graph theoretical, combinatorial, and geometrical objects. With respect to the latter we study and characterize polyhedra which seen as subposets of the componentwise ordering of Euclidean space form (upper locally) distributive lattices. Distributive lattice structures have been constructed on many sets of combinatorial such as lozenge tilings, planar bipartite perfect matchings, planar orientations with prescribed outdegree, domino tilings, planar circular flow, orientations with prescribed number of backward arcs on cycles and several more. A common feature of all of them is that the Hasse diagram of the distributive lattice may be constructed applying local transformations to the objects. These local transformations lead to a natural arc-coloring of the diagram. In this work we present the first unifying generalization of all such instances of graph-related distributive lattices. We obtain a distributive lattice structure on the tensions of a digraph. A particular interest of this work lies in embedding lattices into Euclidean space. The motivation is to combine geometrical and order-theoretical methods and perspectives. We investigate polyhedra, which seen as subposets of the componentwise ordering of Euclidean space form upper locally distributive or distributive lattices. In both cases we obtain full characterizations of these classes of polyhedra in terms of their description as intersection of bounded halfspaces. In particular we obtain a polyhedral structure on known discrete distributive lattices on combinatorial objects as those mentioned above as integer points of distributive polytopes. Our characterization of upper locally distributive polyhedra opens connections to the theory of feasible polytopes of antimatroids. In the setting of distributive polyhedra we find graph objects that might be considered as the most general ones, which form a distributive lattice and carry a polyhedral structure. The connection to polytope theory links distributive lattices to generalized flows on digraphs. Thus, there is a link to important objects of combinatorial optimization. Moreover we exhibit new contributions to the theory of bicircular oriented matroids.
URI: urn:nbn:de:kobv:83-opus-28465
http://depositonce.tu-berlin.de/handle/11303/2937
http://dx.doi.org/10.14279/depositonce-2640
Exam Date: 9-Nov-2010
Issue Date: 19-Nov-2010
Date Available: 19-Nov-2010
DDC Class: 510 Mathematik
Subject(s): Graph
Orientierter matroid
Polyeder
Uld
Verband
Graph
Lattice
Oriented matroid
Polyhedra
Uld
Usage rights: Terms of German Copyright Law
Appears in Collections:Technische Universität Berlin » Fakultäten & Zentralinstitute » Fakultät 2 Mathematik und Naturwissenschaften » Institut für Mathematik » Publications

Files in This Item:
File Description SizeFormat 
Dokument_1.pdf2.9 MBAdobe PDFThumbnail
View/Open


Items in DepositOnce are protected by copyright, with all rights reserved, unless otherwise indicated.