Аннотация результатов, полученных в 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-пространстве существует красно-синее паросочетание Тверберга.

Аннотация результатов, полученных в 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)).

Аннотация результатов, полученных в 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.