# 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

(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:

62C10

Keywords: