Экстремальные задачи теории гиперграфов и их применения в евклидовой теории Рамсея Звонарев Артем Евгеньевич

Содержание к диссертации

Введение

1 Теорема о мощности множества ребер гиперграфа с запрещенным пересечением и ее уточнения 13

1.1 Введение 13

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

1.3 Доказательство уточнения теоремы Франкла-Редля

1.3.1 Некоторые параметры 18

1.3.2 Алгоритм Франкла-Редля $1(6) 19

1.3.3 Первый случай остановки алгоритма и доказательство теоремы 2 в этом случае 21

Доказательство леммы 1 23

1.3.4 Второй случай остановки алгоритма и доказательство теоремы 2 в этом случае 24

Доказательство леммы 2 26

2 Хроматические числа пространства с запрещенными одно цветными треугольниками 28

2.1 Введение и формулировка результата 28

2.2 Описание вычислений — ручных и компьютерных, — давших следствие 1 31

Доказательство утверждения 1 31

2.3 Доказательство теоремы 3 33

2.3.1 Выбор параметров, формулировки лемм и вывод утверждения теоремы 33

2.3.2 Доказательство леммы 4 37

3 О дистанционных графах с большим хроматическим и малым кликовым числами 42

3.1 Формулировка результата 42

3.2 Доказательство теоремы 6 43

Заключение 47

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

• Доказательство уточнения теоремы Франкла-Редля
• Второй случай остановки алгоритма и доказательство теоремы 2 в этом случае
• Описание вычислений — ручных и компьютерных, — давших следствие
• Выбор параметров, формулировки лемм и вывод утверждения теоремы

Введение к работе

Актуальность темы.

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

Первоначально задачи, рассматриваемые в диссертации, появились в рамках комбинаторной геометрии. Это весьма многогранная и бурно развивающаяся часть современной комбинаторики. По-видимому, отправной точкой для ее развития послужила проблематика, обсуждавшаяся И. Кеплером и другими еще в начале XVII века. В частности, одна из задач в этой области в то время формулировалась следующим образом: каково максимальное число равных материальных шаров, которые можно приложить к равному всем им шару в евклидовом пространстве? И. Кеплер предположил, что число таких шаров 12, но полное и строгое решение этой задачи было дано лишь в 1953 году Б. Л. Ван дер Варде-ном и К. Шютте¹. Вообще, именно в XX веке комбинаторная геометрия сформировалась в самостоятельную дисциплину. С одной стороны, уже упомянутое решение задачи Кеплера поспособстваволо развитию современной теории упаковок и покрытий²'³'⁴. С другой стороны, появился ряд новых задач, которыми мотивируется наша работа и о которых мы поговорим ниже.

В 1933 году К. Борсук⁵ поставил проблему отыскания минимального числа f(n) частей меньшего диаметра, на которые можно разбить произвольное ограниченное множество в евклидовом пространстве К^га. Далее Борсук высказал гипотезу, что f(n) = п + 1. Для п = 1, 2 доказательство этого утверждения было получено самим Борсуком. А в 1955 году Эглстон⁶ доказал справедливость гипотезы в размерности п = 3 . Позднее рядом авторов были получены элементарные доказательства в этой размерности. Однако, начиная с размерности 4 доказательство гипотезы Борсука получить не удавалось. Были также предприняты попытки опровергнуть гипотезу, и в 1993 году Дж. Кан и Г. Калаи⁷ построили контрпримеры в размерностях п > 2014. Сейчас известно, что гипотеза уже не верна начиная с размерности п = 64.

Еще одна основополагающая задача комбинаторной геометрии, история которой тесно связана с историей гипотезы Борсука⁸'⁹'¹⁰'¹¹, - это задача о нахождении так называемого хроматического числа евклидова пространства. Истоки она берет еще в 1950 году, когда Э. Нельсон предложил найти минимальное количество х(^^га) цветов, в которые можно

^:К. Schutte, B.L. van der Waerden, Das Problem der dreizehn Kugeln, Mathematische Annalen, 125 (1953), 325 - 334.

²П.М. Грубер, К.Г. Леккеркеркер, Геометрия чисел, Наука, Москва, 2008.

³Дж. Касселс, Введение в геометрию чисел, Мир, Москва, 1965.

⁴Дж. Конвей, Н. Слоэн, Упаковки шаров, решетки и группы, Мир, Москва, 1990.

⁵К. Borsuk, Drei Satze uber die n-dimensionale euklidische Sphare, Fundamenta Mathematicae, 20 (1933), 177 - 190.

^eH.G. Eggleston, Covering a three-dimensional set with sets of smaller diameter, Journal of the London Mathematical Society, 30 (1955), 11 - 24.

⁷J. Kahn, G. Kalai, A counterexample to BorsukYs conjecture, Bulletin of the American Mathematical Society, 29 (1993), 60 - 62.

⁸В.Г. Болтянский, И.Ц. Гохберг, Теоремы и задачи комбинаторной геометрии, Наука, Москва, 1965.

⁹А.М. Райгородский, Вокруг, гипотезы Борсука, Современная математика, Фундаментальные направления, 23 (2007), 147- 164.

¹⁰V.G. Boltyanski, Н. Martini, P.S. Soltan, Excursions into combinatorial geometry, Universitext, Springer, Berlin, 1997.

ⁿA.M. Райгородский, Проблема Борсука, Москва, МЦНМО, 2006.

так покрасить все точки евклидова пространства Ш.^п_} чтобы между точками одного цвета не было расстояния 1. Величина х(^^га) ^и была названа хроматическим числом евклидова простанства.

За прошедшие с момента постановки задачи о хроматическом числе шестьдесят с лишним лет появились разнообразные ее обобщения. Например, рассматривались хроматические числа произвольных метрических пространств¹²'¹³'¹⁴'¹⁵'¹⁶'¹⁷'¹⁸. В частности, изучалась¹⁹'²⁰ величина x(Q^ra)? ^или хроматическое число рационального пространства. В данном случае точки берутся из пространства Q^ra, снабженного евклидовой метрикой. Также изучались хроматические числа пространств с несколькими²¹'²² (и даже бесконечно многими) запрещенными расстояниями. А именно, рассматривались величины х((Х, р),Л), где (X, р) - метрическое пространство, а множество запретов берется как некоторое подмножество Л С К₊ и

_Х((Х,р),Л) = тіп{_Х: 3V_U...,V_X W = V, U ... U V_x,

Vi Vxjel/, р(х,у)^Л}.

Еще одно естественное и важное обобщение понятия хроматического числа пространства дается в так называемой евклидовой теории Рамсея. Здесь множество S С R^d называется рамсеевским, если для любого г существует такое п₀ > d, что при каждом п > п₀ и при любой раскраске пространства К^га в г цветов найдется конгруэнтная одноцветная копия S. Можно дать то же определение и в терминах хроматических чисел. А именно, пусть xs^IR"^-) — минимальное количество цветов, в которые можно так покрасить К^га, чтобы одноцветные точки не образовывали множеств, конгруэнтных S. В этих обозначениях S рамсеевское тогда и только тогда, когда хИ^"^-) ~~^ ^ПР^{И п} ~~^ - В свете оценки (1.239... + о(1))^га < х(^^га) < (3 + о(1))^га ясно, что любое двухточечное множество S является рамсеевским и даже, как говорят, экспоненциально рамсеевским. Для многих других множеств также доказана экспоненциальная рамсеевость. Например, это сделано для множества вершин произвольного симплекса (в частности, для треугольников²³) и для декартовых произведении экспоненциально рамсеевских множеств . Однако всякий

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

¹³М. Benda, М. Perles, Colorings of metric spaces, Geombinatorics, 9 (2000), 113 - 126.

¹⁴D.R. Woodall, Distances realized by sets covering the plane, Journal of Combinatorial Theory, Series A, 14 (1973), 187- 200.

¹⁵ A.M. Raigorodskii, Coloring Distance Graphs and Graphs of Diameters, Thirty Essays on Geometric Graph Theory, J. Pach edition, Springer, 2013, 429 - 460.

^leA.M. Райгородский, О хроматических числах сфер в евклидовых пространствах, Доклады РАН, 432 (2010), N2, 174 - 177.

¹⁷А.М. Raigorodskii, On the chromatic numbers of spheres in R, Combinbatorica, 32 (2012), N1, 111 - 123.

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

¹⁹D.G. Larman, С.A. Rogers, The realization of distances within sets in Euclidean space, Mathematika, 19 (1972), 1 - 24.

²⁰Е.И. Пономаренко, A.M. Райгородский, Новая нижняя оценка хроматического числа рационального пространства, Успехи математических наук, 68 (2013), N5, 183-184.

²¹Н.Г. Мощевитин, A.M. Райгородский, О раскрасках пространства Ш^п с несколькими запрещенными расстояниями, Математические заметки, 81 (2007), N5, 733 - 744.

²²А.Б. Купавский, Хроматическое число пространства Ш^п с множеством запрещенных расстояний, Доклады РАН, 435 (2010), N6, 740 - 743.

²³Р. Frankl, V. Rodl, All triangles are Ramsey, Transactions of the American Mathematical Society, 297 (1986), N2, 777- 779.

²⁴R.L. Graham, B.L. Rothschild, J.H. Spencer, Ramsey theory, John Wily and Sons, NY, Second Edition, 1990.

раз это делается неявно, так что выписать оценку вида хИ^"^-) > (с + о(1))^га с конкретной с > 1 не представляется возможным.

Теперь расскажем о связи описанных выше задач с проблемами экстремальной комбинаторики и теорией гиперграфов. Для начала введем определение дистанционного графа. Дистанционный граф или граф расстояний - это любой граф G = (V,E), у которого

1/СК", С{{х,у}: |х-у| = а}, а > 0.

Желая подчеркнуть, что вершины графа принадлежат пространству размерности п, будем говорить об n-мерном дистанционном графе. Если \V\ < оо, то скажем явно, что граф расстояний конечный. В терминах дистанционных графов х(^"0 — ^эт0 хроматическое число графа расстояний, у которого V = К^га. А поскольку, как нетрудно видеть, х(М^га) < оо, некоторые соображения компактности показывают, что хроматическое число пространства достигается на конечном гг-мерном дистанционном графе.

Все известные экспоненциальные нижние оценки величины х(^^га) достигаются на конечных дистанционных графах с вершинами в точках решетки Ъ^п. А экспоненциальные оценки величин xs(IR^ra), вовсе основаны на множествах (0,1)-векторов в пространстве. Опишем общую идею на примере величины хИ^"^-) и графа с вершинами в {0,1}^п. Пред-пол ожим, что в каждой вершине этого графа одно и то же число единиц. В этом случае граф является дистанционным тогда и только тогда, когда для некотогого Ъ скалярное произведение его вершин (как векторов) равно Ъ. Пусть х(С) - хроматическое число графа G, то есть минимальное количество цветов, в которые так можно покрасить все вершины этого графа, что все ребра не являются одноцветными (иначе говоря, вершины, образующие ребра, покрашены в разные цвета). Пусть, далее, a(G) есть размер любого из максимальных независимых множеств вершин графа G (то есть множества вершин, в которых никакие две вершины не соединены ребром). Ясно, что x(G) ^ ыс) > ^гл,е 1^(^01 - количество вершин графа G. При этом в нашем случае a(G) - это максимальное число (0,1)-векторов, у которых попарные скалярные произведения не равны Ъ. Таким образом,

желая продолжить цепочку неравенств х(^"0 ^ x(G) ^ _а(с) > ^МЬІ Д^ЛЖНЬІ научиться оценивать сверху число независимости. Напомним, что гиперграф - это пара множеств Н = (V,E), где V = V(H) - некоторое (как правило, конечное) множество, называемое множеством вершин гиперграфа, а Е = Е(Н) - произвольная совокупность подмножеств множества V, называемых ребрами гиперграфа. Ясно, что каждому (0,1)-вектору можно сопоставить ребро гиперграфа на п вершинах: это просто множество номеров координат, на которых стоят единицы. В этих терминах a(G) - это максимальное число ребер гиперграфа, попарные пересечения которых не могут иметь мощность Ъ. Отыскание последней величины - это и есть классическая проблема экстремальной комбинаторики и теории кодирования. Здесь самые сильные до последнего времени результаты принадлежали П. Франклу и В. Редлю²⁵.

Цель работы и основные задачи. Цель работы состоит в решении следующих задач: усиление теоремы Франкла-Редля и изучение его приложений; получение новых верхних оценок произведения мощностей двух совокупностей подмножеств гг-элементного множества с запретом на "перекрестные" пересечения; получение новых нижних оценок для хроматического числа пространства с запрещенным равносторонним треугольником;

²⁵Р. Frankl, V. Rodl, Forbidden intersections, Transactions of the American Mathematical Society, 300 (1987), N1, 259 - 286.

обобщение на случай дистанционных графов классического результата П. Эрдеша²⁶ о том, что для любых к,1 существует граф G, у которого x(G) > к, g(G) > I.

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

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

Теоретическая и практическая значимость полученных результатов. Диссертация носит теоретический характер. Полученные в ней результаты дают новую информацию о рамсеевских свойствах евклидова пространства.

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

1. Существенно усилена теорема Франкла-Редля о максимуме произведения мощностей двух совокупностей подмножеств гг-элементного множества, в которых запрещены "перекрестные" пересечения.

2. Получены новые явные экспоненциальные нижние оценки величины хд(М^га), равной минимальному количеству цветов, в которые можно так покрасить К^га, чтобы одноцветные точки не образовывали множеств, конгруэнтных А, где в качестве множества А рассматривается тройка вершин равностороннего треугольника.

3. Доказана теорема о существовании дистанционных графов с хроматическим числом x(G_n) > (1.239... + 5(п))^п при 8(п) —> 0, п —> оо и без клик растущего размера.

Степень достоверности и апробация результатов. Материалы диссертации опубликованы в 4 работах, в изданиях, рекомендованных ВАК РФ [1, 2, 3, 4]. Список этих работ приведен в конце автореферата. Также результаты докладывались и получили одобрение специалистов на международной конференции "4th Polish Combinatorial Conference" в Бедлево (Польша, 2012 г.), на семинаре под руководством профессора В.Б. Алексеева, профессора А.А. Сапоженко, профессора С.А. Ложкина (ВМК МГУ, 2015 г.), а также на научных семинарах под руководством профессора A.M. Райгородского в МФТИ (кафедра дискретной математики) и в МГУ им. М.В. Ломоносова (кафедра математической статистики и случайных процессов) (2012 - 2015 г. г.). Достоверность полученных результатов подтверждается применением современных методов экстремальной комбинаторики и теории кодирования.

Структура и объем диссертации Диссертация состоит из введения, трех глав, заключения, списка условных обозначений и списка литературы. Общий объем диссертации составляет 59 страниц. Список литературы содержит 68 наименований.

Доказательство уточнения теоремы Франкла-Редля

Прежде всего заметим, что доказательство теоремы 2, будучи существенным уточнением доказательства теоремы 1 Франкла-Редля, тем не менее, во многом с ним перекликается. Поэтому мы будем часто апеллировать к работе [37] и даже к обозначениям из этой работы.

Итак, пусть фиксировано п Є N и даны гиперграфы Н = (Vn Ei), Н2 = (V12 ). У них одно и то же множество из п вершин, и нам нужно оценить произведение мощностей их множеств ребер. Поскольку п фиксировано, введем для множеств ребер новые обозначения, в которых п явно не фигурирует. А именно, заменим обозначение Е на J-, а обозначение Е% — на Q. Так и индексов меньше, и символы совпадают со своими аналогами из работы [37].

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

Кроме того, коль скоро п дано, даны и числа d — мощность каждого ребра — и / — величина запрещенного пересечения.

Напомним несколько важных обозначений из работы [37]. Пусть на одном и том же n-элементном множестве вершин X есть два множества ребер Х,У. Пусть числа /і, 1 і таковы, что 0 1\ 1 і п. Тогда запись {X,У) Є V(n, [/і,/2]) означает, что для любого ребра из А" и любого ребра из У мощность их пересечения не принадлежит отрезку [/і, І2]. При 1\ = І2 отрезок состоит из одного числа. Например, для наших множеств ребер J7, Q выполнено Далее, по х Є X определяются совокупности XQ,X\\ Х0 = X0(X) = {F Є X : x F}} Хх = Хі{х) = {F\{x}: x Є F Є X} и их аналоги Уо,Уі- Наблюдение (очевидное) со страницы 267 работы [37] состоит в том, что (#І,;УІ)ЄР(7І-І,[/І-І,/2-І]), (А о, оП 1)єР(п-1,[/1-1,/2]). Отметим, что если гиперграф (X, У) однороден, то Уо П У\ = 0. Наконец, в [37] используется обозначение I VI где под UЛ мы понимаем объединение всех ребер из совокупности X. Вернемся к нашим совокупностям J7, Q и их параметрам n, i, /. Пусть 5 Є (0,1). Опишем алгоритм 21() со страницы 268 работы [37]. Этот алгоритм преобразует исходные совокупности J-,Q в некоторые новые совокупности J7 , , и, если изначально множествам из разных совокупностей было запрещено пересекаться по / элементам, то в итоге взаимные пересечения окажутся либо большими некоторой величины, либо меньшими некоторой другой величины.

Очевидно, последние четыре величины удовлетворяют всем ограничениям, наложенным на одноименные величины из раздела 1.2, т.е. на те величины, по которым фактически берутся внутренние супремумы в определениях чисел ( i,( 2 из формулировки теоремы 2. Иными словами, (Х\,(і2і$ — положительные вещественные числа, а = «і + а2, а + /3 1. Ясно также, что если J ,Q — совокупности, полученные по завершении алгоритма, то p{F)p{G ) (1 + 5ffJ{5)p{T)p{G). В следующем параграфе мы разберем случай, когда алгоритм останавливается на 1\ = 0. В последнем параграфе разберем другой случай остановки.

Зафиксируем любое число 5[ 5\ (см. формулировку теоремы 2). Пусть vri\ — это мощность множества вершин гиперграфов J- , Q , выданных алгоритмом 2l( i) Предположим, что алгоритм завершился при 1\ = 0. Ясно, что vri\ = п — а — (3. Далее, поскольку концы интервала запрещенных пересечений (т.е. величины /і, І2) сдвигаются на 1 влево только на шагах (d) и (g), то понятно, что в текущем случае (когда по завершении алгоритма 1\ = 0) / = 6І\ + (3, откуда р (i\ + (3 при п — оо или, что то же самое, (3 р — (Х\. Разумеется, также выполнено неравенство при п — оо. Иными словами, величины а\,а, (3 связаны асимптотически теми же соотношениями, какими связаны одноименные величины из внутреннего супремума в определении числа5\. Если бы еще оказалось, что /2(0:, /3, 5[, Z\) 0 (хотя бы при больших п), то мы с уверенностью могли бы утверждать, что при больших п выполнено неравенство min(gi/4Ml) — я— !-№Г- (3) (i + WiVi) Докажем оценку /2(0;, /3, 5[, Z\) 0 в дополнительном предположении, что p{F)p{G) (1 - ( i)Zl) Действительно,

Это совокупности ребер на множестве вершин мощности гп\. Более того, как и в исходных совокупностях J- ,Q , ребра из J- пересекаются с ребрами из Q не менее чем по (3 = (Зп вершинам (поскольку в начале алгоритма правый конец интервала запретов — это / = 6L\ +(3 И ЭТОТ конец смещается на 1 только на шаге (d), т.е. а\ раз). Наконец, каждое ребро в любом из гиперграфов "с волной" имеет мощность не больше

Далее, во всех трех случаях определения величины д\ присутствует ве личина 2 V / . Соответствующая оценка доказана в работе [37] в виде теоремы 2.1 на странице 266. Там нет /ІІ, поскольку там множества вершин имеют мощности п; у нас же они суть гп\ \i\Ti, откуда и нормировка, и о(1) в основании экспоненты, фигурирующей в итоговой оценке. Осталось лишь объяснить "среднюю" оценку в случае, когда ai = а — (Х\ — /3 + 7і и 2і + /3 Y- Она тоже фактически доказана в предпоследнем неравенстве на странице 266 статьи [37]. В наших обозначениях то неравенство выглядит так:

Рассуждения очень похожи на те, которые мы провели в п. 1.3.3. Однако для большей четкости изложения их стоит повторить, т.к. есть и отличия.

Зафиксируем любое число д 2 62 (см. раздел 1.2). Пусть Ш2 — это мощность множества вершин гиперграфов J- ,Q , выданных алгоритмом 21((52). Предположим, что алгоритм завершился при/2 = та. Ясно, что Ш2 = п—а—(3. Далее, поскольку концы интервала запрещенных пересечений (т.е. величины hi h) сдвигаются на 1 влево только на шагах (d) и (g), то понятно, что в текущем случае (когда по завершении алгоритма 1 = тп) 1 — а\ = п — а — (3, откуда р —Иными словами, величины а\,а, (3 связаны асимптотически теми же соотношениями, какими связаны одноименные величины из внутреннего супремума в определении числа #2- При этом неравенство /2(0:,/3, 5 2) О справедливо при больших п ровно по тем же причинам, по каким такое же неравенство выполнялось в первом случае остановки алгоритма.

Второй случай остановки алгоритма и доказательство теоремы 2 в этом случае

Напомним определение основной величины, которой и будет в основном посвящена настоящая глава. Определение 3. %5 (МП) — минимальное количество цветов, в которые можно так покрасить Мп, чтобы одноцветные точки не образовывали множеств, конгруэнтных S. В нашем конкретном случае будем рассматривать в качестве множества S тройку вершин равностороннего треугольника. Для этого множества введем отдельное обозначение А. В своей работе [37] П. Франкл и В. Редль доказали Теорему 1 (см. раздел 1.1) в том числе, имея целью оценить %д(Мп), и в работе [37] им это удалось. Однако, было доказано лишь существование константы большей единицы в основании экспоненты. Более того, эффективного описания той константы из работы [37] получить невозможно. Нам же удалось получить явную нижнюю оценку для %д(Мп).

Перед тем как перейти к формулировке основной теоремы данной главы, сделаем несколько предположений. А именно, пусть множество 9JT состоит из всех возможных упорядоченных наборов чисел v = (г , u w v 9), удовлетво ряющих условиям

Напомним, что в теореме 2 первой главы настоящей диссертации, величина є — это функция двух аргументов, которые там обозначены а и р, то есть функция, зависящая от величины мощности ребра (d — это функция от п, имеющая асимптотику d an, а Є (0,1/2)) и от запрещенного расстояния (/ — это функция от п, имеющая асимптотику / рп, р Є (0, а)). Также введем величину сух = у,х_ у_у — для произвольных чисел х 0 и у Є (0, х), и с%, = \ при у = х и с . = 0 при у х.

В следующем разделе мы опишем вычисления, позволившие получить следствие 1. В разделе 2.3 мы докажем теорему 3. Отметим, что в статьях [47] и [48] изучено следующее хроматическое число: Ха,ь{ -п) — это минимальное количество цветов, в которые можно так покрасить точки пространства, чтобы не существовало трех точек одного цвета, служащих вершинами равнобедренного треугольника с длиной боковых сторон 1 и длиной основания в пределах от а 1 до Ь 1. Конечно, Хаф( п) Хд(1Кп)- И во многих случаях оценка из следствия 1 с учетом этого неравенства дает более сильные результаты. А именно, в работе [48] приведена следующая таблица оценок

Здесь по горизонтали стоят значения 6, по вертикали — а, а в клетках — константы в основаниях экспоненциальных нижних оценок величины Ха,ъ0 -п)-Видно, что улучшения возникают при Ь = 1.1, а 0.03, при Ь = 1.15, а 0.12, при Ъ = 1.2, а 0.18, при Ъ = 1.25, а 0.24, при Ъ = 1.3, а 0.3, при Ъ = 1.35, а 0.36, при Ъ = 1.4, а 0.4. Это связано с тем, что результаты работ [47], [48] получены принципиально иным методом, и наличие нового подхода, данного в теореме 3, позволяет серьезно продвинуться в задаче при тех параметрах, где старый метод давал слабые результаты.

В свете утверждения 1 перебор идет без каких-либо дополнительных тонкостей. Для поиска 5\ параметрами внешних циклов перебора служат 5 и «і, (І2- Величина 5 берется с шагом 0.001, а величины а\, а — с шагами 0.01. По ним на каждой итерации вычисляется (3 = р — (Х\ и сразу проверяется условие f2(ot,(3,5) 0. Если условие не выполнено, осуществляется переход к новой итерации. Иначе считается значение

Теперь обратимся к следствию 1. В теореме 3 идет максимизация по (г, v) Є Т. Экспериментально (в серии запусков с невысокой точностью) было установлено, что достаточно брать г Є (0, 2). После этой локализации г перебирались с шагом 0.0001. При фиксированном г значения остальных параметров также выбирались в циклах: и, v и w с шагом 0.001; v , 9 с шагом 0.01. Когда все параметры были фиксированы, находилось

Вычисления осуществлялись на кластере Яндекса. Задача была разделена на 10000 частей, обработка которых велась параллельно. Весь расчет занял трое суток. За большое участие в этой работе автор благодарит В.А. Кошелева, исследователя и руководителя группы в отделе теоретических и прикладных исследований Яндекса.

Несмотря на то, что вычисления велись на кластере, итоговый результат можно при желании проверить и на обычном персональном компьютере, и даже на калькуляторе. Для этого достаточно знать лишь те значения вспомогательных параметров из формулировки теоремы 2, которые отвечают за величину є для приведенных выше r,v,u, v\ 9. Вот они: Si = mm{(Si)Zl, (52)Z2} = 0.99, ах = 0.04, а2 = 0.02, (3 = 0.236074, 7i = 0.29. Теоретически, при повышении точности перебора, можно найти и больше десятичных знаков для оптимальных параметров. Однако это может привести лишь к увеличению є и улучшению итоговой оценки, которая сейчас имеет величину 1.052.

Описание вычислений — ручных и компьютерных, — давших следствие

Обзор полученных результатов и перспективные направления дальнейших исследований В настоящей диссертации исследован ряд вопросов, находящихся на стыке нескольких областей науки. В главе 1 в рамках теории экстремальных задач о раскрасках гиперграфов нам удалось существенно уточнить классический результат П. Франкла и В. Редля (Теорема 1) и, более того, получить новые верхние оценки произведения мощностей двух совокупностей подмножеств n-элементного множества с запретом на "перекрестные" пересечения. В главе 2 мы получили новые оценки хроматического числа пространства с запрещенным равносторонним треугольником, применив результат первой главы и используя принципиально новый подход, описанный в теореме 3. Тем самым удалось серьезно продвинуться в задаче, где старый подход, часто используемый при решении задач в области экстремальной комбинаторики и евклидовой теории рамсея, давал слабые результаты. И, наконец, в главе 3, используя вероятностный метод, удалось доказать аналог классического утверждения П. Эрдеша для случая дистанционных графов.

Существует много различных направлений дальнейших исследований. Во-первых, если говорить о результатах, полученных в главе 1, то можно сформулировать аналоги доказанных утверждений для случая, когда гиперграфы П\- и -однородные. Во-вторых, можно попытаться перенести технику, используемую при доказательстве теоремы 2, на случай произвольных треугольников с заданными длинами сторон. И, наконец, можно перейти от запретов на треугольники к запретам на симплексы, а также другие более сложные конфигурации, расположенные на сферах. Кроме того, результаты теорем 1 и 2 возможно допускают дальнейшие уточнения, но они возникнут, если справедлива некоторая гипотеза. Вот о ней и о том, что может получиться, поговорим далее. Гипотеза о произведении мощностей множеств ребер гиперграфов в случае, когда мощности перекрестных пересечений ограничены снизу

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

Эта гипотеза доказана в случае, когда Н\ и Hz совпадают, т.е. в случае, когда дан один гиперграф и его ребра имеют достаточно большие попарные пересечения (см. [54]-[58]). Для случая, когда гиперграфы по существу различны, имеется ряд работ, частично решающих проблему (см. [59] [61]).

Модификация теоремы 2 Ввиду гипотезы 1 можно модифицировать алгоритм выбора необходимых параметров для теоремы 2 следующим образом. Как и перед формулировкой теоремы 2, зафиксируем числа Предположим, что верна гипотеза 1. Найдем величины5\}52 с помотаю алгоритма, описанного перед формулировкой теоремы. Пусть є = minj i, }. Тогда существует функция (р натурального аргумента п, принимаются, возможно, как положительные, так и отрицательные значения и стре-мяищяся к нулю при п — о, с которой имеет место следуюгцее утверждение. Пусть d и I — функции натурального аргумента п, принимаюгцие натуральные значения и при имеющие асимптотики d(n) an, 1(п) рп. Пусть, кроме того, Щ = (Vn, Ef), Щ = (Vn, EQ) — две последовательности d(n)-однородных гиперграфов, в которых для каждого п множество вершин Vn одно и то же и \Vn\ = п, причем для любых F\ Є Е, F i Є Е% выполнено \F\ П F2 7 Кп) (множества ребер Е Е могут как пересекаться, так и не пересекаться). Тогда

Теперь сравним результаты теоремы 2 и 6. В главе 1 мы говорили о том единственном случае, где П. Франкл и В. Редль конкретизировали свою оценку из работы [37], то есть когда а = 0.5 и р = 0.25. У них получилось число 3.96, и, как мы описали далее в главе 1, теорема 2 дает более сильный результат, а именно оценку 3.892. Проведя аналогичные вычисления для теоремы 6, нами была получена оценка 3.87, что, конечно, еще лучше. Вычисления констант в теореме 6 намного более трудоемкие, поэтому мы пока ограничились случаем когда а = 0.5 и р = 0.25.

Как и у теоремы 2, так и у теоремы 6 есть следствие. Справедливо Следствие 2. Если верна гипотеза 1, то имеет место оценка Хд(Мп) (1.06... + О(1))п. Понятно, что следствие 2 сильнее следствия 1 из теоремы 2. Описание вычислений, давших следствие, похоже на приведенные выше, и здесь мы его не повторяем. В следующем разделе мы приведем схему доказательства теоремы бив конце рассмотрим ряд ситуаций, в которых все перевисленные теоремы допускают уточнения.

Схема доказательства теоремы 6

Доказательство теоремы 6 очень похоже на доказательство теоремы 2, подробно изложенное в первой главе настоящей диссертации. Поясним, в чем состоят различия. В разделе 1.3.2 был описан алгоритм, который по исходным гиперграфам Т = Н, Q = Щ строит новые гиперграфы J7 , Q . У алгоритма есть два варианта остановки.

В первом случае гиперграфы J- , Q обладают следующими параметрами. Их общее множество вершин имеет мощность /ІІП± j\ (п), где j\ — функция, стремящаяся к нулю при п —Ребра каждого из них содержат не более а\П ± /г( ) вершин, где /2 — функция, аналогичная j\. При этом мощность пересечения любого ребра из J- и любого ребра из Q не меньше (Зп ± /з{п)-Нетрудно проверить с использованием формулы Стирлинга, что ввиду гипотезы 1

Ровно такую же роль играла в этом случае и величина д\ из алгоритма 1. Дальнейшие рассуждения повторяют рассуждения из доказательства теоремы 2.

Во втором случае остановки алгоритма гиперграфы J7 , Q обладают иными параметрами. Их общее множество вершин имеет мощность Ц2П ± h\(n), где h\ — функция, стремящаяся к нулю при п — оо. Ребра каждого из них содержат не более а п ± h iji) вершин, где h — функция, аналогичная h\.

Выбор параметров, формулировки лемм и вывод утверждения теоремы

В свете утверждения 1 перебор идет без каких-либо дополнительных тонкостей. Для поиска 5\ параметрами внешних циклов перебора служат 5 и «і, (І2- Величина 5 берется с шагом 0.001, а величины а\, а — с шагами 0.01. По ним на каждой итерации вычисляется (3 = р — (Х\ и сразу проверяется условие f2(ot,(3,5) 0. Если условие не выполнено, осуществляется переход к новой итерации. Иначе считается значение

Аналогично считается , только здесь есть еще цикл по Л с шагом 0.01. Теперь обратимся к следствию 1. В теореме 3 идет максимизация по (г, v) Є Т. Экспериментально (в серии запусков с невысокой точностью) было установлено, что достаточно брать г Є (0, 2). После этой локализации г перебирались с шагом 0.0001. При фиксированном г значения остальных параметров также выбирались в циклах: и, v и w с шагом 0.001; v , 9 с шагом 0.01. Когда все параметры были фиксированы, находилось

Вычисления осуществлялись на кластере Яндекса. Задача была разделена на 10000 частей, обработка которых велась параллельно. Весь расчет занял трое суток. За большое участие в этой работе автор благодарит В.А. Кошелева, исследователя и руководителя группы в отделе теоретических и прикладных исследований Яндекса.

Несмотря на то, что вычисления велись на кластере, итоговый результат можно при желании проверить и на обычном персональном компьютере, и даже на калькуляторе. Для этого достаточно знать лишь те значения вспомогательных параметров из формулировки теоремы 2, которые отвечают за величину є для приведенных выше r,v,u, v\ 9. Вот они: Si = mm{(Si)Zl, (52)Z2} = 0.99, ах = 0.04, а2 = 0.02, (3 = 0.236074, 7i = 0.29. Теоретически, при повышении точности перебора, можно найти и больше десятичных знаков для оптимальных параметров. Однако это может привести лишь к увеличению є и улучшению итоговой оценки, которая сейчас имеет величину 1.052.

Пусть, далее, Pi — это минимальное простое число, с которым v := v—pi v n — 2. Известные результаты аналитической теории чисел (см. [49] и [50]) говорят о том, что существует такая функция / вещественного аргумента х, что f(x) = о(х) при х — оо и для любого х 1 на отрезке [ж, х + f(x)} есть простое число. Это значит, что v г п. Положим Пара Gn = (уп,Еп) — это так называемый дистанционный граф. У этого графа вершины — точки пространства, а ребра — отрезки данной длины.

Лемма 3. Если множество точек W С Vn таково, что \W\ тп, то существует треугольник с вершинами eW и ребрами из Еп. Лемму 3 мы докажем позже, а пока выведем из нее теорему 3. Пусть Шп покрашено в х тг цветов. Тогда и Vn покрашено в не более \ цветов. По принципу Дирихле в один из этих цветов покрашено некоторое множество точек W С Vn мощности тп. Значит, есть в W одноцветный треугольник,

В свою очередь, лемма 3 является следствием леммы 4. Для ее формулировки введем еще ряд параметров. Положим и = [ип], w = [wn]. Выберем р2 как минимальное ппростое число, с которым величина 9, определенная равенством в = w—p2i не превосходит вп — 2. Опять же, удобства заменим ввиду [49] и [50], имеем Лемма 4. Если множество точек\ С Vn таково, что \W\ тп, то число ребер графа Gn, оба конца которых находятся в W, не меньше величины Выведем из леммы 4 лемму 3. Пусть W С Vn таково, что \W\ тп. Тогда по лемме 4 в W много ребер графа Gn. Значит, хотя бы одна из вершин в W имеет степень не меньше величины Для дальнейшего наш граф на гиперграф по следующему принципу. Вершине графа, т.е. n-мерному (ОД)-вектору с v единицами, сопоставим ребро гУ-однородного гиперграфа с п вершинами. Обозначим совокупность ребер полученного гиперграфа Т = Тп- Тогда пара (Fi, F2) ребер из J- "образует ребро" (в исходном графовом смысле), если \F\ П F2I = v (мощность пересечения ребер гиперграфа J- равна скалярному произведению векторов из Vn, отвечающих этим ребрам).

В новых терминах множество W — это тоже совокупность ребер Q некоторого гиперграфа: Q С Т. И мы знаем, что одно из ребер F Є Q имеет не меньше Воспользуемся теоремами, доказанными П. Франклом-Р.М. Уилсоном в [51] и Е.И. Пономаренко в [52], [53] (см. также [12], [54]). Теорема 4 ([51]). Пусть Н = (V}E) — к-однородный гиперграф на п вершинах, причем для любых Fi F i Є Е выполнено \F\ П F z\ 7 I и к — I — степень простого числа, которую мы обозначим q. Если 21 к, то \E\ Y,Cn Теорема 5 ([52], [53]). Пусть Н = (V} Е) — к-однородный гиперграф на п вершинах, причем к ; для любых Fi F i Є Е выполнено \F\ П F i\ 7 I, 2l kuq = k — I — степень простого числа. Положим d = 21 — к + 1. Определим натуральное число г из соотношения

Назовем множество W С V вершин какого-либо графа G = (V, Е) независимым, если никакие два его элемента не соединены ребром из множества Е. Размер любого из максимальных по мощности независимых множеств в графе G обозначим через a(G) и будем говорить, что a(G) — число независимости данного графа. В определенном смысле независимые множества — это "антиклики"; именно поэтому число независимости и кликовое число принято обозначать первой и последней буквами греческого алфавита.