Kombinatorik linearer Erweiterungen von endlichen Halbordnungen

Abstract

Diese Arbeit soll einen Überblick über die Kombinatorik linearer Erweiterungen von endlichen Halbordnungen verschaffen. Grundlage dafür ist die zu diesem Thema bereits bestehende umfangreiche Literatur.Das Hauptaugenmerk ist die Bestimmung der Anzahl der linearen Erweiterungen von Halbordnungen. Einige der prominentesten Halbordnungen werden genauer untersucht. Für seriell-parallele, sowie rechteckige Halbordnungen und Wurzelwälder werden explizite Formeln für die Anzahl der linearen Erweiterungen hergeleitet. Für den Booleschen Verband und allgemeinere gereihte Halbordnungen werden Abschätzungen dafür präsentiert. Weiters wird die Ordnungsdimension einer Halbordnung, welche in direktem Zusammenhang mit der Menge der linearen Erweiterungen steht, behandelt. Insbesondere werden zweidimensionale Halbordnungen charakterisiert. Mit dem Ordnungspolytop und dem Kettenpolytop wird ein geometrischer Aspekt von Halbordnungen und ihren linearen Erweiterungen eingebracht. Zwei verschiedene zufällige Halbordnungen werden untersucht. Von besonderer Bedeutung ist dabei die Bestimmung der erwarteten Anzahl der linearen Erweiterungen. Auch die Erzeugung linearer Erweiterungen mithilfe der klassischen Ordnungs-Markov-Kette wird behandelt. Außerdem wird eine große, ungelöste Frage in diesem Gebiet betrachtet, bekannt als "1/3-2/3-Vermutung." Abschließend wird in Kürze auf die wichtigsten Anwendungsbereiche eingegangen.

This master thesis gives an overview of the combinatorics of linear extensions of partially ordered sets (posets). The basis of this thesis is provided by the already existing extensive literature. The main focus is to count the number of linear extensions of a poset. Some of the most important posets are examined in detail. For series-parallel posets as well as rectangular posets and rooted trees, explicit formulas for the number of linear extensions are established. Furthermore, there are presented bounds for the number of linear extenions for the boolean lattice and the more general ranked posets.Also the order dimension of a poset, which is closely related to the set of linear extensions, is considered. Especially the two-dimensional posets are characterised. A geometrical point of view of posets and their linear extensions is shown via the order polytope and the chain polytope. Moreover, two different random posets are examined. In this case the main goal is to determine the expected number of linear extensions for those. Additionally, there is shown how to generate linear extensions with the help of the classical order Markov chain. Another topic of this thesis is a big unsolved question which is known as the "1/3-2/3 conjecture". Eventually there is a brief summaryof the most important applications.