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

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

 

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


Номер 21-71-10092

НазваниеЭкстремальные задачи на стыке дискретной вероятности и комбинаторной геометрии

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

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

Период выполнения при поддержке РНФ 07.2021 - 06.2024 

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

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

Ключевые словаЭкстремальная комбинаторика, полуалгебраические графы, покрытия, гиперграфы, случайные графы, кванторная глубина, евклидова теория Рамсея.

Код ГРНТИ27.45.00; 27.43.00; 27.47.00


 

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


Аннотация
Данная заявка посвящена ряду вопросов экстремального и рамсеевского типа, которые возникают в математике и теоретической информатике на стыке экстремальной теории графов и гиперграфов, геометрии, вероятностного метода и их приложений. Одной из основной задач мы считаем развитие "диалога'' между этими областями. В этой заявке мы рассмотрим некоторые из перспективных направлений исследований на стыке этих областей, которые можно кратко охарактеризовать следующим образом: 1) Экстремальные свойства конфигураций точек: максимизация или минимизация различных паттернов, которые могут задаваться набором точек, исследование структуры экстремальных примеров. 2) Задачи на стыке теории случайных графов, теории моделей и графовых алгоритмов. Связь с задачами из экстремальной теории множеств. 3) Многомерная комбинаторика: задачи в духе экстремальной комбинаторики для объектов с богатой геометрической структурой. 4) Геометрические задачи рамсеевского типа, связанные задачи о покрытии и вероятностный метод. Наш проект лежит на стыке вероятности, дискретной геометрии и комбинаторики, а также затрагивает некоторые области теоретической информатики. Связи между ними многочисленны и привели к очень интересному развитию этих областей. Одновременно, ясно, что исследования на их стыке не исчерпали себя: напротив, бурное развитие комбинаторики и теоретической информатики в последние годы даёт богатый материал для дальнейших изысканий. Например, развитие методов, связанных с псевдослучайностью, привело к недавнему прогрессу в центральной задаче теории Рамсея: о верхних оценках диагональных чисел Рамсея. Связь между случайными ограничениями ДНФ-формул и комбинаторикой привела к существенному продвижению в задаче Эрдеша-Радо о подсолнухах, и далее в нахождении пороговых вероятностей для свойств случайных структур. Разработанный за последнее десятилетие алгебраический метод в дискретной геометрии привёл к значительным продвижениям в задачах о свойствах конфигураций точек. Поэтому можно заключить, что эта область исследований очень активна и обладает большим потенциалом. Приведём список задач, продвижению в которых будет посвящен проект (с нумерацией, соответствующей пунктам выше): 1. Верхние оценки в задаче Эрдеша-Пёрди о числе симплексов, конгруэнтных данному. Вариант этой задачи для графов диаметров. Верхние оценки числа рёбер в полуалгебраических графах без полных двудольных подграфов. Задачи, обобщающие теорему Тверберга для точек на плоскости в терминах графа Тверберга. Задача о том, сколько различных направлений задают n точек, структурные результаты в конфигурациях, близких к экстремальным. Задача о числе рёбер в геометрическом графе на n вершинах, в котором каждое ребро пересекается со всеми рёбрами, кроме m. 2. Вопросы, связанных с гипотезой Самюэльса об отклонениях сумм случайных величин. Изучение свойств случайных фреймов. Верхние и нижние оценки размера семейства множеств, в которых нет проекций на m-элементные множества, имеющие определённый вид. 3. Улучшение существующих верхних и нижних оценок числа рёбер в (d+1)-равномерном гиперграфе, не содержащем триангуляции d-сферы. Оценки числа рёбер в полуалгебраических графах (и гиперграфах) без полных двудольных подграфов. 4. Задачи о нахождении максимального подмножества декартовых произведений множеств без изоморфных копий некоторых метрических пространств в метрике Чебышева. Оценки хроматических чисел пространств с метрикой Чебышева. Изучение связанных задач о покрытии в духе Эрдеша-Роджерса для чебышевской метрики для трёхмерного пространства, а также задач о разбиении целочисленной прямой на изометричные плитки. Предполагаемые методы исследования отражают суть проекта: это перемежение геометрических и вероятностных соображений, а также идей, пришедших из теоретической информатики, с методами классической и экстремальной комбинаторики. В частности, мы будем использовать классические комбинаторные методы, методы экстремальной комбинаторики, связанные с двойным подсчётом, квазислучайностью, суперсатурацией, алгебраические и вероятностные методы в дискретной геометрии, методы теории случайных графов, методы аддитивной комбинаторики. Все предполагаемые результаты являются новыми и внесут существенный вклад в совместное развитие изучаемых областей. У научного коллектива есть задел в работе над смежными задачами, а также большой опыт совместной работы.

Ожидаемые результаты
Все предполагаемые научные результаты соответствуют мировому уровню исследований (обладают мировой новизной). Их получение будет способствовать существенному продвижению соответствующих научных областей, а также окажет значительное влияние на развитие более прикладных исследований в области информатики, в частности, полученные результаты могут стать основой для построения более эффективных алгоритмов при анализе данных, распознавании образов и прочих задач машинного обучения, а также для оптимизации сложных вычислений. Предполагается получение следующих научных результатов: 1) Решение задачи о нахождении максимального подмножества множества [n]^d, не содержащего внутри себя в метрике Чебышёва арифметической прогрессии из n элементов c разностью 1 и обобщение этого результата на другие линейные метрические пространства, а также их прямые произведения. 2) Явное построение для каждого натурального k множества рациональных точек в интервале от (1/(k+1),1/k) мощности порядка k^4, при переходе через которые длин сторон кубов в покрытии [R\Z]^3 изменяется минимальное количество кубов в покрытии. Планируется точное решение задачи при ряде параметров. 3) Уточнение гипотезы Самуэльса для одинаково распределенных независимых случайных величин с двумя атомами, которое позволит упорядочить распределения по значению вероятности отклонения суммы случайных величин от математического ожидания. 4) Проверка верности утверждения, состоящего в том, что для любого четного числа точек на плоскости найдётся гамильтонов цикл, являющийся графом Тверберга. 5) Получение новой верхней оценки в задаче Эрдеша-Пёрди вида n^{cd} при c<1. 6) Решение задачи Эрдеша-Пёрди для графов диаметров (задача решается для множеств, диаметр которых равен единице). 7) Получение новых верхних и нижних оценок размера семейства множеств, в котором нет проекций на 4-элементные множества, содержащие цикл длины 4. 8) Доказательство того, что при почти всех p свойства, справедливые с вероятностью, стремящейся к 1, в случайной frame с вероятностью ребра p, и являющиеся frame validity в модальной логике, нельзя аксиоматизировать с помощью s-extension аксиом и еще некоторого другого конечного набора аксиом. 9) Доказательство гипотезы Ямисона в случае, когда n точек в общем положении задают n+O(\sqrt{n}) направлений: точки при этом лежат на некоторой квадрике и являются вершинами аффинного образа некоторого правильного m-угольника. 10) Получение новых верхних оценок на число рёбер в полуалгебраических графах без полных двудольных подграфов с t вершинами в каждой доле, при условии полиномиального роста t от числа вершин. 11) Улучшение существующих верхних и нижних оценок числа рёбер в (d+1)-равномерном гиперграфе, не содержащем триангуляции d-сферы. 12) Решение проблемы Шмидта-Тулера о трёхточечных покрытиях целочисленной прямой. 13) Получение точного значения на число рёбер в геометрическом графе на n вершинах, в котором каждое ребро пересекается со всеми рёбрами, за исключением не более m других (при n значительно большем, чем m). 14) Получение новых верхних и нижних оценок размера семейства множеств, в котором нет проекций на 2m-элементные множества, содержащие полный m-дольный гиперграф с долями размера 2 (условия, соответствующие двудольному аналогу свойства из определения VC-размерности).


 

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


Аннотация результатов, полученных в 2021 году
Теория Рамсея в пространстве с метрикой Чебышева. Следующая классическая задача комбинаторной геометрии была поставлена Нельсоном в 1950 г.: чему равно минимальное число цветов, требуемое для того, чтобы покрасить евклидову плоскость таким образом, что никакие две точки на расстоянии 1 не получат один и тот же цвет? Полученные в данном направлении научные результаты можно разбить на три группы. Первая группа посвящена задачам об одномерных метрических пространствах, которые мы называем батонами. Были значительно упрощены некоторые рассуждения из статьи Купавского и Сагдеева для таких метрических пространств, а также для большого класса батонов были получены асимптотически точные значения оснований экспонент в оценках соответствующих хроматических чисел пространства с максимум-нормой. Помимо этого, была установлена связь между этими задачами и задачей теоретико-числового характера о подмножествах целых чисел. Вторая группа результатов посвящена декартовым произведениям арифметических прогрессий. Последняя группа результатов посвящена задачам о бесконечных метрических пространствах. Ниже дано более подробное описание полученных результатов. Первый полученный результат состоит в выявлении тесной связи между хроматическим числом пространства с максимум-нормой и запрещенным целочисленным батоном и максимальной плотностью С подмножества целых чисел, которое не содержит транслятов того же самого батона (точнее, батона или его отражения). Точнее, хроматическое число равно C^{-n+o(n)}. Важно отметить, что подобные плотности изучались в целом ряде различных контекстов, и имеется множество вариантов этой задачи в терминах упаковок, покрытий, замощений, блокирующих множеств, избегающих множеств, раскрасок и т.д. В частности, команда проекта имеет хорошее понимание данной задачи для k-элементных батонов при k стремящемся к бесконечности. Более того, существует алгоритм, который позволяет посчитать точное значение С для заданного батона, правда сложность его экспоненциальна. Однако, нахождение формулы для точного значения С для произвольных батонов выглядит очень трудной задачей. Для двухэлементных батонов она тривиальна, но даже для трёхэлементных в общем случае не решена. Планируется изучить этот вопрос в рамках отдельной статьи. Также были получены подобные результаты и для не обязательно целочисленных батонов. В частности, для множества линейно независимых над z чисел a_1,...,a_k получено, что соответствующее хроматическое число с запрещенным батоном B(a) растёт как ((k+1)/k+o(1))^n. Вторая группа результатов относится к декартовым произведениям, с естественным расстоянием, которое равняется максимуму покоординатных расстояний. Во-первых, были получены очень точные верхние и нижние оценки хроматического числа степеней батонов B_k. В частности, из оценок следует, что их хроматическое число растёт как ((k+1)/k+o(1))^n для любой фиксированной степени. Настолько точная оценка была получена за счёт того, что было найдено в точности значение числа независимости некоторого релевантного гиперграфа. Один сложный и интересный вопрос состоит в том, чтобы понять поведение хроматических чисел декартовых произведений двух разных батонов. В частности, верно ли, что основание экспоненты в точном значении в этом случае будет равно минимуму из двух оснований для батонов, произведение которых мы рассматриваем. Данную задачу не получилось решить в общем случае, однако получен ответ в случае, когда каждый из батонов является арифметической прогрессией. В частности, из этого результата следует, что хроматическое число декартового произведения нескольких двухэлементных батонов равно (2+o(1))^d. К третьей группе результатов относится изучение бесконечных метрических пространств. В евклидовом случае ситуация простая: для каждого n и произвольного бесконечного метрического пространства X существует раскраска в два цвета евклидова пространства без одноцветных копий X. На самом деле верно гораздо более сильное утверждение (см. работу Эрдеша и др.) Картина в случае пространства с максимум-нормой оказывается гораздо более сложной. В рамках проекта было показано, что для любого бесконечного метрического пространства соответствующее хроматическое число не более n+1. Более того, эта оценка является точной для геометрических прогрессий с достаточно большим знаменателем (зависящим от n). Этот результат, однако, не доказывает существования одного бесконечного метрического пространства с хроматическим числом, которое стремится к бесконечности с ростом n, то есть не влечёт существования бесконечного l_\infty-рамсеевского множества. Подобный результат был показан в другой теореме. Однако, на данный момент удалось получить только логарифмическую по порядку оценку. Улучшение этой оценки до линейной или хотя бы полиномиальной является интересной открытой проблемой. Покрытие тора кубами. Мы изучили вопрос о минимальном количестве кубов с заданной стороной c<1 в покрытии d-мерного тора [R/Z]^d при d=3. Нам удалось найти точное значение минимального количества кубов в покрытии при всех c из [7/15,1). Кроме того, для всех целых k>1 мы нашли минимальное количество кубов со стороной c<1 в покрытии [R\Z]^3 при всех c в интервале от (k^3-1)/(k^4-1) до (k^2-1)/(k^3-k-1). Для доказательства полученных результатов мы установили, что задача нахождения искомой величины сводится к своему дискретному аналогу - к задаче нахождения минимального количества кубов со стороной s, покрывающих [Z/tZ]^d для некоторых s,t таких, что s/t близко к c. Таким образом, эти вспомогательные утверждения влекут, что задача сводится к рассмотрению счетного множества значений c, причем количество таких значений в каждом интервале вида [1/r,1/(r-1)] конечно. Монотонность функции распределения биномиальной случайной величины. Знаменитая гипотеза Самуэльса о вероятности “малого” отклонения суммы случайных величин от математического ожидания имеет непосредственные приложения в комбинаторике: например, для гипотезы Эрдеша о паросочетаниях в однородных гиперграфах. В 2018 году Жуковским в совместной работе с Д. Дмитриевым было показано, что для одинаково распределенных случайных величин с двумя атомами задача эквивалентна задаче о максимуме функции распределения биномиальной случайной величины с параметрами n и b/(n+c) в точке b. В той же статье было доказано, что эта функция при c=0 возрастает при n>3b+2 и убывает при n<3b+1. В рамках проекта для каждого положительного c, не превосходящего 1, мы нашли асимптотику значения аргумента, при котором меняется монотонность (по b) функции распределения биномиальной случайной величины с параметрами n и b/(n+c) в точке b. Кроме того, при c=1 мы доказали, что эта функция строго возрастает (по b). Последний результат позволил отранжировать распределения случайных величин в теореме Самуэльса по значениям вероятности отклонения от математического ожидания при c=1. Графы Тверберга. Графом Тверберга называется граф G, множество вершин которого является конечным множеством точек в евклидовом d-пространстве в том случае, если пересечение шаров, индуцированных его ребрами, не пусто. Совершенное паросочетание для множества, состоящего из чётного числа точек в евклидовом d-пространстве, называется паросочетанием Тверберга, если оно является графом Тверберга. Гамильтонов цикл для множества точек в евклидовом d-пространстве называется циклом Тверберга, если он является графом Тверберга. В ходе исследования с помощью применения идеи о биссекторных прямых были доказаны следующие результаты: Для любого конечного множества точек на плоскости существует цикл Тверберга (то есть мы полностью решили проблему существования циклов Тверберга). Для любого набора из n красных и n синих точек на плоскости существует красно-синее паросочетание Тверберга. Кроме того, с помощью метода бесконечного спуска, нам удалось доказать следующие результаты: Для любого четного числа точек в евклидовом d-пространстве существует открытое паросочетание Тверберга. Для n красных и n синих точек в евклидовом d-пространстве существует красно-синее паросочетание Тверберга.

 

Публикации

1. Богданов И.И., Григорян О.Р., Жуковский М.Е. О покрытии тора кубами / ON COVERINGS OF TORI WITH CUBES ДОКЛАДЫ РОССИЙСКОЙ АКАДЕМИИ НАУК. МАТЕМАТИКА, ИНФОРМАТИКА, ПРОЦЕССЫ УПРАВЛЕНИЯ / Doklady Mathematics, том 105, стр. 75–77, 2022 (год публикации - 2022) https://doi.org/10.31857/S2686954322020072

2. Волков Н.А., Дмитриев Д.И., Жуковский М.Е. О поведении биномиального распределения вблизи медианы / BEHAVIOUR OF BINOMIAL DISTRIBUTIONS NEAR ITS MEDIANS ДОКЛАДЫ РОССИЙСКОЙ АКАДЕМИИ НАУК. МАТЕМАТИКА, ИНФОРМАТИКА, ПРОЦЕССЫ УПРАВЛЕНИЯ / Doklady Mathematics, том 105, стр. 89–91, 2022 (год публикации - 2022) https://doi.org/10.31857/S2686954322020199

3. Питер Франкл, Сергей Киселев, Андрей Купавский On the maximum number of distinct intersections in an intersecting family Discrete Mathematics, Том 345, Выпуск 4, Номер статьи 112757 (год публикации - 2022) https://doi.org/10.1016/j.disc.2021.112757


Аннотация результатов, полученных в 2022 году
В рамках второго года выполнения проекта мы изучили задачи, связанные с известной задачей Эрдеша о единичных расстояниях: чему равен максимум количества единичных расстояний среди n точек на плоскости? Этот вопрос далёк от разрешения, однако в размерности d > 3 становится гораздо проще. Этот вопрос можно нетривиальным образом обобщить на произвольную размерность следующим образом. Пусть C(d,k,n) это максимум по всем k-вершинным симплексам S и n-элементным подмножествам P в d-мерном евклидовом пространстве числа конгруэнтных копий S в P. Следующая гипотеза была сформулирована Эрдешом и Пэрди, а также Агарвалом и Шариром: Для всех d>3 и k не превосходящем d имеем С(d,k,n)=O_d(min{n^k,n^{d/2}}) для чётных d и C(d,k,n)=O_d(min{n^k,n^{d/2-1/6}}) для нечётных d. Эта гипотеза нетривиальна только для k>d/2. До нашей работы продвижения по этой гипотезы были лишь для d<7. У нас же получилось доказать следующее: Для каждого d>3, k<d+2 и epsilon>0, имеем C(d,k,n)=O_{d,epsilon}( n^{5d/8+k/8+epsilon}). В частности, получаем что C(d,k,n)=O_{d,epsilon}( n^{3d/4+epsilon}) для каждого k< d+1. Одним из следствий из этого результата являются наилучшие известные оценки числа подобных симплексов в конфигурациях из n точек в d-мерном пространстве. Наш результат значительно улучшил результаты из работы Агарвала, Апфельбаума, Пэрди и Шарира, в которой они смогли доказать верхние оценки вида O_d(n^{d-const}) для некоторой небольшой константы. По-видимому, поведение величины C(d,k,n) не меняется существенным образом при замене произвольного симплекса на единичный. Однако есть ещё одна естественная постановка задачи, в которой ответ получается существенно другим. Пусть DIAM(d,k,n) это максимальное число единичных k-симплексов на множестве диаметра 1, состоящего из n точек в d-мерном пространстве. В рамках нашего исследования мы получили следующий результат: Для каждого 1<k <d+2 и epsilon>0 имеем DIAM(d,k,n)=O_{d,epsilon}(n^{d/2+epsilon}). В этих результатах мы используем различные вероятностные методы, связанные с разрезаниями. Для их эффективного применения потребовался аккуратный анализ возникающих рекурсий, который можно свести к классу задач линейного программирования. Для изучения этих линейных программ нам потребовался их аккуратный анализ, а также анализ геометрического смысла различных ограничений, в сочетании с классическими комбинаторными методами. Следующей заявленной темой были исследования случайных дистанционных графов, т.е. случайных подграфов дистанционного графа. Дистанционный граф G(n,r,s) – это граф, вершины которого – элементы булевого куба {0,1}^n веса r, и ребра соединяют элементы, скалярное произведение которых равно s. Доказано, что необходимым и достаточным условием, которому должен удовлетворять переменный размер цикла t=t(n) для того, чтобы в графе G(n,r,s) число простых циклов такого размера было асимптотически равно общему числу циклов (включая самопересекающиеся циклы), является t=o(min(N1/2,N1)), где N — число вершин в графе G(n,r,s), N1 — степень вершины в графе G(n,r,s) (граф G(n,r,s) регулярный, т.е. все вершины имеют одинаковую степень). Также получены точные асимптотические выражения для числа простых циклов размера t=o(min(N1/2,N1)) в графе G(n,r,s) при попадании t=t(n) в различные интервалы (в пределах указанного ограничения). Если функция t(n) сверхлогагрифмическая, т.е. t>>ln(n), то число простых циклов (асимптотически) принимает несложный вид N1t/(2t). Если же t(n) имеет логарифмический порядок, т.е. t~c⋅ln(n), то, в зависимости от величины c, асимптотика числа простых циклов будет описываться различными функциями, вид которых также известен (не приводятся здесь ввиду громоздкости). Для доказательства также используется спектр графа G(n,r,s). Мы также исследовали число пар непересекающихся рёбер в геометрических графах. Конкретно мы исследовали два вопроса: 1) Найти точное наибольшее значение на число рёбер в геометрическом графе на n вершинах, в котором каждое ребро пересекается со всеми рёбрами за исключением не более m других (при n значительно большем, чем m). 2) Найти наименьшее число d(e,n) такое, что в любом геометрическом графе на n вершинах с e ребрам найдётся d(e,n) непересекающихся пар рёбер. Для решения этих задач мы применили довольно сложную индукцию с методом перераспределения зарядов (двойной подсчёт). Первую задачу нам удалось решить полностью, а вторую при условии, что все вершины геометрического графа - выпуклые (не находятся в выпуклой оболочке своих соседей). Помимо заявленных задач, мы исследовали и другие вопросы, в основном связанные со свойствами кнезеровских графов и пересекающихся семейств. Семейство множеств называется пересекающимся, если любые два его множества имеют непустое пересечение. Пересекающиеся семейства играют огромную роль в экстремальной теории множеств, так как часто оказываются экстремальными примерами в ее задачах. Особенно часто возникают т.н. звезды – пересекающиеся семейства, все множества которых содержат некоторый фиксированный элемент. Пусть n > k > 0 – два натуральных числа. Рассмотрим пересекающиеся семейства, состоящие из подмножеств множества {1, …, n} мощности k. В своей статье “On the number of distinct differences in an intersecting family” П. Франкл показал, что если n > k (k + 3), то для любого пересекающегося семейства cF семейство его разностей D(cF) = {F\F’ : F, F’ ∊ cF} имеет максимальную мощность, если cF – звезда. Он предположил, что это верно всегда при n > 2k. В рамках данного исследования мы приводим контрпримеры к этой гипотезе и показываем, что если n = c * k для некоторого c ∊ (2, 4) и k достаточно большое, то существует пересекающееся семейство, семейство разностей которого больше, чем у звезды. Один из таких примеров – максимальное пересекающееся семейство, не являющееся звездой. Основной же наш результат в данном направлении состоит в том, что для n > 50 k ln(k) и k >= 50, гипотеза Франкла верна. Кнезеровским графом с параметрами n, k называют граф, чье множество вершин — это подмножества множества {1, …, n} размера k, а два подмножества соединены ребром, если они не пересекаются. Мы исследовали предписанное хроматическое число Кнезеровского графа. Зафиксируем произвольное s >= 3. Нам удалось доказать, что предписанное хроматическое число не меньше, чем 1/(2 s^2) n ln(n), если n достаточно большое, а 3 <= k <= n^{½ - 1/s}. Если же k = 2, то предписанное хроматическое число хотя бы n ln(n) / 32 для достаточно больших n. Доказательство этого факта основывается на методе контейнеров и некотором вероятностном рассуждении. Также мы получили верхнюю оценку предписанного хроматического числа: мы показали, что оно не превосходит n + n ln(n/k) для всех n >= 2k > 0. Здесь мы снова использовали вероятностное рассуждение. Наконец, нам были изучены следующие задачи метрического типа. Пусть M – метрическое пространство. В рамках данного исследования мы рассмотрели максимальные множества с нечетными расстояниями и максимальные последовательности, равноудаленные вправо. Множество называется множеством с нечетными расстояниями, если расстояние между любыми двумя его точками целое и нечетное. Последовательность s_1, …, s_t метрического пространства M называется равноудаленной вправо, если для всех i < j < k справедливо d(s_i, d_j) = d(s_i, d_k). Прежде две эти характеристики изучались преимущественно для Евклидова пространства. В рамках нашего исследования мы рассматриваем случаи, когда M – это R^n с чебышевской или манхеттенской метрикой. В частности, мы получили следующие результаты: 1) Максимальная мощность множества с нечетными расстояниями в R^n с чебышевской метрикой равняется 2^n. 2) Максимальная длина равноудаленной вправо последовательности в R^n с чебышевской метрикой равняется 2^n - 1. 3) Максимальная мощность множества с нечетными расстояниями в R^n с манхеттенской метрикой хотя бы 4n - 1. 4) Максимальная длина равноудаленной вправо последовательности в R^n с манхеттенской метрикой не превосходит n! * n * ln(n) * (4 + o(1)).

 

Публикации

1. Буланкина В., Купавский А.Б. Choice number of Kneser graphs Discrete Mathematics, том 345, выпуск 11, статья 113097, ноябрь 2022 (год публикации - 2022) https://doi.org/10.1016/j.disc.2022.113097

2. Голованов А.И., Купавский А.Б., Сагдеев А.А. Odd-distance and right-equidistant sets in the maximum and Manhattan metrics European Journal of Combinatorics, том 107, статья 103603, январь 2023 (год публикации - 2023) https://doi.org/10.1016/j.ejc.2022.103603

3. Пирахмад О., Полянский А.А., Василевский А. Intersecting Diametral Balls Induced by a Geometric Graph Discrete & Computational Geometry, 2022 (год публикации - 2022) https://doi.org/10.1007/s00454-022-00457-x

4. Франкл П., Киселев, С.Г. Купавский А.Б. Best possible bounds on the number of distinct differences in intersecting families European Journal of Combinatorics, том 107, статья 103601, январь 2023 (год публикации - 2023) https://doi.org/10.1016/j.ejc.2022.103601

5. Чернега Н., Полянский А.А., Садыков Р. С. Disjoint Edges in Geometric Graphs Graphs and Combinatorics, том 38, статья 162, 2022 (год публикации - 2022) https://doi.org/10.1007/s00373-022-02563-2


Аннотация результатов, полученных в 2023 году
Граф называется полуалгебраическим в R^d, если его можно описать с помощью знаков конечного числа многочленов ограниченной степени, зависящих от координат двух точек в R^d (т.е., наличие ребра определяется, например, выполнением или невыполнением некоторых полиномиальных равенств или неравенств, заданных этими многочленами). Такие графы естественным образом возникают в вычислительной геометрии в задачах геометрического поиска, планирования движения роботов и т.п. Например, в этот класс попадают графы единичных расстояний, графы инциденций точек и плоскостей графы пересечений отрезков и проч. В отличие от абстрактных графов, многие экстремальные характеристики таких графов в первую очередь зависят от размерности d. Одна из классических задач теории графов – задача Заранкевича о том, насколько много рёбер может быть в графе, не содержащем полного двудольного подграфа K_{s,t}. Известно, что для абстрактных графов эта величина по крайней мере n^{2-1/s} для s<t. Однако, для полуалгебраических графов эта величина растет как Сn^{2-1/d}, где С зависит от s,t. Нам удалось получить результаты типа Заранкевича для полуалгебраических графов, в которых экстремальная функция зависит полиномиально от размера запрещенного двудольного подграфа. Более того, наш результат по-видимому дает точный ответ в размерностях d=2,3, а также для важного класса графов: графов единичных расстояний. Пусть дано конечное подмножество S целых чисел. Все множества вида x+S, где x – это некоторое целое число, мы будем называть параллельными переносами S. Мы изучили задачи, связанные с плотностью упаковок и покрытий множества целых чисел переносами данного множества S. Подобные задачи рассматривались Эрдешем и Лоренцем в 1950-х гг., а несколько позднее Ньюманом. Несложно видеть, что мы можем замостить множество целых чисел переносами произвольного двухточечного множества. Ситуация с трехточечными множествами становится сложнее. В некоторых случаях возможно получить упаковки/покрытия, которые являются замощениями, однако, в общем случае это невозможно. Ньюман доказал, что плотность не превосходит ⅖ для произвольных покрытий, и что эта оценка точна для множества {0,1,3}. Шмидт и Туллер около 20 лет назад предложили некоторые явные выражения для плотности упаковок и покрытий трехточечными множествами, которые зависят от длин интервалов между точками и некоторых делимостей по модулю 3. Нашим основным результатом в данном направлении является доказательство этой гипотезы. Нам удалось получить этот результат с помощью довольно тонкого рассуждения о двойном подсчете. В 1966 г. Хельге Тверберг доказал, что для любых (r - 1)(d + 1) + 1 точек в R^d существует разбиение их на r частей, выпуклые оболочки которых пересекаются. Мы изучили вариант теоремы Тверберга, недавно представленный Хумером и др. и Собероном и Тангом. Мы развиваем подход, представленный в наших предыдущих работах. Для любого графа мы предполагаем, что его вершинное множество является конечным подмножеством R^d. Вес графа G, обозначаемый через cost G, – это сумма евклидовых расстояний между парами вершин, соединенных ребром в G. Мы определяем максимальное (по сумме длин рёбер) дерево конечного точечного множества X в R^d как дерево с множеством вершин X, которое максимизирует вес среди всех деревьев с множеством вершин X. Аналогично, мы определяем максимальное (по сумме длин рёбер) паросочетание четного точечного множества X в R^d как совершенное паросочетание с вершинами в X, которое максимизирует вес среди всех паросочетаний с вершинами в X. Для двух точек x, y в R^d мы обозначаем через B(xy) замкнутый евклидов шар с диаметром xy. Мы говорим, что шар B(xy) индуцирован xy. Граф G называется графом Тверберга, если шары B(xy), где xy в E(G), имеют общую точку. Аналогично, граф является открытым графом Тверберга, если открытые шары с диаметрами, индуцированными его ребрами, пересекаются. Совсем недавно Абу-Аффаш и др. доказали, что максимальное дерево любого конечного точечного множества на плоскости является графом Тверберга. Мы обобщили их результат на большие размерности: Максимально суммарное дерево любого конечного точечного множества в R^d является графом Тверберга. В 2023 г. Берег и др. показали, что максимальное паросочетание для любого четного множества на плоскости является графом Тверберга. Наш второй результат – это новое доказательство немного более сильной версии их результата в предположении, что точки различны: максимальное паросочетание для любого четного множества различных точек на плоскости является открытым графом Тверберга. Для данных целых чисел n,k мы можем рассмотреть так называемый кнезеровский граф. Его вершинами являются все k-элементные подмножества множества {1,...,n}, а ребрами соединены непересекающиеся подмножества. Число независимости кнезеровского графа было найдено Эрдешем, Ко и Радо в их знаменитой работе (пересекающиеся семейства k-элементных множеств – это в точности независимые подмножества кнезеровского графа KG_{n,k}). Оно равно {n-1\choose k-1}. Изучению пересекающихся семейств и смежных вопросов посвящен отдельный раздел экстремальной комбинаторики. Далее исследователи изучали следующий вопрос. Пусть нам дано подмножество вершин кнезеровского графа, чуть большее размера максимального независимого множества. Насколько много ребер должно появиться в таком подмножестве? Различные результаты были получены Катоной, Катоной и Катоной; Дасом и Траном; Балогом и соавторами; Судаковым и соавторами. Относительно недавно Хуанг получил следующий прорывной результат касательно графа гиперкуба: если мы рассмотрим подмножество вершин размера 2^{n-1}+1, то есть на 1 больше независимого, то в нём обязательно есть вершина степени sqrt(n). Этот результат привёл к разрешению важной гипотезы о чувствительности в теоретической информатике. Фридгут в личном общении задал подобный вопрос касательно кнезеровских графов. А именно, верно ли, что для подмножества вершин кнезеровского графа размера {n-1\choose k-1}+1, будет верен некоторый аналог результата Хуанга для гиперкуба? Нам удалось доказать это утверждение в предположении n>ck^2 в гораздо более сильной форме. А именно, мы изучили степени в подграфах размера большего, чем пример в теореме Хилтона-Милнера, а также получили сильные структурные результаты касательно формы экстремальных примеров. Мы также получили широкое обобщение классического результата Боллобаша и Эрдеша о числе независимости в “типичных” графах. Напомним, что в биномиальном случайном графе G(n,p) ребра между вершинами множества {1,...,n} проводятся независимо с вероятностью p каждое. Так, G(n,½) – это граф, выбранный равновероятно из множества всех графов на заданном множестве из n вершин. Боллобаш и Эрдёш в 1976 г. доказали, что если p является константой, то с вероятностью, стремящейся к 1 (при стремлении числа вершин к бесконечности), число независимости случайного графа (т.е. максимальный размер множества вершин, индуцирующего пустой граф) сконцентрировано в двух точках. После этого открытия появился ряд статей (Дутта, Жуковский, Камальдинов, Канг, Кривошапко, МакДиармид, Скоркин, Субраманиан, Фунтулакис, 2010-2021 гг.), демонстрирующих концентрацию в двух точках и для размера максимального индуцированного подграфа ограниченной максимальной степенью, подграфа с ограниченным числом ребер, дерева, подграфа с заданной средней степенью, леса. Известны концентрационные результаты для величин подобного рода и для p, являющихся функциями от n и стремящимися к нулю с ростом n. Так, в 1990 г. Фриз доказал концентрацию в интервале длины o(1/p) вокруг функции, асимптотически равной 2 log(np)/p. Мы доказали концентрацию размера наибольшего индуцированного леса (неограниченной степени) и леса ограниченной степени в интервале длины o(1/p). Нами также доказана двухточечная концентрация наибольшего размера индуцированного леса ограниченной степени и индуцированного дерева ограниченной степени при постоянной вероятности проведения ребра p.

 

Публикации

1. Ахмеджанова М. Б., Кожевников В. С. Induced Forests and Trees in Erdős–Rényi Random Graph Doklady Mathematics, 2024 (год публикации - 2024) https://doi.org/10.1134/S1064562424701886

2. Барабанщикова П. Ю., Полянский А. А. Intersecting diametral balls induced by a geometric graph II Discrete Mathematics, том 347, выпуск 1, январь 2024, статья 113694 (год публикации - 2024) https://doi.org/10.1016/j.disc.2023.113694

3. Купавский А.Б. Rainbow version of the Erdős Matching Conjecture via concentration Combinatorial Theory, том 3, выпуск 1 (год публикации - 2023) https://doi.org/10.5070/C63160414

4. Франкл Н., Купавский А.Б., Сагдеев А.А. Solution to a conjecture of Schmidt and Tuller on one-dimensional packings and coverings Proceedings of the American Mathematical Society, том 151, номер 6, июнь 2023, стр. 2353-2362 (год публикации - 2023) https://doi.org/10.1090/proc/16254

5. Франкл Н., Купавский А.Б., Сагдеев А.А. Max-norm Ramsey theory European Journal of Combinatorics, Том 118, май 2024, статья 103918 (год публикации - 2024) https://doi.org/10.1016/j.ejc.2024.103918


Возможность практического использования результатов
не указано