Die Verwendung geometrischer Methoden aus der Ehrhart-Theorie zur Lösung kombinatorischer Probleme

• Antragsteller: Dr. Felix Breuer
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2011 bis 2013
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 198982932

Thema des beantragten Forschungsprojekts ist die Anwendung geometrischer Methoden, insbesondere der Ehrhart-Theorie, auf Probleme der abzählenden Kombinatorik.Ehrhart-Theorie ist die Theorie des Abzählens ganzzahliger Punkte in Polytopen. Ein Polytop ist die Lösungsmenge eines Systems linearer Ungleichungen und dessen Ehrhart-Polynom zählt ganzzahlige Punkte in verschiedenen Streckungen. Anwendungen der Ehrhart-Theorie reichen vom Zählen von Lösungen von Optimierungsproblemen bis zum Auswerten von Box-Splines in der numerischen Analysis.Dieses Projekt befasst sich mit der Anwendung von Ehrhart-Theorie auf kombinatorische Zählfunktionen. Ehrhart-Theorie interpretiert solche Zählfunktionen geometrisch, was eine neue und oft sehr hilfreiche Perspektive auf das jeweilige kombinatorische Problem eröffnet. Das beantragte Projekt erkundet drei neue Forschungsrichtungen:1) Die Anwendung von Ehrhart-Theorie erfordert die Übersetzung der kombinatorischen Beschreibung einer Zählfunktion in die Sprache von Polytopen. In diesem Projekt sollen Algorithmen für diesen Prozess der Geometrisierung entwickelt werden. Ziel ist es die Methoden der Ehrhart-Theorie so zu erweitern, dass sie direkt auf Zählfunktionen angewandt werden können, die in einer kombinatorischen Sprache, z.B. mittels logischer Formeln, definiert sind.2) Ein wichtiges offenes Problem ist die Suche nach kombinatorischen Interpretationen für die Koeffizienten von Ehrhart-Polynomen. In diesem Projekt soll ein neuer Lösungsansatz verfolgt werden, der auf der Analyse unimodularer kubischer Komplexe aufbaut. 3) Um den Anwendungsbereich von Ehrhart-Theorie auf Zählfunktionen jenseits der Quasipolynome zu erweitern, sollen multivariate Ehrhart-Funktionen untersucht werden. Dies führt zum Studium von Dedekindschen Kotangenz-Summen und der Erforschung von Algorithmen für deren Auswertung, was insbesondere eine Alternative zu Barvinoks Algorithmus für das Zählen von Gitterpunkten in Polytopen ergeben kann.

• DFG-Verfahren: Forschungsstipendien
• Internationaler Bezug: USA
• Gastgeber: Professor Dr. Matthias Beck