Cover graphs and order dimension

Wiechert, Veit

The goal of this dissertation is to study the various connections between the dimension of posets and graph theoretic properties of their cover graphs. We are particularly interested in properties of cover graphs that impose upper bounds on the dimension. A classical result in this context is due to Moore and Trotter from 1977. They showed that posets whose cover graphs are trees have dimension at most 3. Requiring cover graphs to be planar though is not enough to guarantee an upper bound on the dimension, as is witnessed by the famous construction of Kelly. However, Streib and Trotter proved that such a bound exists once the height of these posets is bounded. Their result forms the starting point of a series of papers and already led to a new fruitful research direction. In this dissertation we continue this line of research and determine the exact type of sparsity needed in cover graphs to guarantee that the dimension of the corresponding posets is bounded from above by a function in their height. This type of sparsity is given by the notion of bounded expansion, which was introduced by Nešetřil and Ossona de Mendez as a model for uniform sparseness in graphs. Our theorem generalizes a number of results including the most recent one for posets of bounded height with cover graphs excluding a fixed graph as a topological minor (Walczak, SODA 2015). We also show that the result is in a sense best possible, as it does not extend to nowhere dense classes; in fact, it already fails for cover graphs with locally bounded tree-width. The second main objective of this dissertation is to establish explicit bounds on the dimension in the cases that cover graphs satisfy concrete sparsity properties, such as being planar, having bounded tree-width, or excluding a fixed graph as a minor. Our main contribution in this context is an upper bound on the dimension of planar posets that is linear in height. This is an improvement upon exponential bounds and is best possible up to a constant factor as witnessed by Kelly's examples. We complement our results by several lower bound constructions certifying that our upper bounds are essentially best possible.
In dieser Dissertation beschäftigen wir uns mit der Dimension von Partialordnungen und den zahlreichen Verbindungen dieses Parameters zu strukturellen Eigenschaften von Covergraphen. Ein klassisches Resultat in diesem Kontext stammt von Moore und Trotter aus dem Jahr 1977. Sie zeigen, dass Partialordnungen, deren Covergraphen Bäume sind, höchstens Dimension drei besitzen. Es ist bekannt, dass eine solche konstante obere Schranke an die Dimension nicht existiert, wenn wir jediglich fordern, dass die Covergraphen planar sind: Kellys Beispiele von planaren Partialordnungen aus dem Jahr 1981 haben beliebig große Dimension. Die Situation ändert sich, wenn wir die Höhe der Partialordnungen beschränken. Streib und Trotter zeigen, dass in diesem Fall die Dimension der Ordnungen nach oben beschränkt ist. Ihr Resultat begründete eine neue Forschingsrichtung in der Dimensionstheorie und steht mittlerweile am Anfang einer ganzen Reihe von Ergebnissen. In dieser Dissertation knüpfen wir an diese Ergebnisse an und bestimmen exakte strukturelle Eigenschaften an Covergraphen, die uns obere Schranken an die Dimension von zugehörigen Partialordnungen beschränkter Höhe liefern. Dabei folgen wir einer Hierarchie struktureller Eigenschaften auf Graphen, die auf Nešetřil und Ossona de Mendez zurückgeht. Wir zeigen, dass in dieser Hierarchie die Graphenklassen mit bounded expansion zuvor genannte Schranken garantieren und dass dies nicht mehr Fall ist, wenn Covergraphen nowhere dense sind. Beispiele von Graphenklassen mit bounded expansion sind gegeben durch planare Graphen, Graphen mit beschränkter Baumweite, und allgemeiner Graphen die einen fixen Graphen als topologischen Minor ausschließen. Sie gehen über diese jedoch hinaus, und somit verallgemeinert unser Theorem ein Reihe von Resultaten der letzten Jahre in diesem Bereich. Ein weiterer Schwerpunkt dieser Arbeit beschäftigt sich mit konkreten Abschätzungen an die Dimension von Partialordungen, deren Covergraphen aus den zuvor genannten Graphenklassen stammen. Unser Hauptresultat in dieser Richtung ist eine obere Schranke an die Dimension von planaren Partialordnungen, die linear in der Höhe der Ordnungen ist. Dieses Resultat ist bis auf einen konstanten Faktor bestmöglich, wie Kellys Beispiele zeigen, und verbessert somit bisherige exponentielle Schranken.