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