на главную страницу ЛШСМ-2015 к списку курсов ЛШСМ-2015

Аркадий Борисович Скопенков

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

А. Б. Скопенков планирует провести 4 занятия.

Известно, что существует быстрый алгоритм, определяющий, вложим ли данный граф в плоскость, т. е. можно ли граф расположить на плоскости так, чтобы его ребра не пересекались и не самопересекались. Мы рассмотрим аналогичную задачу для гиперграфов в пространствах произвольной размерности: как распознать вложимость N-мерного гиперграфа в M-мерное пространство? Теория гиперграфов (или симплициальных комплексов) — бурно развивающийся раздел математики, возникший на стыке комбинаторики, топологии и программирования.

Основные идеи будут представлены на “олимпиадных” примерах: размерности не выше 3, на простейших частных случаях, свободных от технических деталей. В частности, результаты о гиперграфах будут обсуждаться на элементарном языке систем точек. За счет этого спецкурс доступен для начинающих, хотя содержит красивые сложные результаты. От участников потребуется математическая культура и решение задач. Будут предложены красивые задачи для исследования.

Спецкурс начнется со следующих результатов. Попробуйте перед первым занятием доказать их, а также более простые утверждения 1.1, и 1.2 и 1.11 из http://www.mccme.ru/circles/oim/algor.pdf. Это поможет Вам решить, изучать ли этот спецкурс.

Линейная теорема Конвея–Гордона–Закса. Для любых 6 точек общего положения в пространстве найдутся два зацепленных треугольника с вершинами в этих точках, т. е. два таких треугольника, что объединение сторон первого пересекает второй (двумерный) треугольник в единственной точке.

Линейная теорема Ван Кампена–Флореса. Из любых 7 точек в четырехмерном пространстве можно выбрать две такие непересекающиеся тройки точек, что (двумерный) треугольник образованный первой тройкой, пересекает (двумерный) треугольник, образованный второй тройкой.

Венцом спецкурса будет теорема об NP-трудности проблемы распознавания реализуемости двумерных гиперграфов в четырехмерном пространстве (Matousek–Tancer–Wagner, 2010).

Программа курса

  1. Реализуемость и зацепленность на плоскости.
  2. Реализуемость и зацепленность в пространстве.
  3. Реализуемость и зацепленность в четырехмерном пространстве.
  4. Обобщение на кусочно-линейные реализации.
  5. Об алгоритмах распознавания реализуемости двумерных гиперграфов.

Литература

А. Скопенков, Алгоритмы распознавания реализуемости гиперграфов, параграфы 1 и 4.