Семинары: А. Б. Скопенков, NP-трудность вложимости и почти вложимости гиперграфов в R^d

СЕМИНАРЫ


Межкафедральный семинар МФТИ по дискретной математике 9 марта 2017 г. 18:30, г. Долгопрудный, Актовый зал Лабораторного корпуса МФТИ

NP-трудность вложимости и почти вложимости гиперграфов в R^d А. Б. Скопенков
Аннотация: 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. {\it 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. (On joint work with Martin Tancer and on Matoušek-Tancer-Wagner work)