КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ

Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.

 

ОБЩИЕ СВЕДЕНИЯ

---

Номер проекта 24-71-10021

НазваниеЭкстремальная теория множеств и её приложения к задачам дискретной геометрии и дискретной оптимизации

Руководитель Купавский Андрей Борисович, Доктор физико-математических наук

Организация финансирования, регион федеральное государственное автономное образовательное учреждение высшего образования "Московский физико-технический институт (национальный исследовательский университет)" , г Москва

Конкурс №98 - Конкурс 2024 года «Проведение исследований научными группами под руководством молодых ученых» Президентской программы исследовательских проектов, реализуемых ведущими учеными, в том числе молодыми учеными

Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-114 - Дискретная математика и математическая кибернетика

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

Код ГРНТИ27.45.15, 27.45.00, 27.47.00

---

 

ИНФОРМАЦИЯ ИЗ ЗАЯВКИ

---

Аннотация
Этот проект посвящён задачам экстремальной комбинаторики и их приложениям в дискретной геометрии и дискретной оптимизации. Типичная задача в экстремальной комбинаторике звучит следующим образом. Пусть дан некоторый класс объектов (графы, гиперграфы, многогранники, конфигурации векторов, семейства множеств, слов и т.п.) с ограничениями. Насколько большими могут быть характеристики объекта из этого класса? Подобные вопросы возникают в различных областях математики и теоретической информатики, и одним из часто возникающих классов объектов, которым занимается экстремальная теория множеств, являются семейства подмножеств конечного множества. Экстремальная теория множеств – это одна из самых динамично развивающихся областей комбинаторики, в которой работают такие выдающиеся математики, как Алон, Боллобаш, Мубаи, Киваш, Кюн, Остус, Пах, Судаков, Франкл, Фюреди и многие другие, в том числе молодые, учёные. В этой области за последнее время появилось несколько прорывных результатов и методов: прогресс в гипотезе Эрдеша-Радо о подсолнухах и в гипотезе о семействах, замкнутых по объединениям, Франкла. При этом в области остаются и важные нерешённые задачи. Евклидова теория Рамсея за последние несколько лет пережила всплеск, во многом благодаря доказательству нижней оценки 5 на хроматическое число пространства Де Греем. Помимо этого было получено немало интересных результатов, в том числе и с помощью slice rank, сыгравшего важную роль в изучении множеств без арифметических прогрессий. В некотором смысле похожая ситуация и в дискретной оптимизации, где случился прорыв в экспоненциальных алгоритмах для различных задач целочисленного программирования, в частности, в работах Айзенбрандта и Вайсмантела. При этом между этими тремя областями есть тесные связи в части рассматриваемых объектов и методов. Так, важнейшие результаты об экспоненциальности хроматического числа пространства, а также об экспоненциальной рамсеевости различных множеств доказаны с помощью теорем Франкла и Уилсона, а также Франкла и Рёдля из экстремальной теории множеств; в задачах дискретной оптимизации (и, в частности, в вопросах целочисленности некоторых многогранников) важную роль играют k-кратно пересекающиеся семейства; а вопросы про пары семейств с ограничением встречаются в задачах о сложности расширений и двухуровневых многогранников. Этот проект преследует две основных цели. Во-первых, в рамках проекта мы планируем сфокусироваться на нескольких ключевых проблемах экстремальной теории множеств, а также на развитии новых методов в области. В особенности речь идёт о методе разреженных приближений, предложенных руководителем проекта. Во-вторых, в рамках проекта предполагается развить части дискретной геометрии и дискретной оптимизации, смежные для экстремальной теории множеств, а также развить “диалог” между этими областями. В этой заявке мы рассмотрим направления, которые можно кратко охарактеризовать следующим образом: 1) Прогресс в нескольких классических задачах экстремальной теории множеств, а также развитие новых методов в этой области, и в особенности метода разреженных приближений. 2) Решение ряда экстремальных задач для семейств перестановок, разбиений, гиперплоскостей и векторов. 3) Продвижение в нескольких задачах геометрической теории Рамсея, изучение их аналогов в других нормах, поиск экстремальных конфигураций в малых размерностях на целочисленной и других решётках. Получение новых оценок хроматических чисел геометрических графов. 4) Продвижение в нескольких экстремальных задачах дискретной оптимизации: оценки количества граней в многогранниках и триангуляциях вееров, заданных векторами с ограничениями.

---

 

ОТЧЁТНЫЕ МАТЕРИАЛЫ

---