Anders Björner: On embedding complexes in real space

Abstract

Planarity is a very important and much studied graph
property.  It is the $d=1$, $k=2$ case of a general notion of embedding of
simplicial $d$-complexes in real $k$-space.

Euler observed in 1752 that planarity implies a strong
upper bound on the number of edges of a graph. Namely,
the edges and vertices of a planar graph must satisfy $E \le 3V-6$.
Similar bounds exist in higher dimensions. van Kampen and Flores
exhibited complexes that cannot be embedded in double dimension.

It has been known since long that planarity of graphs can be
decided in linear time. Recent work of Matousek, Tancer and Wagner shows
that the algorithmic aspects of embeddability are more
complex in higher dimensions. For instance, deciding embeddabaility
in codimension one is algorithmically undecidable for $d>3$.

In this talk I will partly survey some results in this area
and partly present some updates to my joint work with A.Goodarzi
concerning an obstruction to codimension one embeddings.