RUS  ENG ЖУРНАЛЫ   ПЕРСОНАЛИИ   ОРГАНИЗАЦИИ   КОНФЕРЕНЦИИ   СЕМИНАРЫ   ВИДЕОТЕКА   ЛИЧНЫЙ КАБИНЕТ
Видеотека
Архив
Популярное видео

Поиск
RSS
Новые поступления





Для просмотра файлов Вам могут потребоваться






Летняя школа «Современная математика», 2015
21 июля 2015 г. 09:30, г. Дубна, дом отдыха «Ратмино»
 


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

А. Б. Скопенков
Материалы:
Adobe PDF 1.2 Mb

Количество просмотров:
Эта страница:44
Материалы:22

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

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

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

Материалы: skopenkov_algor.pdf (1.2 Mb)

Website: http://www.mccme.ru/dubna/2015/courses/askopenkov.html
Цикл лекций

ОТПРАВИТЬ: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru
 
Обратная связь:
 Пользовательское соглашение  Регистрация  Логотипы © Математический институт им. В. А. Стеклова РАН, 2017