Комбинаторика и комбинаторная геометрия - это разделы дискретной математики, которые лежат в основе многих фундаментальных и прикладных исследований. Постановки задач, возникающих в рамках этих разделов, зачастую доступны школьникам. Но методы решения не менее часто выходят за рамки университетских программ. В рамках воркшопа будут обсуждаться наиболее актуальные тренды в комбинаторике и комбинаторной геометрии. В то же время речь пойдет о том, как использовать эти тренды для привлечения школьников и студентов к занятию чистой и прикладной математикой.
Даты и место проведения: 16 - 20 Декабря, Сочи, Сириус
Расписание
Расписание
Доказательство (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.
Мы обсудим решение старой задачи спектральной теории графов о существовании конечного семейства запрещённых подграфов для графов и графов со знаков, собственные значения которых не меньше некоторого фиксированного числа \(\lambda\).
Наше исследование мотивировано задачей об асимптотике размера множества с двумя фиксированными расстояниями при растущей размерности. Совместная работа с Цзылином Цзяном.
Доклад по совместной работе с А.В. Малютиным, А. Гребенниковым, К. Исаевой и М. Михайловым. Мы изучаем алгоритмическую сложность задач о справедливом делении с акцентом на минимизацию количества запросов к участникам. Оказалось, что в некоторых задачах поиск приближенных решений существенно ускоряется при обращении к определенным вполне естественным геометрическим условиям на множества предпочтений участников. Для нескольких классов задач мы показываем, что геометрические условия дают алгоритмы поиска решения, в которых достаточное количество запросов зависит от желаемого уровня точности приближенного решения логарифмически.
Многогранники в трехмерном пространстве Лобачевского будем называть гиперболическими. Для многогранника с заданным скелетом и предписанными двугранными узлами необходимые и достаточные условия его гиперболической реализации даются теоремой Андреева. Причем, такая реализация является единственной с точностью до изометрии пространства. Мы обсудим некоторые комбинаторные задачи и гипотезы, связанные с построением трехмерных гиперболических многогранников и многообразий, и их объемами.
На круглом столе планируется обсудить:
- имеющийся опыт и видение того как это делать, начиная с самых младших классов;
- как научить преподаванию комбигеометрии студентов, осваивающих технологии работы со школьниками?
Участники:
- Райгородский Андрей Михайлович
- Мамий Дауд Казбекович
- Куликова Евгения Александровна
- Волченков Сергей Геннадьевич
- Воронов Всеволод Александрович
- Гаврилюк Андрей Александрович
- Дольников Владимир Леонидович
- Кожевников Павел Александрович pdf
- Резников Андрей Владимирович
- Сухов Кирилл Андреевич
- Батманов Игорь Артемович pdf
К круглому столу также могут присоединиться остальные участники мероприятия.
На круглом столе планируется обсудить:
- имеющийся опыт и видение того как это делать, начиная с самых младших классов;
- как научить преподаванию комбигеометрии студентов, осваивающих технологии работы со школьниками?
Участники:
- Райгородский Андрей Михайлович
- Мамий Дауд Казбекович
- Куликова Евгения Александровна
- Волченков Сергей Геннадьевич
- Воронов Всеволод Александрович
- Гаврилюк Андрей Александрович
- Дольников Владимир Леонидович
- Кожевников Павел Александрович pdf
- Резников Андрей Владимирович
- Сухов Кирилл Андреевич
- Батманов Игорь Артемович pdf
К круглому столу также могут присоединиться остальные участники мероприятия.
Расписание
Программный комитет конференции:
- Мусин Олег Рустумович
Профессор кафедры дискретной математики МФТИ
- Райгородский Андрей Михайлович
Директор Физтех-школы прикладной математики и информатики, главный научный сотрудник лаборатории комбинаторных и геометрических структур МФТИ
- Мамий Дауд Казбекович
Ректор Адыгейского Государственного Университета
- Полянский Александр Андреевич
Старший научный сотрудник лаборатории комбинаторных и геометрических структур МФТИ
Оргкомитет конференции:
- Райгородский Андрей Михайлович
Директор Физтех-школы прикладной математики и информатики, главный научный сотрудник лаборатории комбинаторных и геометрических структур МФТИ
- Полянский Александр Андреевич
Старший научный сотрудник лаборатории комбинаторных и геометрических структур МФТИ;
- Миронов Виктор Николаевич
Инженер лаборатории комбинаторных и геометрических структур МФТИ;
- Крохин Борис Евгеньевич
Руководитель проектов лаборатории инноватики МФТИ
Участники:
- Волченков Сергей Геннадьевич (ЯГУ)
- Веснин Андрей Юрьевич (ТГУ)
- Дольников Владимир Леонидович (МФТИ)
- Кожевников Павел Александрович (МФТИ)
- Мамий Дауд Казбекович (АГУ)
- Мусин Олег Рустумович (МФТИ)
- Полянский Александр Андреевич (МФТИ)
- Райгородский Андрей Михайлович (МФТИ)
- Барабанщикова Полина Юрьевна (МФТИ)
- Батманов Игорь (МФТИ)
- Блудов Михаил Васильевич (МФТИ)
- Василевский Алексей Сергеевич (МФТИ)
- Воронов Всеволод Александрович (АГУ)
- Грибанов Дмитрий Владимирович (НИУ ВШЭ НН)
- Дергачев Евгений Андреевич (АГУ)
- Душков Екатерина Ивановна (МФТИ)
- Ионин Василий Андреевич (СПбГУ)
- Киселев Сергей Григорьевич (МФТИ)
- Кузьмин Никита Александрович (НИУ ВШЭ НН)
- Малышев Дмитрий Сергеевич (НИУ ВШЭ НН)
- Мокеев Дмитрий Борисович (НИУ ВШЭ НН)
- Неопрятная Анна Михайловна (АГУ)
- Развенская Ольга Олеговна (НИУ ВШЭ НН)
- Резников Андрей Владимирович (АГУ)
- Скоркин Аркадий Юрьевич (АГУ)
- Снопов Павел Михайлович (МФТИ)
- Широков Илья (МФТИ)
Дистанционное участие:
- Богачев Николай Владимирович (МФТИ)
- Гаврилюк Андрей Александрович (НИУ ВШЭ)
- Куликова Евгения (Яндекс)
- Пах Янош (Renyi Institute и МФТИ)
- Сухов Кирилл Андреевич (СПб)
- Талецкий Дмитрий Сергеевич (НИУ ВШЭ НН)
Местные организаторы:
- Daud Mamiy