Экстремальные задачи теории множеств и их применения к задачам теории Рамсея тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат наук Сагдеев Арсений Алексеевич

• Сагдеев Арсений Алексеевич
• кандидат наук
• 2021

Оглавление диссертации кандидат наук Сагдеев Арсений Алексеевич

1.3.2 Доказательство теоремы

Алгоритм преобразования двух семейств подмножеств

Первый случай остановки алгоритма

Второй случай остановки алгоритма

Третий случай остановки алгоритма

Завершение доказательства теоремы

1.4 Анализ нового алгоритма

1.4.1 Оптимизация вычислений в новом алгоритме

Вычисление А\(а, р, 61,62)

Вычисление Д2(а, р, 61, 62)

Вычисление Д3(а, р,61,62)

1.4.2 Некоторые частные случаи применения теоремы

2 Асимптотические свойства {0,1}—графов

2.1 Числа независимости графов С(п,к,1)

2.2 "Достаточно большое" подмножество вершин графа С(п, к, £) обязательно содержит внутри себя "почти все" его ребра: доказательство на основе теоремы Франкла-Редля о двух семействах с запрещенным перекрестным пересечением

2.3 "Достаточно большое" подмножество вершин графа С(п, к, £) обязательно содержит внутри себя "почти все" его ребра: новое доказательство

3 Два приложения к теории Рамсея

3.1 Дистанционные графы с большим обхватом и большим хроматическим числом

3.1.1 Формулировка основных результатов

3.1.2 Доказательство теоремы

3.1.3 Доказательство теоремы

3.2 Хроматическое число п—мерного пространства с запрещенным правильным 1—мерным симплексом

3.2.1 Случай 1 =

3.2.2 Общий случай

Заключение

Список литературы

Введение диссертации (часть автореферата) на тему «Экстремальные задачи теории множеств и их применения к задачам теории Рамсея»

Введение

Актуальность темы исследования и степень ее разработанности

Задача, с которой так или иначе связаны все рассматриваемые в настоящей работе проблемы, берет свое начало в 1950 году, когда Нельсон заинтересовался вопросом о том, какого минимального числа цветов х(К2) достаточно для того, чтобы раскрасить евклидову плоскость К2 так, что никакие две точки на единичном расстоянии не оказались бы покрашены в один и тот же цвет (см. [1]). Столь элементарное определение хроматического числа плоскости х(К2) может создать впечатление о том, что и найти точное значение этой величины будет нетрудно. Однако, за прошедшие 70 лет этого до сих пор не было сделано, и лучшие оценки, которые мы имеем на сегодняшний день, таковы:

5 < х(К2) < 7, (1)

причем неравенство х(К2) > 5 было доказано только в 2018 году в работе [2].

Одним из наиболее естественных обобщений исходной задачи Нельсона является постановка вопроса о нахождении хроматического числа х(Кп) евклидова пространства определяемого при п = 2 абсолютно аналогично. А именно, величиной х(Кп) называют минимальное число цветов, достаточное для того, чтобы раскрасить так, что никакие две точки на единичном расстоянии не оказались бы покрашены в один и тот же цвет.

Случай п =1 тривиален: доказательство точного равенства х(^) = 2 можно найти, например, в [1]. Однако зазор между наилучшей известной нижней и верхней оценками очень быстро возрастает с ростом п. Например, при п = 3 наилучшие из известных на сегодняшний день оценок (см. [3], [4]) таковы:

6 < х(К3) < 15. (2)

При растущем п доказано, что хроматическое число х(^п) возрастает экспоненциально быстро. А именно, при п ^ то справедливы неравенства:

(1.239... + о(1))п < х (Мп) < (3 + о(1))п .

(3)

Верхняя оценка получена в 1972 году Ларманом и Роджерсом (см. [10]—[12]), а нижняя — в 2000 году Райгородским в [13].

Для обоснования верхних оценок, аналогичных оценкам из (1)-(3), обычно приводят явную раскраску пространства Кп в требуемое число цветов. А вот для обоснования нижних оценок используются дистанционные графы. Граф О = (V, Е), множество V вершин которого является подмножеством пространства Кп, называется дистанционным, если длины всех его ребер равны друг другу. Нетрудно видеть, что для любого дистанционного графа О, вложенного в пространство Кп, верно неравенство

где хроматическое число х (О) графа О определяется как минимальное число цветов, в которые можно раскрасить вершины графа так, чтобы никакие две смежные вершины не оказались бы покрашены в один и тот же цвет. Отметим, что теорема де Брейна—Эрдеша гарантирует существование конечного дистанционного графа О, для которого неравенство (4) обращается в равенство (см. [14], [15]).

Первой работой, где этот подход был реализован в общем виде, а не только при конкретных значениях параметра п, стала работа Райского [16], в которой в качестве исследуемого дистанционного графа был выбран некоторый аналог веретена Мозера (см., например, [1]), состоящий из четырех особым образом соединенных между собой правильных п—мерных симплексов. Этот подход позволил получить линейную по п оценку

В уже упомянутой работе [10] Ларман и Роджерс предложили использовать в данной задаче совершенно иной тип дистанционных графов. Пусть даны натуральные числа п > к > Ь > 0. Дистанционный граф О(п,к,Ь) = (V(п,к),Е(п,к,Ь)) определяется следующим образом. Его вершинами являются все точки п—мерного пространства такие, что ровно к их координат равны единице, а остальные — нулю; ребро соединяет две вершины тогда и только тогда, когда они имеют ровно Ь общих единичных координат. Более

х т > х (о) ,

(4)

х (кп) > п + 2.

формально,

V (п,к) = | V = (^х, ... е : V г V* е {0,1} и ^ vг = к | ,

Г п ]

Е(п, к, £) = < {V, ш} : V, ш е V(п, к) и ^^ = О .

Пусть а (С) — число независимости графа С, то есть размер наибольшего подмножества его вершин, не содержащего внутри себя ни одного ребра графа С. В силу классического неравенства

х(С) > ¿Су, (5)

для получения нижних оценок на хроматическое число х (^п) с помощью неравенства (4) и дистанционных графов С(п, к, £) достаточно научиться оценивать сверху числа независимости последних.

Воспользовавшись уже известной на тот момент теоремой Надя, утверждающей, что а(С(п, 3,1)) < п, Ларман и Роджерс доказали (см. [10]), что

2 п2

х (Жп) > У + о(п2).

Впоследствии, рассмотрев графы С(п, 5, 2), Ларману удалось доказать, что с некоторой константой с > 0 справедливо даже более сильное неравенство

X (Кп) > сп3 + о(п3).

Первую экспоненциально растущую нижнюю оценку хроматического числа удалось получить Франклу и Уилсону в 1981 году в работе [17] с помощью разработанного ими линейно-алгебраического метода. Пусть к = кп +

1 2

ные константы. При всех 0 < у < х определим функцию

о(п), £ = тп + в(п) при п ^ то, где 0 < т < к < 1 — некоторые фиксирован-

сХ = , ХХ ,-. (6)

х у У (х - у)х—У х у

Франкл и Уилсон доказали, что если величина к—£ является простым числом, то при п ^ то и дополнительном условии 2т < к справедливо неравенство

а(С(п, к, £)) < (с?-т + о(1))п .

Забегая вперед, отметим, что в работах [18],[19] была показана асимптотическая неулучшаемость последнего неравенства. В работе [17] Франкл и Уилсон получили также и некоторую оценку а(О(п, к,Ь)) и в случае 2т > к, однако этот их результат оказался не оптимальным и был усилен в работах [20], [21] Пономаренко и Райгородским. Полученный ими результат имеет довольно громоздкую формулировку, так что мы даем ее только во второй главе настоящей работы, когда она понадобится нам по существу. Вопрос об оптимальности результатов работ [20], [21] является открытым.

Положив значения вспомогательных параметров равными к = т2, т = 2—-2, Франкл и Уилсон доказали, что

Наилучшая из известных на сегодняшний день асимптотическая нижняя оценка (3) была получена Райгородским за счет применения той же линейно-алгебраической техники к так называемым {—1,0,1} —графам, которые отличаются от О(п,к,Ь) графов тем, что координаты их вершин принимают значения не только 1 или 0, но и —1.

Формальное определение {—1, 0,1} —графов и множество связанных с ними результатов приведены в работах [22]—[26]. Разнообразные применения линейно-алгебраического метода к другим задачам экстремальной комбинаторике можно найти в статьях [27]—[29] и в книге [36].

Рассмотрим еще более сильное обобщение задачи о вычислении хроматического числа плоскости х(^2). Напомним, что обхватом графа называют длину его наименьшего цикла (обхват графов без циклов по определению полагается равным бесконечности). Для каждого т > 2 и каждого п > 1 мы определим величину ^то(Кп) равной максимуму хроматических чисел дистанционных графов в п—мерном евклидовом пространстве Кп с обхватом более т. Так как обхват любого графа по определению не меньше трех, то в силу уже упомянутой теоремы де Брейна-Эрдёша справедливо равенство

так что данная задача действительно является обобщением исходной.

Вопрос "существует ли дистанционный граф на плоскости с хроматическим числом 4 и без треугольников?" был задан Эрдёшем в [31]. На него был дан положительный ответ. Более того, О'Доннелл (см. [32], [33]) доказал, что

6(^п) = х(®п),

для любого к € N существует дистанционный граф на плоскости с хроматическим числом 4 и с обхватом более т, доказав тем самым, что £т(К2) > 4 при всех т > 2. В упомянутой выше недавней работе [2] было показано, что £2(М2) = х(К2) > 5. Вопрос о том, при каких т > 2 справедливо неравенство £т(К2) > 5, остается открытым.

Задача о поведении величины £т(Кп) при фиксированном т и растущем п была поставлена в работе [34], в которой, среди прочего, было доказано неожиданное на первый взгляд неравенство

при п ^ то. Данное неравенство показывает, что экспоненциального по п роста хроматического числа дистанционных графов в Кп можно добиться даже ограничившись только рассмотрением дистанционных графов без треугольников. Более сильную гипотезу об экспоненциальном по п росте величины £т(Шп) в работе [34] не удалось доказать ни при каком фиксированном т > 3.

В работе [35] Купавский представил неявное решение данной проблемы. Ему удалось доказать, что для каждого фиксированного значения т > 2 существует некоторое ст > 1 такое, что

при п ^ то. Пусть £т — точная верхняя грань констант ст, для которых справедливо неравенство (7). Конкретных нижних оценок, отделяющих величины £т от единицы, в работе [35] представлено не было.

Отметим также, что близкие вопросы о хроматических числах дистанционных графов без больших клик рассматривались в работах [36]—[40].

Оригинальная задача Нельсона о нахождении хроматического числа плоскости х(К2) допускает и другие обобщения. Например, в рамках евклидовой теории Рамсея (см. [41]—[47]) изучается ситуация, когда "запрещается" одноцветность не просто пары точек на единичном расстоянии, а некоторой другой, более сложной конфигурации. Приведем формальное определение.

Пусть М С ^ — некоторое фиксированное множество. Хроматическим числом х(Кп; М) пространства Кп с запрещенным подмножеством М мы назовем минимальное число цветов, которых достаточно для того, чтобы раскрасить пространство Кп так, что никакая изометричная копия М' С Кп множества М не оказалась бы полностью одноцветной.

£т(мп) > (ст + о(1))

п

(7)

Нетрудно видеть, что данное определение действительно обобщает исходную задачу Нельсона, так как если М — пара точек на единичном расстоянии, то только что определенная нами величина х(Кп; М) в точности совпадает с х(Мп). Отметим, что в этом случае неравенство (3) гарантирует, что величина х(^п; М) экспоненциально быстро стремится к бесконечности с ростом п. Данное наблюдение мотивирует следующее определение.

Множество М С К называется (экспоненциально) рамсеевским, если величина х (Жп; М) (экспоненциально) стремится к бесконечности с ростом п. Одной из центральных проблем евклидовой теории Рамсея является задача об описании всех рамсеевских и экспоненциально рамсеевских множеств. Эта задача пока еще очень далека от своего решения. Доказано (см., например, книгу [47]), что любое рамсеевское множество М С К обязано быть конечным и сферичным (т.е. лежать на поверхности некоторой (^ — 1)—мерной сферы в Долгое время была популярна гипотеза, утверждающая, что эти два условия являются не только необходимыми, но и достаточными. В последнее время стал популярен другой, более сложный гипотетический критерий рамсеевости (см. [48]-[50]), однако для условий, накладываемых им на множество М С К^, строго не доказана ни их необходимость, ни достаточность.

Тем не менее, некоторые другие конкретные примеры расмеевских множеств, помимо уже упомянутой пары точек на единичном расстоянии, известны. В работе [51] была обоснована рамсеевость множества вершин произвольной трапеции, в [52] — правильного к—угольника, а в [53] — правильного многогранника в любой размерности. Помимо этого, очевидно, что если М1 С М2 и М2 — рамсеевское множество, то М1 — тоже, так как X (Кп; Мх) > х (Кп; М2). Кроме того, Франкл и Редль доказали в работе [54], что если М1, М2 являются рамсеевскими множествами, то таковым также является и их декартово произведение Мх х М2.

Для некоторых множеств обосновано даже более сильно свойство — их экспоненциальная рамсеевость. В работах [55], [56] Франкл и Редль показали, что этим свойством обладают множества вершин произвольных симплексов и прямоугольных параллелепипедов любой размерности. Однако, их доказательство было неявным, и даже для простейшего случая — множества А вершин равностороннего треугольника, Франкл и Редль не предъявили константу сд > 1 такую, что

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

Наибольший интерес для данной работы представляет рассмотрение ситуации, когда запрещенное множество М является множеством вершин Sd правильного мерного симплекса. Для доказательства экспоненциальной рамсеевости данных множеств Франклу и Редлю потребовалось глубоко изучить свойства графов С(п,к,£).

Пусть, как и ранее, к = кп + о(п), £ = тп + о(п) при п ^ то, где 0 <т<к < 1 — некоторые фиксированные константы, а величина к — £ является простым числом. Нетрудно видеть, что из верхней оценки Франкла и Уилсона на число независимости а(С(п, к, £)) следует существование такого достаточно маленького положительного числа 6, что любое подмножество W вершин графа С(п, к,£) мощности хотя бы (1 — 6)п IV(п, к)| содержит внутри себя хотя бы одно ребро.

В работе [55] Франклу и Редлю удалось доказать справедливость более сильного утверждения, гарантирующее попадание "почти всех" ребер С(п,к,£) в произвольное "достаточно большое" подмножество его вершин. А именно, они доказали, что для любого £ > 0 существует 6 > 0 такое, что при всех достаточно больших п любое подмножество W вершин графа С(п, к,£) мощности хотя бы (1 — 6)п IV(п, к)| содержит внутри себя хотя бы (1 — £)п |Е(п, к, £)| ребер. Нетрудно видеть, что если для некоторых фиксированных значений параметров £, к и т утверждение теоремы Франкла и Редля справедливо при некотором 6 > 0, то оно справедливо и при всех 0 <6' <6, так что в дальнейшем в данной работе через 6(£, к,т) мы будем обозначать точную верхнюю грань значений 6, при которых теорема Франкла-Редля справедлива. Как уже было отмечено выше, результаты работы [55] были неконструктивными, так что задача отыскания явной оценки величины 6(£,к, т), вытекающей из [55], является весьма нетривиальной.

Для доказательства положительности величины 6(£, к,т) Франкл и Редль рассмотрели вспомогательную задачу экстремальной теории множеств, представляющую и самостоятельный интерес. Пусть а(п) = ап + о(п),р(п) = рп + о(п) при п ^ то, где 0 < р < а < 2 — некоторые фиксированные константы. Пусть [п] = {1, ... ,п} — стандартное п—элементное множество, а & и — две совокупности его а(п)— элементных подмножеств с запрещенным перекрестным пересечением мощности р(п) (т.е. такие, что для всех ^ е & и С е С верно, что П С| = р(п)). В работе [55] Франкл и Редль

доказали, что такие совокупности & и не могут "быть очень большими" одновременно. А именно, они доказали существование такого достаточно маленького положительного числа е, что при всех достаточно больших п справедливо неравенство | • | < (4 — 4е)п. Иначе говоря, наложение даже одного единственного запрета на мощность перекрестного пересечения сразу же экспоненциально понижает максимально возможное произведение мощностей двух совокупностей. Как и ранее, через е(а, р) в данной работе мы будем обозначать точную верхнюю грань значений е > 0, при которых справедлива данная теорема Франкла—Редля.

Отметим, что данный результат наиболее интересен в ситуации а = 2, так как при а < | существует "не так много" а(п)—элементных подмножеств, и экспоненциально понижение по сравнению с 4п обеспечивается и без запрета на мощность пересечения. Однако, в той же работе [55] было показано, что и в этой ситуации наложение одного единственного запрета на мощность перекрестного пересечения обеспечивает экспоненциальное понижение максимального возможного произведения мощностей двух совокупностей по сравнению с тем же максимумом, но без наложения запрета.

Первая попытка конкретизации определенной выше функции е(а, р) была сделана в серии работ [57]—[59], в которой был приведен некоторый алгоритм, получающий на вход значения параметров а и р и выдающий на выходе нижнюю оценку величины е(а, р). В качестве недостатков данной серии работ нам бы хотелось отметить два следующих факта. Во-первых, представленный в [57]—[59] алгоритм выдает далеко не оптимальные результаты в рамках используемого метода. Во-вторых, не был произведен асимптотический анализ данного алгоритма, который позволил бы для любой фиксированной размерности ё правильного симплекса получить явные нижние экспоненциально растущие при п ^ то оценки хроматических чисел х(Кп; Sd).

Отметим, что рассмотренные выше обобщение исходной задачи Нельсона являются далеко не единственными. Например, вместо евклидовых пространств Кп можно изучать хроматические числа других метрических пространств, наиболее естественными кандидатами на роль которых являются, пожалуй, сферы и пространства ^ = (Шп,£р) с метрикой £р (см. [60]—[69]). Помимо этого, вместо одного запрещенного монохроматического множества можно запретить одноцветность сразу нескольких конфигураций (см. [70]— [72]) или даже их бесконечного семейства (см. [73]—[77]). Однако, данные обобщения не являются предметом изучения настоящей работы.

Цель работы и основные задачи

Цель настоящей работы состоит в нахождении в явном виде нижних оценок функций е(а, р) и 6(£,к,т), а также в применении полученных результатов к двум задачам теории Рамсея. Во-первых, к задаче об отыскании явных нижних нетривиальных оценок величин <^то при к > 2. Во-вторых, к задаче о нахождении при каждом ё е N явной нижней экспоненциально растущей при п ^ то оценки хроматического числа х(КП; п—мерного евклидова пространства с запрещенным правильным одноцветным ё—мерным симплексом

Научная новизна

Все результаты, представленные в диссертации, являются новыми.

Теоретическая и практическая значимость работы

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

Методология и методы исследования

В диссертации используется линейно-алгебраический, вероятностный и другие классические методы экстремальной комбинаторики.

Положения диссертации, выносимые на защиту

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

2. Произведен асимптотический анализ как ранее известного, так и нового алгоритма получения оценок значений величины е(а, р) для случая

а = 2, р ^ 1.

3. Результаты пунктов 1 и 2 применены для нахождения явной нижней оценки величины д(е, |, |) для всех достаточно малых £ > 0.

4. Представлен новый, не зависящий от результатов пунктов 1 и 2 метод нахождения явных нижних оценок величины 6(е, к,т) при всех возможных допустимых значениях параметров.

5. Результаты пунктов 3 и 4 применены для нахождения при каждом т > 2 явной нижней нетривиальной оценки величины £т.

6. Результаты пунктов 3 и 4 применены для нахождения при каждом ё € N явной нижней экспоненциально растущей при п ^ то оценки хроматического числа х(Кп; Sd).

Степень достоверности и апробация результатов

Все результаты работы строго доказаны.

По теме диссертации были сделаны доклады на следующих научных конференциях:

— Международная конференция "European Conference on Combinatorics, Graph Theory and Applications", Вена, Австрия, 28 августа - 1 сентября, 2017

— Международная конференция "Extremal Combinatorics and Discrete Geometry", Майкоп, Россия, 19 - 23 декабря, 2018

— Международная конференция "3rd Hungarian-Russian Combinatorics workshop", Москва, Россия, 20 - 25 мая, 2019

— Международная конференция "European Conference on Combinatorics, Graph Theory and Applications", Братислава, Словакия, 26 - 30 августа, 2019

— Всероссийская конференция "Осенние математические чтения в Адыгее", Майкоп, Россия, 15 - 20 октября, 2019

Публикации

Результаты диссертации опубликованы в 10 работах, представленных в конце списка литературы. Все эти работы опубликованы в журналах, индексируемых базой Scopus и входящих в перечень ВАК. Все результаты, выносимые на защиту в данной диссертации, были получены автором диссертации самостоятельно, включая результаты, опубликованные в совместных работах.

Благодарности

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

Краткое содержание работы

Настоящая работа состоит из трех глав.

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

Вторую главу мы начнем с формулировки как классических, так и нашего нового результата о числах независимости графов С(п,к,Ь). Далее мы применим результаты первой главы для получения явных нижних оценок величины 5(е, 1, 4). Наконец, мы представим новый, альтернативный способ получения явных нижних оценок величины 5 (е, 1,1), который окажется и более сильным, и более общим по сравнению с предшествующим.

Третья глава настоящей работы разделена на две части. В первой из них мы применяем полученные в первых двух главах результаты для нахождения явных нижних оценок величины £т при всех т > 2, а во второй — величин х(Шп, Sd) при всех 1 > 2.

Глава 1

Два семейства подмножеств с запрещенным перекрестным пересечением

Пусть п, е N [п] = {1, ... , п} — стандартное п—элементное множество, а & и — две совокупности его а(п) — элементных подмножеств, где а(п) — натуральное число не превосходящее п. Очевидно, что если не накладывать на & и никаких дополнительных ограничений, то задача об отыскании максимально возможного значение величины | • | тривиальна: искомый

у-^а(п) у-^а(п)

максимум равняется Сп • Сп .

Одним из самых естественных ограничений, которые можно наложить на совокупности & и , чтобы сделать данную задачу интересной и содержательной, является ограничение на мощность перекрестного пересечения. А именно, мы дополнительно потребуем чтобы для всех ^ е & и С е было верно, что П С| = р(п), где р(п) < а(п) — некоторое фиксированное натуральное число. В работе [55] Франкл и Редль доказали, что такие совокупности & и не могут "быть очень большими" одновременно.

Дадим формальное описание данного результата. Пусть а(п) = ап + о(п), р(п) = рп + о(п) при п ^ то, где 0 < р < а < 1 — некоторые фиксированные константы. Пусть & и — две совокупности а(п)—элементных подмножеств множества [п] с запрещенным перекрестным пересечением мощности р(п). В работе [55] Франкл и Редль доказали существование такого достаточно маленького положительного числа 7, что при всех достаточно больших п справедливо неравенство | • | < (1 — 7)п • сП°П • СП(п). Таким образом, наложение даже одного единственного запрета обеспечивает экспоненциальное понижение максимально возможного значения величины | • | в данном асимптотическом случае.

Помимо этого, Франклу и Редлю удалось найти явный алгоритм, предъявляющий после завершения своей работы конкретную величину е > 0 такую, что

| • | < (4 - 4е)п (1.1)

при всех достаточно больших п. Нетрудно видеть, что если неравенство (1.1) справедливо при некотором е > 0, то оно справедливо и при всех 0 < е' < е, так что в дальнейшем в данной работе через е(а, р) мы будем обозначать точную верхнюю грань значений е, при которых неравенство (1.1) справедливо.

Задача отыскания величины е(а, р) наиболее интересна для случая а = 2, так как только в этом случае при п ^ то неравенство (1.1) гарантирует экспоненциальное понижение максимально возможного значения величины

1^7-1 \г/?\ /^а(п) /^а(п)

| • р | по сравнению с Сп • Сп .

Предложенный в работе [55] алгоритм получения нижних оценок величины е(а, р) непросто применить как к произвольным зафиксированным значениям а, р, так и для важного для приложений к теории Рамсея асимптотического случая а = 1 ,р = 1—2т, г ^ 0. Франкл и Редль не изучили результаты работы своего алгоритма для интересующих их частных значений параметров а и р, а ограничились использованием неявного результата о положительности величины е(а,р).

Настоящая глава частично устраняет данный пробел. К ее основным результатам относится теорема 2, опубликованная в работе [86] и доставляющая для малых г нижнюю оценку величины е(1 /2, (1 — г)/2), гарантированную алгоритмом Франкла-Редля, теорема 3, усиливающая данный алгоритм и опубликованная в работе [87], а также теорема 6, усиливающая результат теоремы 2 и также опубликованная в [87].

1.1 Алгоритм Франкла—Редля

Так как Франкл и Редль в статье [55] были в первую очередь заинтересованы в доказательстве неявного утверждения о том, что при всех допустимых значениях параметров а, р величина е(а, р) положительна, а не в конкретизации нижних оценок, то и возникший по ходу доказательства алгоритм получения таких оценок они не выписали в качестве отдельного самостоятельного утверждения.

В представленном в настоящем параграфе виде данный алгоритм был впервые опубликован в работе [57]. Для его формулировки нам потребуется ввести серию дополнительных обозначений.

Зафиксируем вначале произвольные параметры £1,(2 > 1.

Пусть ах,а2,в — такие положительные числа, что и а + в < 1, где а =

+ а2. Пусть 71,72 — произвольные числа из (0,а + в). Положим

дх = 1 — а — в + 71, М2 = 1 — а — в + 72,

ах = шт |а — ах — в + 71, д1} , а2 = шт |а — ах — в + 72, .

Пусть Н(•) : (0; 1) ^ (0; 1) — функция энтропии, определенная следующим образом:

Н(х) = —х х — (1 — х) 1с^2 (1 — х).

Теперь введем некоторую величину д1, которая будет определяться по-разному в зависимости от того, как соотносятся между собой уже введенные параметры.

Если ах = ^, то

д, = 22^ (^ )". Если а1 = а — а1 — в + 71 и а1 + в > "г1, то

д, = шп {22Н(Й)"', 2Н(Й)"'+Н(^, 2'2Н(^ } .

Если а1 = а — а1 — в + 71 и а1 + в < "1, то

д1 = ш,п {22Н(51Ь, 22Н(Щ*1)"■} .

Для 6 е (0; 1/2) положим

_ Тт (3 — 2-Ут — 6)

/1(6 ) =-тш-,

/2(С; а, в, 6) = а 1п (1 + 6) + в 1п /1(6) + 1п (1 — 6е),

61(^1; а, р) = вир < 6 : вир

шт (д1/4"х)

71

(1 + 6)/(6) " в = р — а1,а + в > р,/2(^1; а, в, 6) < 0 ¡> < 1 — 6С1

Определим теперь схожим образом 52(^2; а, р). А именно, пусть к = — — 2

Список литературы диссертационного исследования кандидат наук Сагдеев Арсений Алексеевич, 2021 год

Список литературы

[1] А. Сойфер, Хроматическое число плоскости: его прошлое, настоящее и будущее, Матем. просвещение, 2004, N8, 186 - 221.

[2] A.D.N.J. de Grey, The chromatic number of the plane is at least 5, Geombinatorics, 28 (2018), 18 - 31.

[3] Oren Nechushtan, On the space chromatic number, Discrete Math., 256, N1-2 (2002), 499 - 507.

[4] D. Coulson, A 15— colouring of 3—space omitting distance one, Discrete Math., 256, N1-2 (2002), 83 - 90.

[5] A.M. Raigorodskii, Combinatorial geometry and coding theory, Fundamenta Informaticae, 145, N3 (2016), 359 - 369.

[6] P. Brass, W. O. J. Moser, J. Pach, Research problems in discrete geometry, Springer Science & Business Media, 2006.

[7] A.M. Raigorodskii, Coloring distance graphs and graphs of diameters, Thirty essays on geometric graph theory, Springer, New York, NY, 2013, 429 - 460.

[8] D. Cherkashin, A. Kulikov, A. Raigorodskii, On the chromatic numbers of small-dimensional Euclidean spaces, Discrete Applied Mathematics, 243 (2018), 125 - 131.

[9] L.I. Bogoliubsky, A.M. Raigorodskii, A Remark on Lower Bounds for the Chromatic Numbers of Spaces of Small Dimension with Metrics ^1,^2, Math. Notes., 105 (2019), N2, 180 - 203.

[10] D.G. Larman, C.A. Rogers, The realization of distances within sets in Euclidean space, Mathematika, 19 (1972), 1 - 24.

[11] R. Prosanov, A new proof of the Larman-Rogers upper bound for the chromatic number of the Euclidean space, Discrete Applied Mathematics, 276 (2020), 115 - 120.

13

14

15

16

17

18

19

20

21

22

23

R.I. Prosanov, Upper Bounds for the Chromatic Numbers of Euclidean Spaces with Forbidden Ramsey Sets, Math. Notes, 103 (2018), N2, 243 - 250.

А.М. Райгородский, О хроматическом числе пространства, Успехи мат. наук, 55 (2000), N2, 147 - 148.

Bruijn, N. D., Erdos, P. (1951). A colour problem for infinite graphs and a problem in the theory of relations. Indigationes Mathematicae, 13, 371-373.

A. Soifer, The Mathematical Coloring Book, Springer, 2009.

D.E. Raiskii, Realization of all distances in a decomposition of the space Rn into n + 1 parts, Mathematical notes, 7 (1970), N3, 194 - 196.

P. Frankl, R.M. Wilson, Intersection theorems with geometric consequences, Combinatorica, 1 (1981), N4, 357 - 368.

А.В. Бобу, А.Э. Куприянов, А.М. Райгородский, О максимальном числе ребер однородного гиперграфа с одним запрещенным пересечением, Доклады РАН, 463 (2015), N1, 11 - 13.

А.В. Бобу, А.Э. Куприянов, А.М. Райгородский, Асимптотическое исследование задачи о максимальном числе ребер однородного гиперграфа с одним запрещенным пересечением, Матем. сборник, 207 (2016), N5, 17 - 42.

E.И. Пономаренко, А.М. Райгородский, Улучшение теоремы Франк-ла-Уилсона о числе ребер гиперграфа с запретами на пересечения, Доклады РАН, 453 (2014), N3, 268-269.

Е.И. Пономаренко, А.М. Райгородский, Новые оценки в задаче о числе ребер гиперграфа с запретами на пересечения, Пробл. передачи информ., 49 (2013), N4, 98 - 104.

А.М. Райгородский, Проблема Борсука и хроматические числа некоторых метрических пространств, Успехи мат. наук, 56 (2001), N1, 107 -146.

А.М. Райгородский, О хроматическом числе пространства с метрикой , УМН, 59 (2004), N5, 161 - 162.

Е.И. Пономаренко, А.М. Райгородский, Новые верхние оценки чисел независимости графов с вершинами в {-1,0,1}n и их приложения в

задачах о хроматических числах дистанционных графов, Матем. заметки, 96 (2014), N1, 138 - 147.

[25] А.Б. Купавский, Явные и вероятностные конструкции дистанционных графов с маленьким кликовым и большим хроматическим числами, Изв. РАН. Сер. матем., 78 (2014), N1, 65 - 98.

[26] P. Frankl, A. Kupavskii, Families of vectors without antipodal pairs, Studia Scientiarum Mathematicarum Hungarica, 55 (2018), N2, 231 - 237.

[27] E. Croot, V.F. Lev, P.P. Pach, Progression-free sets in Z4 are exponentially small, Annals of Mathematics (2017), 331 - 337.

[28] J.S. Ellenberg, D. Gijswijt, On large subsets of with no three-term arithmetic progression, Annals of Mathematics (2017), 339 - 343.

[29] E. Naslund, W. Sawin, Upper bounds for sunflower-free sets, Forum of Mathematics, Sigma, Vol. 5, Cambridge University Press, 2017.

[30] А.М. Райгородский, Линейно-алгебраический метод в комбинаторике, МЦНМО, Москва, 2007.

[31] P. Erdos, Unsolved problems, Congres Numerantium XV, Utilitas Math., Winnipeg, 1976.

[32] P. O'Donnell, Arbitrary girth, 4-chromatic unit distance graphs in the plane.

I. Graph embedding, Geombinatorics, 9:3 (2000), 145 - 150.

[33] P. O'Donnell, Arbitrary girth, 4-chromatic unit distance graphs in the plane.

II. Graph embedding, Geombinatorics, 9:4 (2000), 180 - 193.

[34] Е.Е. Демёхин, А.М. Райгородский, О.И. Рубанов, Дистанционные графы, имеющие большое хроматическое число и не содержащие клик или циклов заданного размера, Матем. сборник, 204 (2013), N4, 49 - 78.

[35] A.B. Kupavskiy, Distance Graphs with Large Chromatic Number and Arbitrary Girth, Moscow Journal of Combinatorics and Number Theory, 2 (2012), N2, 52 - 62.

[36] А.М. Райгородский, О дистанционных графах, имеющих большое хроматическое число, но не содержащих больших симплексов, Успехи мат. наук, 62 (2007), N6, 187 - 188.

[37] A.M. Raigorodskii, O.I. Rubanov, Small clique and large chromatic number, Electronic Notes in Discrete Mathematics, 34 (2009), 441 - 445.

[38] А.М. Райгородский, О.И. Рубанов, О дистанционных графах с большим хроматическим числом и без больших клик, Мат. заметки, 87 (2010), N3, 417 - 428.

[39] А.Б. Купавский, А.М. Райгородский, О дистанционных графах с большим хроматическим и малым кликовым числами, Доклады РАН, 444 (2012), N5, 483 - 487.

[40] А.Б. Купавский, Явные и вероятностные конструкции дистанционных графов с маленьким кликовым и большим хроматическим числами, Изв. РАН. Сер. матем., 78 (2014), N1, 65 - 98.

[41] P. Erdos, R.L. Graham, P. Montgomery, B.L. Rothschild, J. Spencer, E.G. Straus, Euclidean ramsey theorems I, Journal of Combinatorial Theory, Series A, 14 (1973), N3, 341 - 363.

[42] P. Erdos, R.L. Graham, P. Montgomery, B.L. Rothschild, J. Spencer, E.G. Straus, Euclidean ramsey theorems II, In A. Hajnal, R. Rado and V. Sos, eds., Infinite and Finite Sets I, North Holland, Amsterdam, 1975, 529 - 557.

[43] P. Erdos, R.L. Graham, P. Montgomery, B.L. Rothschild, J. Spencer, E.G. Straus, Euclidean ramsey theorems III, In A. Hajnal, R. Rado and V. Sos, eds., Infinite and Finite Sets II, North Holland, Amsterdam, 1975, 559 - 583.

[44] K. Cantwell, Edge-Ramsey Theory, Discrete Comput. Geom., 15 (1996), 341 - 352.

[45] P. Frankl, V. Rodl, Strong Ramsey properties of simplices, Israel journal of mathematics, 139 (2004), 215 - 236.

[46] P. Frankl, J. Pach, C. Reiher, V. Rodl, Borsuk and Ramsey type questions in Euclidean space, Connections in Discrete Mathematics: A Celebration of the Work of Ron Graham, 2018, 259 - 279.

[47] R.L. Graham, B.L. Rothschild, J.H. Spencer, Ramsey theory, 2nd ed., Wiley-Intersci. Ser. Discrete Math. Optim., New York, John Wiley & Sons, Inc., 1990.

[49] I. Leader, P.A. Russell, M. Walters, Transitive sets in Euclidean Ramsey theory, Journal of Combinatorial Theory, Series A, 119 (2012), N2, 382 - 396.

[50] S. Eberhard, Almost all sets of d + 2 points on the (d — 1)—sphere are not subtransitive, Mathematika, 59 (2013), N2, 267 - 268.

[51] I. Kriz, All trapezoids are Ramsey, Discrete Mathematics, 108 (1992), 59 -62.

[52] I. Kriz, Permutation groups in euclidean ramsey theory, Proceedings of the American Mathematical Society, 112 (1991), N3, 899 - 907.

[53] K. Cantwell, All regular polytopes are Ramsey, J. Combin. Theory Ser. A, 114 (2007), 555 - 562.

[54] P. Frankl, V. Rodl, All triangles are Ramsey, Trans. of Amer. Math. Soc., 297 (1986), N2, 777 - 779.

[55] P. Frankl, V. Rodl, Forbidden intersections, Trans. of Amer. Math. Soc., 300 (1987), N1, 259 - 286.

[56] P. Frankl, V. Rodl, A partition property of simplices in Euclidean space, J. of Amer. Math. Soc., 3 (1990), N1, 1 - 7.

[57] А.Е. Звонарев, А.М. Райгородский, Д.В. Самиров, А.А. Харламова, О хроматическом числе пространства с запрещенным равносторонним треугольником. Матем. сборник, 205 (2014), N9, 97 - 120.

[58] А.Е. Звонарев, А.М. Райгородский, Д.В. Самиров, А.А. Харламова, Улучшение теоремы Франкла-Рёдля о числе ребер гиперграфа с запретами на пересечения, Доклады РАН, 457 (2014), N2, 144 - 146.

[59] А.Е. Звонарёв, А.М. Райгородский, Улучшения теоремы Франкла-Рёдля о числе ребер гиперграфа с запрещенным пересечением и их следствия в задаче о хроматическом числе пространства с запрещенным равносторонним треугольником, Труды Математического Института имени В.А. Стеклова, 288 (2015), 109 - 119.

[60] M. Benda, M. Perles, Colorings of metric spaces, Geombinatorics, 9 (2000), N3, 113 - 126.

[62] A.M. Raigorodskii, On the chromatic numbers of spheres in Rn, Combinatorica, 32 (2012), N1, 111 - 123.

[63] А.Б. Купавский, О раскрасках сфер, вложенных в Rn, Математический сборник, 202 (2011), N6, 83 - 110.

[64] A. Kupavskiy, On the chromatic number of Rn with an arbitrary norm, Discrete mathematics, 311 (2011), N6, 437 - 440.

[65] И.М. Митричева, О хроматическом числе для одной серии метрических пространств, Математические заметки, 91 (2012), N3, 422 - 431.

[66] А.М. Райгородский, И.М. Шитова, О хроматических числах вещественных и рациональных пространств с вещественными или рациональными запрещенными расстояниями, Математический сборник, 199 (2008), N4, 107 - 142.

[67] А.М. Райгородский, И.М. Шитова, О хроматическом числе евклидова пространства и о проблеме Борсука, Математические заметки, 83 (2008), N4, 636-639.

[68] R. Prosanov, Chromatic numbers of spheres, Discrete Mathematics, 341 (2018), N11, 3123 - 3133.

[69] О.А. Костина, О нижних оценках хроматического числа сферы, Математические заметки, 105 (2019), N1, 18 - 31.

[70] А.В. Бердников, А.М. Райгородский, О хроматическом числе евклидова пространства с двумя запрещенными расстояниями, Математические заметки, 96 (2014), N5, 790 - 793.

[71] А.В. Бердников, Оценка хроматического числа евклидова пространства с несколькими запрещенными расстояниями, Математические заметки, 99 (2016), N5, 783 - 787.

[72] A.V. Berdnikov, Chromatic number with several forbidden distances in the space with the -metric, Journal of Mathematical Sciences, 227 (2017), N4, 395 - 401.

[73] Д.В. Самиров, А.М. Райгородский, Хроматические числа пространств с запрещенными одноцветными треугольниками, Матем. заметки, 93 (2013), N1, 134 - 143.

[74] Д.В. Самиров, А.М. Райгородский, Новые нижние оценки хроматического числа пространства с запрещенными равнобедренными треугольниками, Итоги науки и техники, Современная математика и ее приложения, 125 (2013), 252 - 268.

[75] Д.В. Самиров, А.М. Райгородский, Новые оценки в задаче о хроматическом числе пространства с запрещенными равнобедренными треугольниками, Доклады Академии Наук, 456 (2014), N3, 280 - 283.

[76] Д.В. Самиров, А.М. Райгородский, Об одной задаче, связанной с оптимальной раскраской пространства без одноцветных равнобедренных треугольников, Труды МФТИ, 7 (2015), N2, 39 - 50.

[77] А.В. Бобу, А.Э. Куприянов, Улучшение нижних оценок хроматического числа пространства с запрещенными одноцветными треугольниками, Математические заметки, 105 (2019), N3, 349 - 363.

[78] R.C. Baker, G. Harman, J. Pintz, The difference between consecutive primes. II, Proc. London Math. Soc. (3), 83 (2001), N3, 532 - 562.

[79] P. Keevash, E. Long, Frankl-Rodl-type theorems for codes and permutations, Trans. of Amer. Math. Soc., 369 (2017), 1147 - 1162.

[80] А.М. Райгородский, А.А. Сагдеев, О хроматическом числе пространства с запрещенным правильным симплексом, Доклады РАН, 472 (2017), N2, 127 - 129.

[81] А.А. Сагдеев, О нижних оценках хроматических чисел дистанционных графов с большим обхватом, Матем. заметки, 101 (2017), N3, 430 - 445.

[82] Р.И. Просанов, А.М. Райгородский, А.А. Сагдеев, Улучшения теоремы Франкла-Рёдля и геометрические следствия, Доклады РАН, 475 (2017), N2, 137 - 139.

[83] A.A. Sagdeev, On a Frankl-Rodl theorem and its geometric corollaries, Electronic Notes in Discrete Mathematics, 61 (2017), 1033 - 1037.

[84] А.А. Сагдеев, О хроматическом числе пространства с запрещенным правильным симплексом, Матем. заметки, 102 (2017), N4, 579 - 585.

[85] А.М. Райгородский, А.А. Сагдеев, Об одной оценке в экстремальной комбинаторике, Доклады РАН, 478 (2018), N3, 271 - 273.

[86] А.А. Сагдеев, О теореме Франкла-Рэдла, Известия РАН, 82 (2018), N6, 128 - 157.

[87] А.А. Сагдеев, Улучшенная теорема Франкла-Рёдля и некоторые ее геометрические следствия, Проблемы передачи информации, 54 (2018), N2, 45 - 72.

[88] A.A. Sagdeev, A.M. Raigorodskii, On a Frankl-Wilson theorem and its geometric corollaries, Acta Mathematica Universitatis Comenianae, 88 (2019), N3, 1029 - 1033.

[89] А.А. Сагдеев, Об одной теореме Франкла-Уилсона, Проблемы передачи информации, 55 (2019), N4, 86 - 106.