Struktur und Algorithmik kombinatorischer Diskrepanzen

• Applicant: Professor Dr. Anand Srivastav
• Subject Area: Mathematics
• Term: from 2002 to 2007
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 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 Programme: Research Grants