Discrete Mathematics and Optimization Seminar
Mar. 30th, 2009
Complexity of Embedding Simplicial Complexes in R^d
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.