Лаборатория комбинаторных и геометрических структур

В течение 2019 – 2021 гг. было получено множество результатов в области экстремальной, вероятностной и аддитивной комбинаторики, а также дискретной и вычислительной геометрии. В частности, был получен положительный ответ на гипотезу Линиала о пороге для существования тора в 3-равномерном гиперграфе, был решён вопрос о полиномиальном росте VC-размерности для класса к-вершинных многогранников, получены различные экстремальные результаты касательно семейств множеств и векторов. Доказано обобщение неравенства Янсона, показана возможность его использования к некоторым вопросам распределения степеней в случайном графе. Получено доказательство гипотезы Аарони и Ховарда при новых значениях параметров. Доказаны новые утверждения о приближениях хунтами для сдвинутых семейств с явными зависимостями от вводных параметров, данный подход применен для доказательства почти линейной оценки в гипотезе Эрдеша о паросочетаниях для нескольких семейств. Получена рекуррентная формула для мощности максимального семейства n-мерных векторов, все координаты которых равны 0, 1 или -1 при фиксированном количестве координат каждого типа и ограничения на скалярное произведение. В 2022 году коллектив лаборатории продолжил работу над несколькими научными проблемами. Полученные результаты можно резюмировать следующим образом: a) исследованы вопросы теории Рамсея, покрытия и раскраски решёток и для max-нормы б) исследованы свойства типа Тверберга для конечных наборов точек в) исследованы теоретико-графские характеристики графов единичных расстояний в больших размерностях г) исследованы новые и классические задачи экстремальной комбинаторики (семейства множеств с малыми пересечениями, гипотезу Эрдёша о матчингах и т.п.) д) исследованы анти-стохастические свойств графов.

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

Образование и переподготовка кадров:

Разработаны две образовательные программы для студентов магистратуры: «Методы защиты информации» и «Продвинутые методы современной комбинаторики».

Проведена стажировка студентов и аспирантов в ведущих университетах и научных организациях: в Венгрии и Австрии.

Успешно подготовлены 1 доктор наук и 6 кандидатов наук по направлению исследования.

Подготовлены к выпуску 9 студентов магистратуры, затем поступившие в аспирантуру, и 1 студент бакалавриата, поступивший в магистратуру. Проведено значительное количество международных мероприятий (очные конференции, онлайн-конференции и воркшопы) по комбинаторике, дискретной геометрии и смежным вопросам с привлечением крупнейших специалистов мирового уровня.

Организационные и инфраструктурные преобразования:

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

Сотрудничество:

• Институт математики имени Альфреда Реньи (Будапешт, Венгрия): совместные исследования, публикации и стажировка студентов.

• Университет им. Лоранда Этвёша (Будапешт, Венгрия): стажировка студентов.

• Израильский технологический институт Технион (Хайфа, Израиль): совместные исследования и публикации.

• Университет Невшателя (Невшатель, Швейцария): совместные исследования и публикации.