Алгоритмы распознавания вложимости $n$-мерных гиперграфов в $2n$-мерное пространство

Хорошо известно, что существует быстрый (точнее — линейный) алгоритм, определяющий, вложим ли данный граф в плоскость, т.е., можно ли граф расположить на плоскости так, чтобы его ребра не пересекались и не самопересекались. Мы рассмотрим аналогичную задачу для гиперграфов в пространствах произвольной размерности: как распознать вложимость $n$-мерного гиперграфа в $2n$-мерное пространство? Теория гиперграфов — раздел математики, возникший на стыке комбинаторики, топологии и программирования, бурно развивающийся в последнее время. Мы начнем с элементарного изложения проблемы устойчивости самопересечений пути на плоскости (http://www.turgor.ru/lktg/2008/5/index.php, Секлюцкий 1969, Реповш–А. Скопенков 1998, Минц 1997, М. Скопенков 2003). На этом маломерном примере мы освоим основную идею препятствия ван Кампена к вложимости n-мерных гиперграфов в $2n$-мерное пространство. Основные результаты доклада — теорема о существовании полиномиального алгоритма распознавания вложимости n-мерных гиперграфов в $2n$-мерное пространство при $n>2$; несуществование такого алгоритма для $n=2$ (Ван Кампен 1932, Шапиро 1957, Ву 1957, Matousek–Tancer–Wagner, 2008, http://www.mccme.ru/circles/oim/algor.pdf). Будет дан популярный обзор с основными идеями доказательств, доступными неспециалистам (в первую очередь студентам). Большая часть доклада будет доступна первокурсникам. Все необходимые определения (гиперграф, вложимость, группы гомологий, препятствие Ван Кампена и т.д.) будут даны. Основные идеи будут представлены на ‘олимпиадных’ примерах: размерности 2, на простейших частных случаях, свободных от технических деталей, и со сведением к необходимому минимуму алгебраического языка.