|
|
Семинар отдела геометрии и топологии МИАН «Геометрия, топология и математическая физика»
10 мая 2017 г. 18:30, г. Москва, мехмат МГУ, ауд. 16-22
|
|
|
|
|
|
Hardness of embedding and almost embedding simplicial complexes in $R^d$
А. Б. Скопенков МФТИ
|
Количество просмотров: |
Эта страница: | 159 |
|
Аннотация:
A map $f\colon K\to \mathbb R^d$ of a simplicial complex is an almost embedding if $f(\sigma)\cap f(\tau)=\emptyset$ whenever $\sigma,\tau$ are disjoint simplices of $K$.
Theorem. For each integers $d,k\ge2$ such that $d=\frac{3k}2+1$ the algorithmic problem of recognition embeddability (almost embeddability) of finite $k$-dimensional complexes in $\mathbb R^d$ is NP hard.}
This talk will be accessible to non-specialists. I will describe motivations and ideas of proof of this result, including singular versions of Higher-dimensional Borromean Rings Lemma and Generalized Van Kampen-Flores Theorem.
The talk is based on joint work with Martin Tancer and on Matousek-Tancer-Wagner work
|
|