Title: Kombinatorik linearer Erweiterungen von endlichen Halbordnungen
Other Titles: Combinatorics of linear extensions of finite posets
Language: Deutsch
Authors: Grossauer, Manuel 
Qualification level: Diploma
Advisor: Gittenberger, Bernhard 
Issue Date: 2020
Citation: 
Grossauer, M. (2020). Kombinatorik linearer Erweiterungen von endlichen Halbordnungen [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2020.68533
Number of Pages: 91
Qualification level: Diploma
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.
Keywords: Lineare Erweiterung; Halbordnung; gleichverteilte Erzeugung; Ordnungspolytop
Linear extension; partial order; uniform generation; order polytope
URI: https://doi.org/10.34726/hss.2020.68533
http://hdl.handle.net/20.500.12708/16411
DOI: 10.34726/hss.2020.68533
Library ID: AC16098986
Organisation: E104 - Institut für Diskrete Mathematik und Geometrie 
Publication Type: Thesis
Hochschulschrift
Appears in Collections:Thesis

Files in this item:


Page view(s)

22
checked on Jul 23, 2021

Download(s)

10
checked on Jul 23, 2021

Google ScholarTM

Check


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