Restricted labelled combinatorial objects

At the center of the proposed project stand a multitude of labeled combinatorial objects that are all constrained by some structural restriction. Both the objects that are going to be analysed and the nature of their underlying restrictions are very different. On the one hand, we shall investigate the occurrence of patterns in simple and thus fundamental data structures. These are lists (permutations and words, or equivalently, permutations on multisets) and trees as well as mappings. In case a certain substructure is not contained, one speaks of a pattern being avoided. In this project we plan to expand the field of pattern avoidance to other objects than permutations. Some of the problems of interest to us will be the following: finding exact or asymptotic enumerative results, describing generating functions, identifying connections with statistics and their distribution, establishing links to other combinatorial objects as well as elaborating algorithms for finding largest given patterns. We will also devote special attention to computational aspects of pattern involvement respectively avoidance. The decision problem "Does T (a given text, for instance a permutation) contain P as a pattern?" is known to be NP-complete. However, in certain special cases, e.g. when the pattern is a separable permutation, this problem can be solved in polynomial time. Our goal is to give a precise description of which parameters of the input (T,P) make this problem computationally hard. In order to answer this question we shall analyse this problem from the viewpoint of parametrized complexity theory. On the other hand, we plan to explore combinatorial objects following certain construction rules or underlying restrictions due to their connection to specific applications and problems. Our analysis shall concentrate on two important combinatorial problems. First, the analysis of parking functions which are closely related to hashing algorithms: We intend to investigate the average case behavior of various types of parking schemes and to consider a more general concept of parking functions by allow other, for instance tree-like, types of "roads". Second, the study of the so-called hiring problem which is a generalization of the well-known secretary problem and plays an important role both within on-line decision making under uncertainty and within the analysis of data stream algorithms: Here we shall analyse different types of hiring strategies including probabilistic variants. Not only the combinatorial objects that shall be analysed but also the methods and tools that will be employed are diverse. The methods reach from classical enumerative combinatorics including bijective proofs as well as analytic combinatorics and analysis of algorithms to classical and parameterized complexity theory and even probabilistic methods.

This project's research lies within discrete mathematics and is concerned with the analysis of a multitude of labelled combinatorial objects whose structure is subject to some fundamental restriction. The research questions we dealt with arise from a mathematical interest for the enumeration as well as the description of combinatorial properties of objects such as permutations, sequences, trees and mappings. In order to study these combinatorial objects, we employed a multitude of methods and established results that highlight different aspects of structural restrictions. In this context we proved exact and asymptotic enumeration formulæ (How many objects X of size n are there that have property Y? How do these numbers behave when n is large?) both by using bijective methods and tools from analytic combinatorics, we analysed combinatorial algorithms from the point of view of classical and parameterized complexity theory (How efficiently can we decide whether object X has property Y?) and obtained probabilistic results (How does property Y behave in a random object X?). In the following, we describe one of the core areas of this project in more detail: parking functions on trees. Imagine the following scenario: Alongside a one-way street there are labelled parking spaces. Sequentially, cars arrive and want to park in this street. Every car has a preferred parking space and tries to park there. If this space is already occupied, it moves on in the allowed direction - reversing is not allowed - and parks in the first empty spot available. If the end of the street is reached without being able to park, the car is unsuccessful and leaves. If all cars find a parking spot using this procedure one says that the given sequence of preferred parking spaces is a parking function. For instance, if there are more cars than spaces or if all cars want to park in the last space, we are not dealing with a parking function. Parking functions are much more than a mathematical game; indeed, this parking procedure describes a fundamental and widely studied hashing algorithm and is thus highly relevant to storing and accessing data in a database. We generalised the concept of parking functions by considering more complicated road networks in which branchings are allowed. Employing methods from analytic combinatorics allowed us to provide explicit formulæ for the number of such generalised parking functions with n parking spaces and at most m cars. Taking a closer look at the asymptotic behaviour of these numbers revealed a fascinating phase transition phenomenon: When m is larger than n/2 the probability that all cars can park successfully suddenly drops to 0. This surprising phenomenon is particularly interesting because qualitatively similar phase transitions occur in very different combinatorial settings.