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.
