Diskrete and algorithmische Geometrie und Topologie

Uli Wagner

Der Schwerpunkt unserer Forschungsgruppe liegt auf Fragen der kombinatorischen und algorithmischen Geometrie und Topologie. Einerseits untersuchen wir grundlegende Fragen der Geometrie und Topologie aus kombinatorischer und algorithmischer Sicht. Andererseits setzen wir Methoden der Topologie in der Kombinatorik, diskreten Geometrie und theoretischen Informatik ein.

Um Algorithmen und Anwendungen zu entwickeln, befassen wir uns mit geometrischen Formen (topologischen Räumen), die wir als Simplizialkomplexe verstehen, d.h. im Sinne einer kombinatorischen Beschreibung, wie der Raum aus grundlegenden Bausteinen (Simplizes) unterschiedlicher Dimensionen — Punkte (Ecken), Strecken (Kanten), Dreiecke, Tetraedern, usw - zusammengesetzt ist. Zum Beispiel ist ein eindimensionaler Komplex nur ein Graph, der durch eine Menge von Ecken und durch eine Beschreibung definiert ist, welche Eckpaare durch eine Kante (z.B. das Layout eines Computerchips oder Netzwerks) verbunden sind; mehrdimensionale Komplexe kodieren Interaktionen zwischen drei oder mehr Ecken.

Hier sind einige typische Fragen, die wir untersuchen:

1. Sind die Räume X und Y definiert, können wir [X, Y], die Menge aller stetigen Funktionen von X zu Y bis zur Homotopie (kontinuierliche Deformation einer Funktion in eine andere), berechnen?

Das ist ein klassisches Thema der algebraischen Topologie. Unser Schwerpunkt liegt auf der Frage, in welchem Ausmaß dies auf mechanischem, automatischem Wege, d.h. durch ein Computerprogramm, berechnet werden kann.

2. Bestimmung eines einfachen Zielraums, z.B. Y=Rd. Ist ein Raum X definiert, können wir entscheiden, ob X in Rd (ohne eigene Schnittpunkte) eingebettet werden kann?

3. Ist ein Raum X in Rd eingebettet, was können wir über seine Struktur und kombinatorische Komplexität (Anzahl der Simplizes) sagen?

Einbettungen sind auch ein klassisches Thema der geometrischen Topologie. Der grundlegendste Spezialfall dieser Fragen, die Planarität von Graphen (die Einbettung eines eindimensionalen Raumes, eines Graphen, in die Ebene R2), ist auch ein Kernthema der Graphentheorie und der theoretischen Informatik, das zu einer ergiebigen kombinatorischen und algorithmischen Theorie mit vielen Anwendungen geführt hat. Daher ist eines unserer Ziele, mehrdimensionale Prinzipien der Planarität von Graphen und eng verwandter Konzepte wie z.B. Graph Minor, Kreuzungszahl, Expander Graph, usw. zu untersuchen.

Kontakt
Uli Wagner
Institute of Science and Technology Austria (IST Austria)
Am Campus 1
A – 3400 Klosterneuburg

Tel: +43 2243 9000 5501
E-mail: uli.wagner@remove-this.ist.ac.at

»CV und Publikationsliste

»Mathematics at IST Austria Website

Assistentin
Astrid Bonventre-Darthe (Assistant to Professor)
Phone: +43 (0)2243 9000-1015
E-mail: astrid.bonventre-darthe@remove-this.ist.ac.at

Team

  • Marek Filakovský, Postdoc
  • Peter Franek, Postdoc (supported by FWF)
  • Radoslav Fulek, Postdoc (ISTFellow)
  • Kristóf Huszár, PhD Student
  • Marek Krčál, Postdoc
  • Isaac Mabillard, PhD Student (supported by SNSF)
  • Zuzana Masárová , PhD Student (jointly affiliated with Edelsbrunner Group)
  • Stephan Zhechev, PhD Student

Ausgewählte Publikationen

  • Mabillard, I, Wagner U. Eliminating Tverberg points, I. An analogue of the Whitney trick. Proc. 30th Ann. ACM Symp. on Comput. Geom. (SoCG), 2014, 171–180.
  • Matoušek J, Sedgwick, E, Tancer M, Wagner U. Embeddability in the 3-sphere is decidable. Proc. 30th Ann. ACM Symp. on Comput. Geom. (SoCG), 2014, 78–84.
  • Čadek M, Krčál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. Computing all maps into a sphere. Proc. 23rd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), 2012, 1–10.
  • Wagner U. Minors in Random and Expanding Hypergraphs. Proc. 27th Ann. ACM Symp. on Comput. Geom. (SoCG), 2011, 351–360.
  • Matoušek J, Tancer M, Wagner U. Hardness of embedding simplicial complexes in Rd, J. Eur. Math. Soc. 13(2), 2011, 259–295.

Karriere

2013 Assistant Professor, IST Austria
2012-2013 SNSF Research Assistant Professor, Institut de Mathématiques de Géométrie et Applications, EPFL Lausanne
2008–2012 Senior Research Associate, Institute of Theoretical Computer Science, ETH Zürich
2006–2008 Postdoctoral Researcher, Institute of Theoretical Computer Science, ETH Zürich
2004–2006 Postdoctoral Fellow, Einstein Institute for Mathematics, The Hebrew University of Jerusalem
2004–2004 Postdoctoral Fellow, Department for Applied Mathematics, Univerzita Karlova, Prag
2003–2003 Postdoctoral Fellow, Mathematical Sciences Research Institute, Berkeley
2000–2004 PhD in Mathematik, ETH Zürich
1995–2000 Diplom in Mathematik, Freie Universität Berlin

Ausgewählte Auszeichnungen

2014 Best Paper Award am Symposium on Computational Geometry (SoCG)
2012 Förderungsprofessur des Schweizerische Nationalfonds (SNSF)
2012 Paper Award am Symposium of Discrete Algorithms (SODA)
2004 Richard-Rado-Preis

To top