Летняя Исследовательская Программа Студентов 2025

Направление 1: Экстремальная комбинаторика

Экстремальная комбинаторика - это один из самых бурно развивающихся разделов математики в данный момент. Типичная задача звучит следующим образом: для некоторого класса объектов с ограничениями найти размер наибольшего объекта. Например, экстремальная теория множеств изучает семейства подмножеств $n$-элементного множества с запрещёнными подструктурами (например, семейства, не содержащие пары множеств, пересекающихся ровно по $t$ элементам). Экстремальная комбинаторика тесно связана с целым рядом других разделов математики: теорией кодирования, комбинаторной геометрией, теоретической информатикой, статистической физикой и т.д.

В рамках Программы мы планируем поработать над несколькими задачами экстремальной теории множеств и смежных задачах из дискретной геометрии и теории кодирования:

1. Семейства множеств с фиксированной VC-размерностью и приложения к задачам вычислительной геометрии
2. Семейства множеств с предписанными пересечениями и приложения к теории кодирования
3. Семейства векторов с ограничениями на скалярные произведения и задачи комбинаторной геометрии.

Направление 2: Дискретная и комбинаторная геометрия

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

На лекциях ЛИПС-25 на первой неделе будут рассмотрены несколько задач по метрической алгебраической геометрии, связанной с графом.

А именно, будут представлены три темы:

1. Электрические сети и геометрия положительного Грассманиана
2. Метрика электрического сопротивления и ее свойства
3. Конечные метрические пространства и многогранники

объединенных общей прикладной задачей-восстановление генетического дерева по метрике на границе.

Квадратичные вычеты и кривые над конечными полями. В теории чисел часто возникают объекты, проявляющие квазислучайное поведение, то есть детерминированные сущности, ведущие себя как типичные реализации некоторых случайных величин. Примерами могут служить, например, нетривиальные нули L-функций, графы Рамануджана или множество квадратичных вычетов по простому модулю. Последнее множество и будет главным объектом наших обсуждений. Во время лекций ЛИПС-25 на первой неделе мы будем обсуждать задачи о распределении квадратичных вычетов по модулю p для большого простого p и связанные с этим задачи о точках на кривых над конечными полями и о некоторых регулярных графах специального вида.

Сложность и содержание может варьироваться в зависимости от уровня подготовки и интересов слушателей.

Задача по характеризации графов, полученных дискретным методом Риччи для кодирования данных и сложных систем. Предлагается рассмотреть метрические пространства с различными мерами в зависимости от исходных систем и придумать алгоритмы для их математического обоснования.

Раскраски метрических пространств со всюду плотными цветами. В евклидовой теории Рамсея изучаются задачи о наименьшем числе цветов, при котором в раскраске n-мерного пространства может не найтись одноцветной изометричной копии некоторого заданного множества. В случае классической задачи Хадвигера-Нельсона рассматривается двоеточие (т.е. две точки на единичном расстоянии). За последние годы в этой области было получено множество интересных результатов. Некоторые из них распространяются на вещественные пространства с метрикой, определяемой произвольной нормой, на сферу, плоскость Лобачевского и другие многообразия. Иногда рассматриваются дополнительные ограничения на цветовые классы (подмножества, покрашенные в каждый из цветов): измеримость, условия на границы и т.д.) Предлагается рассмотреть практически не изученную область: задачи рамсеевского типа с условием, что точки каждого из цветов всюду плотны в рассматриваемом пространстве.

Направление 3: Топологическая комбинаторика

Топологическая комбинаторика занимается решением комбинаторных задач с применением топологических инструментов. Во многих случаях эти решения довольно элегантны, и связь между комбинаторикой и топологией часто оказывается сюрпризом. На лекциях ЛИПС-25 на первой неделе будут рассмотрены несколько открытых задач по справедливому дележу и его применению для машинного обучения, применение топологической комбинаторики к теории игр, а также несколько задач цифровой топологии (digital topology). Из рассмотренных задач будут отобраны наиболее интересные задачи для участников программы и наиболее перспективные с точки зрения их решения.

Будут представлены три темы из топологической комбинаторики:

1. Справедливый дележ и его приложение к машинному обучению
2. Топологическая комбинаторика и ее применение к теории игр
3. Дискретная и цифровая топология

Комбинаторные аспекты тейхмюллеровой динамики. Тейхмюллерова динамика - интересный раздел математики, находящийся на стыке эргодической теории, геометрии пространств модулей и символической динамики. Филдсовские медали Артура Авилы и Мариам Мирзахани были присуждены в 2014 году в том числе за достижения в этой области.

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

Направление 4: Дискретная оптимизация и теория сложных сетей

Задача безусловной бинарной квадратичной оптимизации (QUBO - quadratic unconstrained binary program) является сложной задачей дискретной оптимизации, в виде которой можно формализовать большое количество практически значимых проблем, например, задачу о максимальном разрезе или задачу о рюкзаке. С другой стороны, для задачи QUBO разработан ряд аппроксимаций, и для некоторых их них можно дать оценку на ошибку. Например, качество полуопределённой релаксации оценивается через pi/2 теорему Нестерова. Имеются также подходы через решение гладких невыпуклых задач, и квантово вдохновлённая формулировка. Цель проекта -- изучить и сравнить разные подходы и опробовать новый подход, опирающийся на минимизацию разности выпуклых функций.

Скрытая математика идеальных производственных цепочек. Представьте себе большой вычислительный кластер или современный завод-робототехнику. В таких системах часто нужно распланировать множество связанных операций – так, чтобы результат одной операции передавался дальше, а машины работали без простаивания. Например, при распределённом обучении больших языковых моделей вычислительную задачу разбивают между разными серверами: часть данных и результатов обработки передаётся от одного узла к другому. Аналогичная ситуация возникает в гетерогенных вычислительных кластерах (смешанных системах CPU и GPU) – надо решить, какую задачу направить на CPU, а какую – на GPU. Ещё один пример – цифровое (умное) производство: на конвейере продукт проходит несколько операций (точение, сверление, сборка), и нужно организовать этот процесс так, чтобы оборудование не простаивало, а общее время выполнения всех операций было минимальным.

Такую задачу можно точно описать методами математической оптимизации – например, сформулировать как задачу смешанного целочисленного линейного программирования (MILP). Эта модель отражает все ограничения и в теории позволяет найти оптимальное расписание. Однако на практике MILP-модель чрезвычайно быстро становится гигантской, если количество операций и машин растёт. Даже современные оптимизаторы (типа CPLEX или Gurobi) не справляются: найти оптимальное расписание может занять неприемлемо много времени или вообще оказаться невозможным. Поэтому применение точных методов оправдано лишь для небольших учебных примеров, но не для реальных крупных систем.

Прямое решение через MILP здесь чревато экспоненциальным ростом сложности, поэтому на передний план выходят эвристические и приближённые методы. Вот почему ключевой вызов – разработка хороших эвристик. Эвристический алгоритм – это способ «на глаз» построить решение: он не гарантирует нахождение оптимума, но позволяет быстро получить достаточно качественное расписание.

Задача подсчета точек с целыми координатами внутри многогранников является одной из классических #P-трудных задач вычислительной геометрии. Данная задача имеет большое количество приложений: от вычисления нагрузки вложенных циклов и предсказания кеш-промахов в компьютерных программах, до оценивания количества рисков в инвестиционных портфелях. Мы планируем исследовать два фундаментальных теоретических подхода для решения данной задачи: алгоритм А. Барвинка, и более новый алгоритм, основанный на вычислении групп Гомори локальных угловых многогранников. Оба подхода в своей основе используют теорему Бриона и теорему Lawrence, Хованского и Пухликова, но и имеют существенные различия. Возникающая математика весьма красива и разнообразна — используются кусочки из разных областей: алгебра многогранников, теория производящих функций, геометрия чисел, комбинаторика. Мы также планируем исследовать некоторые приложения и обобщения данных подходов, такие как:

1. полиномы Эрхарта
2. Sparse Integer Linear Programming
3. Fully Polynomial Time Approximation Scheme for Polynomial Maximization.

Направление 5: Теоретическая информатика

В рамках направления будут представлены задачи по следующим темам:

1. Справедливый дележ неделимых предметов
2. Параметризованные алгоритмы
3. Fine-grained complexity
4. Сложность задач поиска

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

Одно из самых популярных понятий справедливости — отсутствие зависти (EF), которое требует, чтобы каждый агент предпочитал свой собственный набор предметов любому другому. Однако в случае неделимых предметов подобные распределения могут не существовать для некоторых входов, что приводит к необходимости изучения ослаблений этого свойства. Одно из актуальных и значимых ослаблений EF (предложенное Карагьянисом и соавторами), называется свободным от зависти по отношению к любому элементу (EFx). При нем набор каждого агента должен стоить как минимум столько же, сколько набор любого другого агента, за вычетом любого предмета. Существование EFx распределения в общем случае является открытым вопросом.

Параметризованные алгоритмы (2) — это алгоритмы, разработанные для решения сложных вычислительных задач, где помимо основного размера входа $n$ учитывается дополнительный параметр $k$, характеризующий структуру задачи.

Мы рассмотрим задачи покрытия рёбер графа кликами — Edge Clique Partition (ECP) и Edge Clique Cover (ECC) — в них требуется найти набор полных подграфов размера не более $k$, которые в объединении содержат все рёбра графа. В случае ECP запрещено покрывать ребро дважды, в случае ECC — это не запрещается. Удивительно, что вторая задача оказывается существенно сложнее первой с точки зрения параметризованных алгоритмов. Несмотря на естественную формулировку, про эти задачи известно не так много, даже на специальных классах графов. Мы исследуем эти задачи и известные результаты для них, рассмотрим открытые для них вопросы с разных точек зрения и постараемся пополнить немногочисленный ряд алгоритмических результатов для ECP и ECC.

Сложность задач поиска (4) изучает задачи, в которых нужно найти решение для некоторой системы условий, либо установить, что решения нет. Это расширение известного класса NP: в нём нужно просто установить, есть ли решение, без его поиска. Особый интерес представляют задачи, в которых решение заведомо есть по той или иной причине, но поиск сложен. Например, у любого числа есть простой делитель, а вот поиск простого делителя подразумевает разложение на множители, что предположительно требует долгого перебора. Класс заведомо решаемых задач называется TFNP, но с точки зрения теории сложности он неудобен, потому что (предположительно) не содержит полных задач. В результате изучается множество разных подклассов, задаваемых разными "архетипичными" задачами. Они образуют причудливую сеть вложений, мы будем изучать эту сеть и классифицировать различные задачи в ней.