Discrete Mathematics and Optimization Seminar
Mar. 30th, 2009
Complexity of Embedding Simplicial Complexes in R^d
Uli Wagner
ETH Zurich
It is well-known that one can test in linear time whether a given graph is planar. We consider the higher-dimensional generalization of this problem: given a k-dimensional simplicial complex K and a target dimension d, does K embed into R^d? (All the relevant topological notions will be defined and explained during the talk, at least on an intuitive level.)

Surprisingly, rather little seems to be known about the algorithmic aspects of this problem. Besides being a natural question from a computational geometer's viewpoint, computational complexity can also be seen as a concrete "measuring rod" for the mathematical difficulty of the embedding problem in different ranges of the parameters and for the strength of various embeddability criteria.

Known results imply that the problem is polynomial-time solvable for k=d=2 or d=2k \geq 6. We observe that the problem is algorithmically undecidable for k=d-1 and d \geq 5. This follows from a famous result of Novikov on the unsolvability of recognizing the 5-sphere.

Our main result is NP-hardness in the range d \geq 4 and d \geq k \geq (2d-2)/3. These dimensions fall outside the so-called metastable range of a theorem of Haefliger and Weber, which characterizes embeddability in terms of the so-called deleted product obstruction. Our reductions are based on examples, due to Segal, Spiez, Freeman, Krushkal, Teichner, and Skopenkov, showing that outside the metastable range, the deleted product obstruction is insufficient.

Our result indicates that (barring P=NP), no simple (i.e., polynomially computable) criterion for embeddability is to be expected outside the metastable range.

Time permitting, we will also discuss some related (mostly open) extremal problems, and threshold questions for random complexes.

Joint work with Jiri Matousek and Martin Tancer.