Algorithmic and Combinatorial Aspects of Embeddings

Wednesday, April 30, 2014 - 10:15am - 11:05am
Keller 3-180
Ulrich Wagner (IST Austria)
We discuss a number of open questions and results concerning
(from a combinatorialist's point of view) higher-dimensional
analogues of graph planarity and crossing numbers, i.e., embeddings
of finite simplicial complexes (compact polyhedra) into Euclidean space.

While embeddings are a classical topic in geometric topology, here
we focus rather on algorithmic and combinatorial aspects. Two typical
questions are the following:
(1) Is there an algorithm that, given as input a finite k-dimensional simplical
complex, decides whether it embeds in d-dimensional space?
(2) What is the maximum number of k-dimensional simplices of a
simplicial complex that embeds into d-dimensional space?

Time permitting, we will also discuss some maps with more general
restrictions on the set of singularities, e.g., without r-fold intersection points.

The talk will be of a survey-like nature and touch upon joint work with a number of colleagues:
M. Cadek, X. Goaoc, M. Krcal, I. Mabillard, J. Matousek, P. Patak, Z. Safernova, F. Sergeraert,
E. Sedgwick, M. Tancer, and L. Vokrinek
MSC Code: