
Discrete Mathematics and Optimization Seminar

Mar. 30th, 2009
Complexity of Embedding Simplicial Complexes in R^d
Uli Wagner
ETH Zurich

Abstract:
It is wellknown that one can test in linear time whether a given graph is planar.
We consider the higherdimensional generalization of this problem: given a
kdimensional 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 polynomialtime solvable
for k=d=2 or d=2k \geq 6. We observe that the problem is algorithmically
undecidable for k=d1 and d \geq 5. This follows from a famous result of Novikov
on the unsolvability of recognizing the 5sphere.
Our main result is NPhardness in the range d \geq 4 and d \geq k \geq (2d2)/3.
These dimensions fall outside the socalled metastable range of a theorem of
Haefliger and Weber, which characterizes embeddability in terms of the socalled
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.



