Gegenstand der Untersuchungen im vorgeschlagenen Projekt sind vielfältige markierte kombinatorische Objekte, denen gewisse strukturelle Einschränkungen zu Grunde liegen. Sowohl die zu erforschenden Objekte, als auch deren Einschränkungen sind dabei unterschiedlicher Natur.
Zum einen sollen in Permutationen, Wörtern (die man auch als Permutationen auf Multimengen bezeichnen kann) und Bäumen sowie Mappings Vorkommnisse von bestimmten Substrukturen untersucht werden. Dies sind die einfachsten und damit fundamentalsten Datenstrukturen. Falls eine bestimmte Substruktur nicht vorkommt, spricht man davon, dass ein gewisses Muster vermieden wird. Die Mustervermeidung hat ihren Ursprung in den Computerwissenschaften, innerhalb der Analyse von Sortieralgorithmen, und soll hier auf andere Objekte und neue Fragestellungen ausgeweitet werden. Von Interesse sind zum Beispiel exakte oder asymptotische Abzählresultate, Beschreibungen von erzeugenden Funktionen, Zusammenhänge zu Statistiken und deren Verteilung, Beziehungen zu anderen kombinatorischen Objekten sowie auch algorithmische Aspekte zur Bestimmung von größten vorgegebenen Mustern. Besondere Aufmerksamkeit wird in diesem Zusammenhang auch dem Entscheidungssproblem „Enthält T (der Text, z.B. eine Permutation) das Muster P (für Pattern)?“ gewidmet. Dieses Problem ist bekanntlich NP-vollständig, lässt sich aber für spezielle Inputs (z.B. für separable Muster) in polynomieller Zeit lösen. Hier soll untersucht werden, welche Parameter des Inputs (T,P) dafür verantwortlich sind, dass dieses Problem aus algorithmischer Sicht so schwer ist. Es soll eine ausführliche Analyse dieses Problems unter dem Blickwinkel der parametrisierten Komplexitätstheorie durchgeführt werden.
Zum anderen sollen markierte kombinatorische Objekte erforscht werden, die gewissen Konstruktionsregeln entsprechen oder aufgrund ihrer Nähe zu einer konkreten Anwendung bestimmten Restriktionen unterliegen. Unsere Untersuchungen werden sich in diesem Zusammenhang zwei Problemen in Folgen und Permutationen widmen. Erstens, dem Studium von Parkfunktionen, die in engem Zusammenhang mit Hashing Algorithmen stehen – hier soll das durchschnittliche Verhalten bei diversen Park-Schemata genauer untersucht sowie die „Anordnung der Parkplätze“ von einer Einbahn auf andere „Straßen“, auch baumartig verzweigte oder wie Mappings angeordnete, erweitert werden. Zweitens dem Hiring Problem, das eine Verallgemeinerung des Sekretärinnenproblems darstellt und sowohl bei Entscheidungsproblemen mit Ungewissheit als auch bei Datenflussalgorithmen eine wichtige Rolle spielt. Hier sollen diverse Strategien, darunter auch probabilitische Varianten, untersucht werden.
Nicht nur die zu untersuchenden kombinatorischen Objekte sondern auch die dabei zum Einsatz kommenden Methoden sind vielfältig. Sie reichen von klassischer Abzählkombinatorik und bijektiven Beweisen über analytische Kombinatorik und Analyse von Algorithmen bis hin zu klassischer und parametrisierter Komplexitätstheorie sowie Wahrscheinlichkeitstheorie.
