Конференция в Сириусе 2021

Доказательство (De Loera, Peterson, Su) обобщения леммы Шпернера основано на оценке максимального количества точек, никакие две из которых не лежат в одном симплексе, построенном по вершинам многогранника. Такое множество точек называется pebble set или множеством галек. Я расскажу, как построить pebble set, как получить верхние и нижние оценки на его размер и как оно используется в лемме Шпернера для многогранников.

В работе изучается новый тип обобщений для теорем типа Хопфа. Требование о наличии у отображения неподвижной точки заменяется на требование о существовании точки, смещающейся в определенном смысле незначительно. Оказывается, в таком случае можно получить нетривиальные результаты о структуре множества тех угловых расстояний в $S^n$, для которых существуют «образы – соседи» при непрерывном отображении $S^n$ в $R^m$ при $m > n$.

Доклад посвящен рассказу о новом аспекте известной связи между косами с n нитями и сфероидами — отображениями из n-мерной сферы $S^n$ в $S^2$.

Известная, но загадочная конструкция позволяет сопоставить брунновым косам сфероиды. Это сопоставление сохраняет алгебраическую структуру (умножение кос соответствует связному суммированию сфероидов). Группы сфероидов известны как гомотопические группы двумерной сферы $S^2$.

В совместной работе мы обнаружили, что это сопоставление индуцирует алгебраические симметрии. А именно, всем автоморфизмам групп крашеных кос соответствуют автоморфизмы гомотопических групп. Например, наши вычисления показали, что «новый автоморфизм» "зеркально обращает" расслоение Хопфа. Работа проводилась на «Летней исследовательской программе студентов».

A geometric graph is a graph drawn in the plane such that its vertices are points in general position and its edges are straight-line segments between these points. There are many interesting results and open problems about geometric graphs that are relevant to well known problems in discrete and computational geometry, such as the halving line problem (Erdos-Lovasz-Simmons-Straus), questions on repeated distances and incidences (Erdos, Szemeredi-Trotter), etc. We survey some basic results in geometric graph theory and highlight some open problems whose solution may be within reach.

Был доказан следующий результат: Рассмотрим семейство F k-множеств размера a*binom(n, k). Тогда количество k-множеств, не пересекающихся с хотя бы (a + eps)*binom(n - k, k) множествами из F, экспоненциально мало по eps. До этого спекатральные методы позволяли доказывать только полиномиальные оценки.

В докладе будет дан обзор результатов, связывающих геометрию и топологию гиперболических многообразий и орбифолдов с арифметикой их фундаментальных групп.

Наследственным классом графов называется любое множество обыкновенных графов, замкнутое относительно удаления вершин и изоморфизма. Любой наследственный класс может быть задан множеством своих запрещенных порожденных подграфов, если это множество конечно, то класс называется конечно определенным.

В докладе рассматривается проблема классификации наследственных классов (особенно, конечно определенных) на случаи полиномиальной разрешимости и труднорешаемости данной задачи на графах. В этом помогают понятия минимального сложного и граничного класса графов. Так, например, задача на графах в конечно определенном классе будет полиномиально разрешимой тогда и только тогда, когда данный класс не включает ни один граничный для данной задачи класс (иначе P=NP).

Доклад будет посвящен обзору известных результатов в области критических (минимальных сложных и граничных) классов графов и их приложений к анализу сложности.

На докладе будет рассмотрен классический метод производящих функций А. Барвинка, позволяющий эффективно решать задачу подсчета количества точек с целочисленными координатами в любом многограннике фиксированной размерности. Далее мы рассмотрим класс Delta-модулярных многогранников и покажем, что задача подсчета количества целых точек в таких многогранниках может быть решена более эффективными алгоритмами. Мы применим данный результат для подсчета количества решения задачи о размене. Более конкретно, мы покажем, что количество способов разменять заданную сумму S набором монет {c1, c2, ..., cN} может быть найдено алгоритмом со сложностью O(n^3 C^4 log(C)), где C есть максимальная стоимость монеты. Наконец, мы применим наши результаты к другим задачам, таким как Vertex Multicover, Stable Multuset, Multyset Multicover и к общей задаче целочисленного программирования.

Задача об H-упаковке состоит в нахождении в заданном графе G максимального числа подграфов, изоморфных некоторому фиксированному графу H и попарно не содержащих общих вершин. Задача об H-разбиении – это версия задачи об H-упаковке, которая спрашивает, можно ли разбить множество вершин данного графа на подграфы, изоморфные графу H. Задача о вершинном покрытии относительно H (H-покрытии) состоит в нахождении наименьшего множества вершин, пересекающегося с каждым подграфом, изоморфным H.

Мы сосредоточимся на задачах об H-упаковке, H-разбиении и H -покрытии для случая, когда H≅P_k – путь на k вершинах, где k – некоторое натуральное число. Доклад будет посвящен обзору приложений данных задач, а также известных результатов в области их решения и вычислительной сложности в различных классах графов.

В докладе рассматривается обобщение классической задачи о вершинной раскраске на случай взвешенного графа. Для построения эффективных алгоритмов решения подзадач задачи о взвешенной вершинной раскраске будут рассмотрены несколько методов редукции графов. Также будет показано, как применить такие методы для задачи о взвешенной вершинной раскраске графов и представлено несколько новых сложностных результатов.

Связный граф с n вершинами и m ребрами называется (n,m)-графом. Индекс Хосойи графа определяется как количество его паросочетаний. В данный момент для любых n>0 и k=-1,0,1,2 полностью описаны (n,n+k)- графы, имеющие максимальный индекс Хосойи среди всех таких графов.

В докладе рассматривается новый подход к поиску графов с максимальными значениями индекса Хосойи, заключающийся в разложении индекса Хосойи по подмножествам отделяющих вершин. Данное разложение порождает некоторые локальные замены графов, увеличивающие индекс Хосойи. Доклад в том числе будет посвящен применению данного метода. В частности, будет предложено новое доказательство для случая k=2.