DC FieldValueLanguage
dc.contributor.advisorGittenberger, Bernhard-
dc.contributor.authorGrossauer, Manuel-
dc.date.accessioned2020-12-04T11:07:48Z-
dc.date.issued2020-
dc.date.submitted2020-12-
dc.identifier.citation<div class="csl-bib-body"> <div class="csl-entry">Grossauer, M. (2020). <i>Kombinatorik linearer Erweiterungen von endlichen Halbordnungen</i> [Diploma Thesis, Technische Universität Wien]. reposiTUm. https://doi.org/10.34726/hss.2020.68533</div> </div>-
dc.identifier.urihttps://doi.org/10.34726/hss.2020.68533-
dc.identifier.urihttp://hdl.handle.net/20.500.12708/16411-
dc.descriptionAbweichender Titel nach Übersetzung der Verfasserin/des Verfassers-
dc.description.abstractDiese 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.de
dc.description.abstractThis 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.en
dc.format91 Seiten-
dc.languageDeutsch-
dc.language.isode-
dc.subjectLineare Erweiterungde
dc.subjectHalbordnungde
dc.subjectgleichverteilte Erzeugungde
dc.subjectOrdnungspolytopde
dc.subjectLinear extensionen
dc.subjectpartial orderen
dc.subjectuniform generationen
dc.subjectorder polytopeen
dc.titleKombinatorik linearer Erweiterungen von endlichen Halbordnungende
dc.title.alternativeCombinatorics of linear extensions of finite posetsen
dc.typeThesisen
dc.typeHochschulschriftde
dc.identifier.doi10.34726/hss.2020.68533-
dc.publisher.placeWien-
tuw.thesisinformationTechnische Universität Wien-
tuw.publication.orgunitE104 - Institut für Diskrete Mathematik und Geometrie-
dc.type.qualificationlevelDiploma-
dc.identifier.libraryidAC16098986-
dc.description.numberOfPages91-
dc.thesistypeDiplomarbeitde
dc.thesistypeDiploma Thesisen
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.openairecristypehttp://purl.org/coar/resource_type/c_18cf-
item.openaccessfulltextOpen Access-
item.openairetypeThesis-
item.openairetypeHochschulschrift-
item.fulltextwith Fulltext-
item.languageiso639-1de-
item.grantfulltextopen-
item.cerifentitytypePublications-
item.cerifentitytypePublications-
Appears in Collections:Thesis

Files in this item:


Page view(s)

27
checked on Sep 5, 2021

Download(s)

12
checked on Sep 5, 2021

Google ScholarTM

Check


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