Combinatorics, Geometry and Topology

Vladimir Kolmogorov

The research of the group focuses on questions in combinatorial and computational geometry and topology. On the one hand, we study basic questions in geometry and topology from a combinatorial and algorithmic viewpoint. On the other hand, we apply methods from topology to problems in combinatorics, discrete geometry, and theoretical computer science.

For the purpose of algorithms and applications, we typically consider the geometric shapes (topological spaces) we study to be represented as simplicial complexes, i.e., in terms of a combinatorial description of how to build the space from basic building blocks (simplices) of various dimensions — points (vertices), line segments (edges), triangles, tetrahedra, etc. For example, a one-dimensional simplicial complex is just a graph, given by a set of vertices and a description which pairs of vertices are joined by an edge (e.g., the layout of a computer chip or a network); higher-dimensional complexes also encode interactions between three and more vertices.

Here are some typical questions we study:

1. Given spaces X and Y, can we compute [X,Y], the set of all continuous functions from X to Y up to homotopy (continuous deformation of one function into another)?

This is a classical topic in algebraic topology. Our focus is on the question to what extent this can be done in a mechanical, automated way, i.e., by a computer program.

2. Fix a simple target space, e.g. Y=Rd. Given a space X, can we decide whether X can be embedded (without self-intersections) into Rd?

3. Assuming that a space X embeds into Rd, what can we say about its structure and its combinatorial complexity (number of simplices)?

Embeddings are also a classical topic in geometric topology. On the other hand the most basic special case of these questions, graph planarity (embedding a one-dimensional space, a graph, into the plane R2) is also a fundamental topic in graph theory and theoretical computer science that has led to a rich combinatorial and algorithmic theory with many applications. Thus, one of our goals is to study higher-dimensional generalizations of graph planarity and of closely related concepts such as graph minors, crossing numbers, expander graphs, etc. 

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

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

CV and Publication List

Assistant
Elisabeth Hacker
Phone: +43 (0)2243 9000-1015
E-mail: elisabeth.hacker@remove-this.ist.ac.at

Team

  • Marek Krcal, Postdoc
  • Isaac Mabillard, PhD Student
  • Martin Tancer, Postdoc

Selected Publications

  • Čadek M, Krčál M, Matoušek J, Sergeraert F, Vokřínek L, Wagner U. 2012. Computing all maps into a sphere. Proc. 23rd Ann. ACM-SIAM Symp. on Discrete Algorithms (SODA), 1–10.
  • Wagner U. 2011. Minors in Random and Expanding Hypergraphs. Proc. 27th Ann. ACM Symp. on Comput. Geom. (SoCG), 351–360.
  • Matoušek M, Tancer M, Wagner U. 2011. Hardness of embedding simplicial complexes in Rd, J. Eur. Math. Soc. 13(2), 2011, 259–295.

Career

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 Zurich
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, Prague
2003–2003 Postdoctoral Fellow, Mathematical Sciences Research Institute, Berkeley
2000–2004 PhD in Mathematics, ETH Zurich
1995–2000 Diplom in Mathematics, Freie Universität Berlin

Selected Distinctions

2012 Research Assistant Professorship Grant of Swiss National Science Foundation (SNSF)
2012 Co-winner of Best Paper Award at Symposium of Discrete Algorithms (SODA)
2004 Richard Rado Prize

To top