Algorithmic aspects of embedding simplicial complexes in R^d

Date

Nov 13, 2013

Time

5:00 PM - 6:00 PM

Speaker

Prof. Dr. Jirí Matoušek

Affiliation

Charles University Prague

Series

TUD Dresdner Mathematisches Seminar

Language

en

Main Topic

Mathematik

Other Topics

Mathematik

Host

Prof. Dr. U. Brehm

Description

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 (piecewise linearly) into R^d? The algorithmic complexity of this problem turns out to de-pend strongly on k and d. In some cases (k = d-1 and d>4) the problem is algorithmically undecidable, in others it is polynomial-time solvable, and in some cases we have sults such as decidability or NP-hardness. We will survey the main results, which in some cases involve methods of classical homotopy theory combined with more recent algo-rithmic methods, and in others (embedding in R^3) methods of 3-dimensional topology. Joint work with Martin Cadek, Marek Krcal, Eric Sedgwick, Francis Sergeraert, Martin Tancer, Lukas Vokrinek, and Uli Wagner.

Links

• Dresdner Mathematisches Seminar

Last modified: Nov 7, 2013, 5:13:55 PM