Struktur und Algorithmik kombinatorischer Diskrepanzen

• Antragsteller: Professor Dr. Anand Srivastav
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2002 bis 2007
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 5356186

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.

• DFG-Verfahren: Sachbeihilfen