[Zurück]

M. Bruner:
"Patterns in labelled combinatorical objects";
Betreuer/in(nen), Begutachter/in(nen): A. Panholzer, V. Vatter; Institut für Diskrete Mathematik und Geometrie, 2015; Rigorosum: 22.06.2015.

Diese Dissertation beschäftigt sich mit unterschiedlichen Arten von Mustern und strukturellen Einschränkungen in markierten kombinatorischen Objekten. Ein kombinatorisches Objekt A ist in einem anderen größeren Objekt B als Muster enthalten, falls man A erhalten kann, indem Teile von B entfernt werden. Dabei muss auch die Ordnungsstruktur der Marken (engl. "labels") erhalten bleiben. Ein erster Teil dieser Arbeit befasst sich mit Mustern in Permutationen. Besondere Aufmerksamkeit wird in diesem Zusammenhang dem Entscheidungssproblem "Enthält die Permutation T das Muster P?" gewidmet. Dieses Problem ist bekanntlich NP-vollständig. Wir stellen einen fpt-Algorithmus für dieses Problem vor, der besonders effizient ist, wenn die Permutation T nur wenige "alternating runs" aufweist. Außerdem analysieren wir die Komplexität dieses Problems für verschiedene Typen von Permutationsmustern. Für eine besondere Permutationsklasse, die durch vier vermiedene Muster definiert ist und im dritten Teil dieser Arbeit auftaucht, konnten wir das Abzählproblem lösen. Weiters wird die Log-Konkavität einer kombinatorischen Zahlenfolge, die mit Mustervermeidung zusammenhängt, untersucht. Ein zweiter Teil dieser Dissertation beschäftigt sich mit Cayley Bäumen, das sind gewurzelte ungeordnete Bäume, und mit Mappings, das sind Abbildungen einer endlichen Menge auf sich selbst. Zunächst präsentieren wir einen neuen bijektiven Zusammenhang zwischen Cayley Bäumen und Mappings, der uns im Folgenden erlauben wird, bijektive Resultate zu beweisen. Wir verallgemeinern die für Permutationen definierten Muster "Aufstiege" und "aufsteigende Runs" und untersuchen deren Verteilung für Cayley Bäume und Mappings. Ein weiteres Thema sind Parkfunktionen, die wir auf Cayley Bäume und Mappings verallgemeinern. Das asymptotische Verhalten der Abzäformeln weist dabei ein interessantes Phasenübergangsverhalten auf. Ein dritter Teil behandelt sogenannte "Single-peaked elections", die in der sozialen Wahltheorie eine wichtige Rolle spielen. Wir führen den allgemeinen Begriff von Konfigurationen in Präferenzprofilen ein und stellen eine Verbindung zu Permutationsmustern her. Für die spezielle Single-peaked-Konfiguration beantworten wir außerdem die Frage, wie wahrscheinlich es ist, dass diese in zufälligen Präferenzprofilen auftaucht.

This thesis is concerned with various types of patterns and structural restrictions in labelled combinatorial objects. We say that a combinatorial object A is contained in another combinatorial object B as a pattern if A can be obtained by deleting parts of B. Moreover, the order structure of the labels must be preserved. A first part of this thesis addresses patterns in permutations. A question that is of particular interest is the decision problem `"Does the permutation T contain the pattern P"? In general, this problem is NP-complete. We present an fpt-algorithm that solves this problem efficiently if T has few alternating runs. We also analyse the computational complexity of this problem for several different types of permutation patterns. For a special permutation class arising in the context of the third part of this thesis, we solve the enumeration problem. Finally, the log-concavity of a combinatorial sequence related to permutation patterns is investigated. A second part of this work is concerned with Cayley trees, i.e., rooted unordered trees and mappings, i.e., functions from a finite set to itself. First, we present a new bijective proof of Cayley's formula which will subsequently allow us to establish bijective correspondences. Next, we generalize the label patterns "ascents" and "ascending runs" from permutations to Cayley trees and mappings and investigate their distribution. Another topic treated in this part is the generalization of the concept of parking functions to Cayley trees and mappings. The asymptotic analysis of the numbers of these objects leads to an interesting phase transition behaviour. A third part deals with so-called single-peaked elections that play an important role in social choice theory. We introduce the concept of configurations in elections and establish a correspondence with permutation patterns. For the special case of single-peaked profiles we answer the question how likely these are to occur when preferences are chosen at random.

Muster, markierte kombinatorische Objekte, Permutationen, Bäume, Bijektionen, analytische Kombinatorik, Algorithmen