КАРТОЧКА ПРОЕКТА ФУНДАМЕНТАЛЬНЫХ И ПОИСКОВЫХ НАУЧНЫХ ИССЛЕДОВАНИЙ,
ПОДДЕРЖАННОГО РОССИЙСКИМ НАУЧНЫМ ФОНДОМ
Информация подготовлена на основании данных из Информационно-аналитической системы РНФ, содержательная часть представлена в авторской редакции. Все права принадлежат авторам, использование или перепечатка материалов допустима только с предварительного согласия авторов.
ОБЩИЕ СВЕДЕНИЯ
Номер проекта 22-11-00131
НазваниеАлгебраические и случайные комбинаторные структуры
Руководитель Петров Федор Владимирович, Доктор физико-математических наук
Организация финансирования, регион федеральное государственное бюджетное образовательное учреждение высшего образования "Санкт-Петербургский государственный университет" , г Санкт-Петербург
Конкурс №68 - Конкурс 2022 года «Проведение фундаментальных научных исследований и поисковых научных исследований отдельными научными группами»
Область знания, основной код классификатора 01 - Математика, информатика и науки о системах; 01-114 - Дискретная математика и математическая кибернетика
Ключевые слова случайные графы, экстремальные статистики, асимптотическая независимость, экстремальная теория множеств, сатурация, паросочетания, пересекающиеся семейства, алгебраическая теория графов, аддитивная комбинаторика, тензорный ранг, матроиды, полиномиальный метод
Код ГРНТИ27.45.00
ИНФОРМАЦИЯ ИЗ ЗАЯВКИ
Аннотация
Комбинаторика является одной из наиболее интенсивно развиваемых областей математики, что обусловлено как внутренней логикой её развития, так и многочисленными приложениями --- как внутри математики, так и в смежных областях (прежде всего, компьютерных науках). Проект призван объединить усилия сложившихся и активно работающих коллективов в Петербурге и в МФТИ, занимающихся как алгебраическими методами в комбинаторике (спектральная теория графов, полиномиальный метод), так и вероятностными (случайные графы, экстремальная комбинаторика). Существующий солидный задел позволяет рассчитывать на получение новых серьёзных результатов.
ОТЧЁТНЫЕ МАТЕРИАЛЫ
Публикации
1.
Крачун Д. Н., Петров Ф. В.
On the size of $A+\lambda A$ for algebraic $\lambda$
Moscow Journal of Combinatorics and Number Theory, Vol. 12 (2023), No. 2, 117–126 (год публикации - 2023)
10.2140/moscow.2023.12.117
2. Петров Ф. В. Asymptotics of Landau--Okhotin function Acta Mathematica Hungarica (год публикации - 2023)
3.
Голованов А. И.
On the maximum size packings of disks with kissing radius 3
Moscow Journal of Combinatorics and Number Theory, том 11, номер 3, страницы 263-286 (год публикации - 2022)
10.2140/moscow.2022.11.263
4. Колупаев Д, Купавский А. Б. Erd˝os Matching Conjecture for almost perfect matchings Discrete Mathematics (год публикации - 2023)
Публикации
1.
Губкин П.
On unique tensor rank decomposition of 3-tensors
LINEAR AND MULTILINEAR ALGEBRA, опубликована онлайн (год публикации - 2023)
10.1080/03081087.2023.2211718
2.
Барабанщикова П., Полянский А.
Intersecting ellipses induced by a max-sum matching
Journal of Global Optimization, published online (год публикации - 2023)
10.1007/s10898-023-01312-w
3.
Франкл П., Купавский А.
Perfect matchings in down-sets
Discrete mathematics, Volume 346, Issue 5, 113323 (год публикации - 2023)
10.1016/j.disc.2023.113323
Аннотация результатов, полученных в 2024 году
Нам удалось найти практически точный ответ на следующий вопрос: при каком соотношении параметров n,k в любой правильно раскраске графа Кнезера KG_{n,k} в минимальное число цветов обязательно появляются тривиальные цвета? Это происходит примерно при n>2k^2.
Получена предельная теорема для максимального числа симметричных расширений в плотном биномиальном случайном графе Эрдеша--Реньи: после подходящего масштабирования максимальное число расширений не обязательно сходится по распределению к распределению Гумбеля, что было верно для всех известных до этого результатов. Более того, оно выражается в терминах специальной интегральной показательной функции, то есть не может быть выражена в элементарных функциях.
Доказано, что пороговая вероятность для свойства наличия триангуляции k-угольника в случайном графе для доли количества вершин на границе a=k/n, не стремящейся к 1, равняется n^(-1/3-a).
Доказано, что сумма весов ребер в знаковых реберно-доминированных графах не меньше, чем -n^2/36.
Показано, что минимальный знаковый реберно-доминированный граф с отрицательной суммой весов содержит 9 вершин.
Доказано, что точки ветвления в любом решении задачи Джильберта--Штейнера на евклидовой плоскости имеют степень 3.
Построены примеры ветвления большей степени в размерностях 3 и выше.
Обобщено правило Мурнагана--Накаямы на случай полных флагов, а именно, описано правило умножения полинома Шуберта на сумму k-х степеней переменных x_i через пути в графе Брюа.
Публикации
1.
Киселев С.Г., Купавский А.Б.
Trivial colors in colorings of Kneser graphs
Discrete Mathematics, 347 (2024) 113869 (год публикации - 2024)
10.1016/j.disc.2023
2.
Вахрушев С.В., Жуковский М.Е.
MAXIMUM NUMBER OF SYMMETRIC EXTENSIONS IN RANDOM GRAPHS
SIAM Journal on Discrete Mathematics, 38:3 (2024) 2468-2488 (год публикации - 2024)
10.1137/23M1588706
3.
Вахрушев С.В., Жуковский М.Е., Скоркин А.Ю.
Насыщение в кнезеровских графах
Математические заметки, Математические заметки, 2024, том 116, выпуск 2, страницы 185–194 (год публикации - 2024)
10.4213/mzm14170
4.
Д. Дёмин, М. Жуковский
First order complexity of finite random structures
LICS '24: Proceedings of the 39th Annual ACM/IEEE Symposium on Logic in Computer Science
, Article No.: 31, Pages 1 - 14 (год публикации - 2024)
10.1145/3661814.3662127
5.
Крачун Д., Миргалимова Р.
Strong greedoid structure of r-removed P-orderings
The Electronic Journal of Combinatorics, Volume 31, Issue 4 (2024)
Article Number
P4.40 (год публикации - 2024)
10.37236/12403
6. Черкашин Д.Д., Петров Ф.В. Branching points in the planar Gilbert–Steiner problem have degree 3 Pure and Applied Functional Analysis (год публикации - 2025)
7. Прозоров П.К., Черкашин Д.Д. Об устойчивости взвешенного степенного перечислителя остовных деревьев Известия Российской академии наук. Серия математическая, Том 89, No 1, 2025 (год публикации - 2025)
8.
Петров Ф. В.
Комбинаторные следствия многих делителей нуля в групповом кольце
Функциональный анализ и его приложения, том 58, выпуск 1, стр. 104-116 (год публикации - 2024)
10.4213/faa4186
Возможность практического использования результатов
Результаты по переносу массы (задача Джильберта -- Штейнера) могут использоваться для совершенствования логистики, городского и транспортного планирования.