Рамсеевская теория зацеплений и алгоритмы распознавания реализуемости гиперграфов. Занятие 3

Известно, что существует быстрый алгоритм, определяющий, вложим ли данный граф в плоскость, т. е. можно ли граф расположить на плоскости так, чтобы его ребра не пересекались и не самопересекались. Мы рассмотрим аналогичную задачу для гиперграфов в пространствах произвольной размерности: как распознать вложимость $N$-мерного гиперграфа в $M$-мерное пространство? Теория гиперграфов (или симплициальных комплексов) – бурно развивающийся раздел математики, возникший на стыке комбинаторики, топологии и программирования.
Основные идеи будут представлены на “олимпиадных” примерах: размерности не выше 3, на простейших частных случаях, свободных от технических деталей. В частности, результаты о гиперграфах будут обсуждаться на элементарном языке систем точек. За счет этого спецкурс доступен для начинающих, хотя содержит красивые сложные результаты. От участников потребуется математическая культура и решение задач. Будут предложены красивые задачи для исследования.
Спецкурс начнется со следующих результатов. Попробуйте перед первым занятием доказать их, а также более простые утверждения 1.1, и 1.2 и 1.11 из приложения. Это поможет Вам решить, изучать ли этот спецкурс.
Линейная теорема Конвея–Гордона–Закса. Для любых 6 точек общего положения в пространстве найдутся два зацепленных треугольника с вершинами в этих точках, т. е. два таких треугольника, что объединение сторон первого пересекает второй (двумерный) треугольник в единственной точке.
Линейная теорема Ван Кампена–Флореса. Из любых 7 точек в четырехмерном пространстве можно выбрать две такие непересекающиеся тройки точек, что (двумерный) треугольник образованный первой тройкой, пересекает (двумерный) треугольник, образованный второй тройкой.
Венцом спецкурса будет теорема об NP-трудности проблемы распознавания реализуемости двумерных гиперграфов в четырехмерном пространстве (Matousek–Tancer–Wagner, 2010).