Теоретическая информатика и комбинаторика (2015 — 2016)

«Теоретическая информатика и комбинаторика» — это совместный научный семинар ФИВТ МФТИ и ФКН ВШЭ. Он проходит 1-2 раза в семестр. Идея в том, чтобы обеспечить максимум научного взаимодействия между факультетами. Поэтому семинар проходит то на территории ФКН по адресу Кочновский проезд, д. 3. (метро Аэропорт, 15 минут пешком), аудитория 509, время среда 16:40 — 18:00, то на территории МФТИ (аудитория и время появится чуть позже).

Страница семинара на сайте ФКН

Заседания:

9 марта 2016 г. (ФКН)
М. Тихомиров «Геометрические графы и сложность их распознавания»
Классические дистанционные графы — это графы, которые можно  нарисовать на плоскости так, чтобы все ребра были отрезками длины 1,  возможно, пересекающимися. С дистанционными графами связано много  известных задач, таких как проблема Эрдеша о количестве единичных  расстояний среди n точек и проблема о хроматическом числе плоскости.
Возникает естественный вопрос: можно ли придумать алгоритм, эффективно распознающий дистанционные графы (а может быть, и позволяющий рисовать их на плоскости)? Оказывается, что нет, такая задача NP-трудна. Такую же задачу можно рассматривать в пространствах других размерностей, а также для других разновидности геометрических графов, т.е. графов с вершинами в точках пространства и ребрами, которые соответствуют некоторому геометрическому соотношению (например, расстояние = 1).
Рассказ будет про ряд результатов в этой области и некоторые подходы к их доказательству.