Struktur und Algorithmik kombinatorischer Diskrepanzen

点击翻译按钮获取中文摘要

Die kombinatorische Diskrepanz ist ein Maß für die Gleichmäßigkeit von Knotenfärbungen eines endlichen Hypergraphen mit zwei oder mehr Farben im Bezug auf die Hyperkanten. Sie ist eng zum klassischen Begriff der Irregularität oder Abweichung von Punkteverteilungen von der uniformen Verteilung in Rd verwandt, der der geometrischen Diskrepanztheorie zugrundeliegt. Neben dem Mathematik-internen Interesse begründen vielfältige Anwendungen der Diskrepanztheorie die Signifikanz und Aktualität des Gebietes. Das Projekt zielt auf die Gewinnung neuer Erkenntnisse zu strukturellen und algorithmischen Problemen in der kombinatorischen Diskrepanztheorie. Die Aufgaben des Projektes zu den strukturellen Aspekten umfassen eine Theoriebildung der Mehrfarbendiskrepanzen, das Studium der Diskrepanz arithmetischer Hypergraphen sowie die Analyse der Diskrepanzfunktion höherdimensionaler Objekte. Der algorithmische Aspekt zielt auf den Entwurf effizienter Approximationsalgorithmen für die Mehrfarben-Diskrepanzfunktion mit Hilfe moderner Design- und Analysetechniken. Methodische Innovationen werden durch die Verbindung von funktionalanalytischen und kombinatorischen Methoden angestrebt.