Markierte kombinatorische Objekte mit Restriktionen

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.

Die Forschungsthemen dieses Projekts liegen innerhalb der diskreten Mathematik und betreffen die Analyse von vielfältigen markierten kombinatorischen Objekten, denen gewisse strukturelle Einschränkungen zu Grunde liegen. Die behandelten Forschungsfragen ergeben sich aus einem mathematischen Interesse für die Struktur, Eigenschaften und Anzahl von Objekten wie Permutationen, Wörtern, Baumen und Mappings. Nicht nur die zu untersuchenden kombinatorischen Objekte und deren Einschränkungen, sondern auch die eingesetzten Methoden und erzielten Resultate sind vielfältig. So wurden unter anderem exakte und asymptotische Abzählformeln (Wie viele Objekte X mit Eigenschaft Y der Große n gibt es? Wieverhalten sich diese Anzahlen wenn n groß ist?) mithilfe von bijektiven Beweisen und analytischer Kombinatorik erzielt, kombinatorische Algorithmen mit klassischer und parametrisierter Komplexitätstheorie analysiert (Wie effizient kann festgestellt werden ob Objekt X die Eigenschaft Y besitzt?) und wahrscheinlichkeitstheoretische Resultate bewiesen (Wie verhalt sich Eigenschaft Y in einem zufälligen Objekt X?). Von den unterschiedlichen Forschungsschwerpunkten, denen sich das Projekt gewidmet hat, wird jener zu Parkfunktionen auf Bäumen nun etwas genauer beschrieben. Man stelle sich dazu folgendes Szenario vor: Entlang einer Einbahnstraße gibt es durchnummerierte Parkplatze. Es fahren nacheinander Autos in die Straße ein, wobei jedes Fahrzeug einen bevorzugten Parkplatz hat. Es fährt bis zu diesem Platz vor und falls dieser frei ist, parkt es dort. Ansonsten fahrt es solange weiter, bis es einen freien Platz findet - zurückgeschoben darf nicht werden und falls das Ende der Straße erfolglos erreicht wird, hat man Pech gehabt. Schaffen es alle Autos einen Parkplatz zu finden, sagt man dass diese Auswahl an Lieblingsparkplatzen eine Parkfunktion ist. Wollen beispielsweise alle am letzten Platz parken, so ist dies nicht möglich - diese Auswahl ist keine Parkfunktion. Parkfunktionen stellen nicht nur eine nette Spielerei dar; im Gegenteil, obige Parkprozedur beschreibt einen grundlegenden und viel studierten Hashing Algorithmus und ist somit von fundamentaler Bedeutung für das Speichern und Finden von Daten in Datenbanken.Dieses Projekt hat das Konzept von Parkfunktionen verallgemeinert, indem verzweigte Straßennetze anstatt einfacher Einbahnstraßen zugelassen werden. Mithilfe von Methoden aus der analytischen Kombinatorik ist es gelungen explizite Formeln dafür anzugeben wieviele solche verallgemeinerte Parkfunktionen mit n Parkplatzen und höchstens m Autos es gibt. Eine genauere Untersuchung dieser Zahlen hat ergeben, dass für wachsende Größen n ein bemerkenswertes Phasenübergangsphänomen auftritt: Wenn m großer als n/2 ist, fällt die Wahrscheinlichkeit, dass alle Autos parken können, plötzlich auf (fast) 0. Dieses überraschende Phänomen tritt auf ähnliche Art und Weise auch in anderen kombinatorischen Situationen auf und ist daher besonders interessant.