Раскраски пространств с запрещёнными одноцветными конфигурациями Самиров Дмитрий Вячеславович

Диссертация - 480 руб., доставка 10 минут, круглосуточно, без выходных и праздников

Автореферат - бесплатно, доставка 10 минут, круглосуточно, без выходных и праздников

Самиров Дмитрий Вячеславович. Раскраски пространств с запрещёнными одноцветными конфигурациями: диссертация ... кандидата физико-математических наук: 01.01.09 / Самиров Дмитрий Вячеславович;[Место защиты: Московский физико-технический институт (государственный университет)].- Москва, 2015.- 62 с.

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

Введение

1 Нижние оценки хроматического числа пространства с запрещенными одноцветными треугольниками 12

1.1 Формулировка основной теоремы и численные результаты 12

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

1 1.2.1 Схема доказательства 14

1.2.2 Построение множествам 15

Построение совокупности Л 15

Построение совокупности В 16

Построение множества векторов 18

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

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

1.2.5 Небольшое замечание 21

2 Усиление нижних оценок хроматического числа пространства с запрещенными одноцветными треугольниками 23

2.1 Формулировки результатов 24

2.2 Сопоставление оценок из теорем 1, 3, 4 26

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

3 2.3.1 Структура доказательства 30

2.3.2 Построение объемлющей совокупности и выбор параметров 31

2.3.3 Построение совокупности Л 32

2.3.4 Построение совокупности М 32

2.3.5 Лемма о мощностях подмножеств множества М Доказательство леммы 34

2.4 Доказательство теоремы 4 35

3 Нижние оценки хроматического числа пространства с запрещенным множеством одноцветных треугольников 38

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

3.2 Доказательство теоремы 5 49

Доказательство леммы 5 50

Заключение 53

Список условных обозначений 55

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

Схема доказательства
Завершение доказательства
Построение объемлющей совокупности и выбор параметров
Лемма о мощностях подмножеств множества М Доказательство леммы

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

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

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

С точки зрения комбинаторной геометрии центральными являются задачи, в которых изучаются комбинаторные свойства геометрических объектов и их взаимных расположений. Именно поэтому комбинаторная геометрия берет свое начало в XIX веке, когда Вороной, Коркин, Золотарев, Минковский и др.¹ начинают изучение разбиений евклидова пространства на многогранники². В начале XX века появятся работы Хелли³'⁴, в которых речь пойдет об отыскании условий для существования трансверсалей в семействах тел в евклидовых пространствах. Наконец, в 1933 году Борсук опубликует классическую работу⁵, из которой впоследствии вырастет современный топологический метод в комбинаторике⁶ и которая в то же время ляжет в основу целого ряда активно изучаемых проблем в комбинаторной геометрии. Разумеется, первая из этих проблем носит имя самого Бор-сука, и состоит она в отыскании минимального числа частей f(n) меньшего диаметра, на которые может быть разбито произвольное множество диаметра 1 в гг-мерном евклидовом пространстве. Этой проблеме посвящено гигантское количество исследований, и ее до сих пор нельзя считать полностью решенной⁷'⁸'⁹.

Вторая по времени возникновения, но не менее важная по сути проблема восходит к Хадвигеру¹⁰. Однако в современном своем виде она была сформулирована в 1950 году Нелсоном, который задался вопросом о том, чему равно минимальное количество цветов, в которые можно так раскрасить все точки евклидовой плоскости, чтобы между точками одного цвета не было расстояния I¹¹. Вопрос сродни проблеме Борсука, ведь, если у Борсука речь идет о разбиении множеств диаметра 1 на части меньшего диаметра (т.е. на части, которые заведомо не содержат пар точек на расстоянии 1), то у Нелсона похожая задача ставится для всего пространства (плоскости). Соответственно, описанное выше минимальное число цветов принято обозначать х(^²) ^и называть хроматическим числом плоскости. Естественно, так же определяется и хроматическое число пространства %(К.^та). Проблема отыскания этого числа носит сейчас название проблемы Нелсона-Хадвигера или даже Нелсона-Эрдеша-Хадвигера. В последнем случае отмечается колоссальная роль, которую сыграл замечательный венгерский комбинаторщик Эрдеш в популяризации задачи. Сейчас работам по проблеме Нелсона-Хадвигера посвящено едва ли не больше публика-

¹Г.Ф. Вороной, Собрание сочинений Т. 1 - 3, Киев, 1952 - 1953.

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

³Л. Данцер, Б. Грюнбаум, В. Кли, Теорема Хелли, Москва, "Мир", 1968.

⁴Г. Хадвигер, Г. Дебруннер, Комбинаторная геометрия плоскости, Москва, "Наука", 1965.

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

⁶J. Matousek, Using the Borsuk - Ulam theorem, Universitext, Springer, Berlin, 2003.

⁷A.M. Raigorodskii, Cliques and cycles in distance graphs and graphs of diameters, "Discrete Geometry and Algebraic Combinatorics", AMS, Contemporary Mathematics, 625 (2014), 93 - 109.

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

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

¹⁰Н. Hadwiger, Ein Uberdeckungssatz fur den Euklidischen Raum, Portugaliae Math., 4 (1944), 140 - 144. ⁿA. Soifer, The Mathematical Coloring Book, Springer, 2009.

ций, чем работам по проблеме Борсука¹²'¹³'¹.

Тот факт, что проблема Нелсона-Хадвигера столь популярна, связан, конечно, отнюдь не только с харизмой Эрдеша и других замечательных популяризаторов. Дело, скорее, в том, что, как мы уже говорили, проблема оказалась на стыке целого ряда важнейших дисциплин, которые активно развивались и продолжают развиваться благодаря собственной исключительной значимости. Ниже мы поговорим об этих дисциплинах.

Прежде всего проблема Нелсона-Хадвигера тесно связана с классической проблематикой раскраски графов¹⁵. Однако здесь идет речь не о раскрасках карт, а о раскрасках вершин так называемых дистанционных графов. В самом деле, пусть G = (V, Е) — граф, у которого вершины — точки в W¹, а ребра — пары точек, отстоящих друг от друга на расстояние 1. Пусть, далее, хроматическое число графа — это, как обычно, наименьшее количество цветов, в которые можно так раскрасить все вершины, чтобы концы любого ребра имели разные цвета. Обозначим x(G) хроматическое число графа G. Понятно, что максимальное значение хроматического числа дистанционного графа — это и есть хроматическое число пространства. Более того, хроматическое число пространства, будучи, как несложно показать, всегда конечным¹⁶, достигается на конечном дистанционном графе ввиду старой теоремы Эрдеша-де Брцйна¹⁷.

Родство задачи Нелсона-Хадвигера с теорией гиперграфов чуть менее очевидно. Дело, однако же, в том, что наиболее распространенный класс дистанционных графов, с помощью которых удается хорошо оценивать снизу хроматические числа пространств, состоит из графов, вершины которых суть вершины булева куба, т.е. (ОД)-векторы. В свою очередь, расстояния между векторами задаются их скалярными произведениями, которые для (ОД)-векторов однозначно соответствуют количествам общих единиц у этих векторов. Иными словами, вершины таких дистанционных графов разумно интерпретировать как ребра гиперграфа, у которого п вершин (если речь шла про Е^га), а ребра имеют такие мощности, сколько единиц было в соответствующих вершинах исходного дистанционного графа. В этом случае задача об отыскании максимально большого числа вершин дистанционного графа, которые можно покрасить в один цвет (такое число называется числом независимости графа, а множества одноцветных вершин — это независимые множества), — это задача о наибольшем числе ребер в гиперграфе с одним запрещенным пересечением. А это задача классическая¹⁸'¹⁹.

Из предыдущего абзаца очевидно, что проблема Нелсона-Хадвигера имеет тесную связь и с теорией кодирования. А именно, в терминах последней число независимости дистанционного графа с вершинами в точках целочисленной решетки с координатами, имеющими право принадлежать заданному наперед множеству целых чисел, — это код с

одним запрещенным расстоянием '.

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

¹³P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, Springer, 2005.

¹⁴P.K. Agarwal, J. Pach, Combinatorial geometry, John Wiley and Sons Inc., New York, 1995.

¹⁵Ф. Харари, Теория графов, Москва, "Мир", 1973.

¹⁶А.М. Райгородский, Хроматические числа, Второе издание, МЦНМО, Москва, Россия, 2014.

¹⁷N.G. de Bruijn, P. Erdos, A colour problem for infinite graphs and a problem in the theory of relations, Proc. Koninkl. Nederl. Acad. Wet., Ser. A, 54 (1951), N5, 371 - 373.

¹⁸P. Frankl, V. Rodl, Forbidden intersections, Trans. Amer. Math. Soc, 300 (1987), N1, 259 - 286.

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

²⁰Ф.Дж. Мак-Вильяме, Н.Дж.А. Слоэн, Теория кодов, исправляющих ошибки, М.: Радио и связь, 1979.

²¹L. Bassalygo, G. Cohen, G. Zemor, Codes with forbidden distances, Discrete Mathematics, 213 (2000), 3 -

Наконец, теория Рамсея, если говорить совсем общо, — это наука о том, что при любом разбиении на несколько частей достаточно большого множества объектов найдется элемент разбиения, содержащий некоторую наперед заданную структуру²²: полного хаоса в очень больших системах не бывает. Так, классические рамсеевские теоремы утверждают, что для любого к при любой раскраске ребер достаточно большого полного графа в два цвета найдется полный подграф на к вершинах, у которого все ребра одного цвета²³, что при любой раскраске множества натуральных чисел в конечное число цветов найдутся сколь угодно длинные одноцветные арифметические прогрессии²⁴, и т.д. В этом ключе утверждение о том, что хроматическое число пространства стремится к бесконечности (очевидно, что х(^^га) ^ ії + 1, ведь вершины правильного гг-мерного симплекса необходимо красить в разные цвета), также является рамсеевским, ведь его можно переформулировать следующим образом: для любого г найдется такое щ, что при всех п > щ и при любой раскраске точек К^га в г цветов найдутся две точки на расстоянии 1, покрашенные в один и тот же цвет.

Из приведенной выше интерпретации возникла целая наука, которая называется евклидова теория Рамсея. Задача этой науки охарактеризовать множества точек, обладающих тем же свойством, что и пары точек на расстоянии 1: множество S рамсеевское, если для любого г найдется такое щ, что при всех п > щ и при любой раскраске точек К^га в г цветов найдется множество точек одного и того же цвета, конгруэнтное множеству S. Одна из самых трудных проблем здесь — доказательство или опровержение гипотезы о том, что S рамсеевское тогда и только тогда, когда S лежит на сфере. Гипотеза доказана только для симплексов (в частности, для треугольников)²⁵'²⁶, для декартовых произведений рамсеевских множеств и еще для буквально нескольких специальных классов. Но даже для тех классов, для которых гипотеза доказана, очень трудны оценки соответствующих хроматических чисел.

Настоящая работа посвящена получению оценок указанного типа в случае раскрасок пространств с запрещенными одноцветными равнобедренными треугольниками.

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

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

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

Теоретическая и практическая значимость полученных результатов. Диссер-

11.

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

²³F.P. Ramsey, On a problem of formal logic, Proc. London Math. Soc. Ser. 2, 30 (1930), 264 - 286.

²⁴А.Я. Хинчин, Три жемчужины теории чисел, Москва, "Эдиториал УРСС", 2004.

²⁵Р. Frankl, V. Rodl, All triangles are Ramsey, Transactions of the Amer. Math. Soc, 297 (1986), N2, 777 -779.

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

тация носит теоретический характер. Полученные в ней результаты дают новую информацию о рамсеевских свойствах евклидова пространства. Эти результаты важны для теории графов и гиперграфов, теории Рамсея, теории кодирования и для комбинаторной геометрии. Они могут быть полезны специалистам Московского физико-технического института, Института проблем передачи информации им. А.А. Харкевича РАН, механико-математического факультета МГУ им. М.В. Ломоносова, факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова, Хабаровского отделения Института прикладной математики ДВО РАН и др. Они могут быть использованы при чтении обязательных и специальных курсов, связанных с дискретной математикой и теоретической информатикой.

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

1. Получены новые экспоненциальные нижние оценки величины

Ха,ь(К^га), равной наименьшему числу цветов, в которые можно так покрасить все точки К^га, чтобы никакие три точки одного цвета не являлись вершинами равнобедренного треугольника с длинами боковых сторон 1 и длиной основания в пределах от а до Ъ. Развита линейно-алгебраическая и вероятностная техника.

2. Получены новые экспоненциальные нижние оценки величины

Х_аЬ(Е^га), равной максимуму среди всех величин Ха,ь,с(^-^п), каждая из которых определяется как наименьшее число цветов, в которые можно так покрасить все точки К^га, чтобы никакие три точки одного цвета не являлись вершинами равнобедренного треугольника с длинами боковых сторон с и длиной основания в пределах от а до Ъ.

3. Результаты предыдущего пункта перенесены на случай, когда максимизируются ве
личины Ха,ь,с₁,...,сі(^^п), каждая из которых определяется как наименьшее число цве
тов, в которые можно так покрасить все точки К^га, чтобы никакие три точки одного
цвета не являлись вершинами равнобедренного треугольника с длинами боковых
сторон Сі и длиной основания в пределах от а до Ъ.

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

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

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

Наконец, теория Рамсея, если говорить совсем общо, — это наука о том, что при любом разбиении на несколько частей достаточно большого множества объектов найдется элемент разбиения, содержащий некоторую наперед заданную структуру (см. [25]): полного хаоса в очень больших системах не бывает. Так, классические рамсеевские теоремы утверждают, что для любого к при любой раскраске ребер достаточно большого полного графа в два цвета найдется полный подграф на к вершинах, у которого все ребра одного цвета (см. [26]), что при любой раскраске множества натуральных чисел в конечное число цветов найдутся сколь угодно длинные одноцветные арифметические прогрессии (см. [27]), и т.д. В этом ключе утверждение о том, что хроматическое число пространства стремится к бесконечности (очевидно, что Х(КП) п + 1, ведь вершины правильного n-мерного симплекса необходимо красить в разные цвета), также является рамсеевским, ведь его можно переформулировать следующим образом: для любого г найдется такое По, что при всех п щ и при любой раскраске точек Шп в г цветов найдутся две точки на расстоянии 1, покрашенные в один и тот же цвет.

Из приведенной выше интерпретации возникла целая наука, которая называется евклидова теория Рамсея. Задача этой науки охарактеризовать множества точек, обладающих тем же свойством, что и пары точек на расстоянии 1: множество S рамсеевское, если для любого г найдется такое щ, что при всех п щ и при любой раскраске точек Шп в г цветов найдется множество точек одного и того же цвета, конгруэнтное множеству S. Одна из самых трудных проблем здесь — доказательство или опровержение гипотезы о том, что S рамсеевское тогда и только тогда, когда S лежит на сфере. Гипотеза доказана только для симплексов (в частности, для треугольников) (см. [28], [29]), для декартовых произведений рамсеевских множеств и еще для буквально нескольких специальных классов. Но даже для тех классов, для которых гипотеза доказана, очень трудны оценки соответствующих хроматических чисел.

Вернемся к проблеме Нелсона-Хадвигера. Задача о раскраске метрического пространства — это одна из самых важных и в то же время многогранных задач современной комбинаторной геометрии. С подробностями ее истории можно ознакомиться по обзорам и книгам [7]-[9], [14] [17]. Ниже мы расскажем лишь о тех моментах, которые непосредственно важны для нашего исследования.

Итак, впервые задача о раскраске пространства была предложена Нелсо-ном и Хадвигером в середине XX века (см. [13], [14]). Тогда речь зашла об отыскании хроматического числа пространства Мп, обозначаемого х(Кп) и равного минимальному количеству цветов, в которые можно так покрасить все точки евклидова пространства, чтобы между точками одного цвета не было расстояния 1:

Множество S называется рамсеевским, если \s(Жп) — оо при п — оо. Легко показать, что если множество S рамсеевское, то оно конечное и лежит на некоторой сфере (см. [26]). Обратное утверждение является открытой гипотезой, которая доказана в ряде случаев — например, для произвольных симплексов (подразумеваются множества вершин симплексов) и декартовых произведений любых рамсеевских множеств (см. [21], [26], [28], [29], [49] [51]). Для симплексов соответствующие хроматические числа растут экспоненциально, как и для двухточечных множеств, с которых начиналась вся проблематика. Правда, константы в основаниях экспонент очень близки к 1, и даже для треугольников, которые нам особенно интересны в контексте настоящей работы, наилучшая известная оценка имеет вид (см. [49]—[51])

Запрещенных одноцветных конфигураций, как и запрещенных расстояний, можно брать целое множество. В первых двух главах настоящей работы будет изучена величина Хаф( п) (при 0 а 1 6 л/2), равная минимальному количеству цветов, в которые можно так покрасить все точки евклидова пространства, чтобы никакие три точки одного цвета не образовывали равнобедренный треугольник с длинами боковых сторон 1 и длиной основания в пределах от а до Ь. Разумеется, если в данном определении единицу заменить каким-нибудь числом с, то получится некоторое новое хроматическое число %адс(Мп). В третьей главе мы рассмотрим, в частности, вопрос об отыскании величины

Наконец, пусть Ха,ь,сь...,сг( п) — это минимальное количество цветов, в которые можно так покрасить все точки евклидова пространства, чтобы никакие три точки одного цвета не образовывали равнобедренный треугольник с длинами боковых сторон q и длиной основания в пределах от а до Ь, і = 1,...,/. Положим

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

Диссертация носит теоретический характер. Полученные в ней результаты дают новую информацию о рамсеевских свойствах евклидова пространства. Эти результаты важны для теории графов и гиперграфов, теории Рамсея, теории кодирования и для комбинаторной геометрии. Они могут быть полезны специалистам Московского физико-технического института, Института проблем передачи информации им. А.А. Харкевича РАН, механико-математического факультета МГУ им. М.В. Ломоносова, факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова, Хабаровского отделения Института прикладной математики ДВО РАН и др. Они могут быть использованы при чтении обязательных и специальных курсов, связанных с дискретной математикой и теоретической информатикой.

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

В таблице 2.1 приведены численные результаты для теоремы 1. Аналогичная таблица есть и в главе 1, но здесь мы даем больший перечень оценок. По вертикали идут значения а, по горизонтали — Ь. А в клетках записаны соответствующие значения константы в основании экспоненты. Прочерк говорит о том, что в этом месте полученная константа меньше единицы.

Понятно, что если какая-то оценка получена при данном а, то и при всех меньших а та же оценка верна. Ниже мы приводим таблицу 2.3, в которой объединены результаты двух первых таблиц с учетом этого соображения. Жирным выделены те места, где видно, что за счет теорем 3 и 4 не только удалось проникнуть в новую область параметров, но и улучшить некоторые прежние оценки. На самом деле жирные числа должны быть, очевидно, в каждом столбце: старые результаты ухудшаются при движении сверху вниз, а новые константы всегда строго больше единицы. Просто для явной иллюстрации нам не хватило подробности в таблицах.

Структура доказательства будет похожа на ту, которая имела место в главе 1. Тем не менее, для большой ясности изложения мы воспроизведем и здесь. Зафиксируем параметры а, Ь и параметры к, 7 из формулировки теоремы. Нашей целью будет построение некоторой совокупности М векторов в Шп, попарные расстояния между которыми лежат в пределах от а до Ь. При этом мы добьемся того, что

В то же время нам удастся доказать, что если Q С М — любое множество, в котором нет точек на расстоянии 1 друг от друга, то с некоторой конкретной функцией 5, зависящей от п и стремящейся к нулю при п — выполнено

Нетрудно видеть, что этого хватит для доказательства теоремы. В самом деле, если то все пространство Мп, а вместе с ним и множество М можно разбить на jiT частей без равнобедренных треугольников с известными длинами сторон. Тогда в одной из частей, на которые разбито М, больше, чем 3S, элементов. Простое комбинаторное рассуждение показывает, что в этой части есть такие три точки х,у, z, что х — z = у — z = 1. Но по построению множества М эти три точки образуют запрещенный треугольник с вершинами одного цвета. Противоречие. Значит,

Дальнейшая структура доказательства такова: в параграфе 2.3.2 мы построим совокупность S, из который впоследствии будет выбираться М в качестве подсовокупности, а также введем некоторые новые параметры и проясним их связь с дальнейшим построением; в параграфе 2.3.3 мы выберем из S такую подсовокупность Л мощности (С\ + о(1))п, что в ней попарные расстояния между векторами не больше Ь; в параграфе 2.3.4 мы "проредим" совокупность Л, так что в итоге возникнет совокупность М с дополнительным нижним ограничением на попарные расстояния и с нужным количеством элементов; в параграфе 2.3.5 мы докажем лемму об оценке величины S.

Наша цель — выбрать из совокупности Е подсовокупность М, в которой попарные расстояния между элементами лежат в пределах от а до Ь. В свете всего, что было сказано выше, для этого достаточно сперва выбрать из S подсовокупность Л, в которой попарные скалярные произведения не меньше дроби 2 а затем из Л сделать М путем удаления из Л пар векторов со скалярным произведением, большим 2j При этом для удобства можно заменить Е на S = у/2дрі Е, элементы которой — просто (ОД)-векторы. Тогда в качестве Л С Т, и М С .А вполне удастся брать совокупности с нижним и верхним ограничениями а и (3 на величины скалярных произведений соответственно. Именно этим мы и займемся в следующих двух параграфах.

Разумеется, можно было выбрать Л и как-то иначе. Однако мы стремились максимизировать константу в основании экспоненты, выражающей мощность искомой совокупности, и именно ради этого мы сделали такой выбор. Тот факт, что константа С\ оптимальна, обусловлен теоремой Алсведе-Хачатряна (см. главу 1, [55], [56], [58], [59]).

Построение совокупности М Здесь мы применяем вероятностный метод, действуя практически так же, как и в главе 1. А именно, полагаем A! = {xi,... , хдг}, где А = (С\ + о(1))п, и В = 1,... }Bcs } — класс всех s-элементных подсовокупностей в Л (величину s мы позже подберем оптимальным образом). Вводим структуру "классического" вероятностного пространства на множестве В: ( В, J-, Р), где P( j) = 4- для любого j Пусть d — число неупорядоченных пар векторов из Л , у которых скалярные произведения больше (3. Пусть также (Bj) — аналогичная величина для Bj С Л . Ввиду линейности математического ожидания

Значит, существует такая совокупность Bj Є В, что (Bj) f(s). Удаляем из Bj по представителю из каждой пары векторов с "большим" скалярным произведением. Остается совокупность векторов, в которой все скалярные произведения не превосходят (3. Ее и обозначаем М .

Построение объемлющей совокупности и выбор параметров

Доказательство нашей теоремы очень близко к доказательству теоремы 3 из предыдущей главы. Однако выбор некоторых параметров будет по существу отличаться. Поэтому мы аккуратно введем необходимые обозначения и проверим, что стоящие за ними объекты обладают теми свойствами, которых хватит для ссылок на подходящие части доказательства упомянутой выше теоремы 3.

Как и в главе 2, выберем из S как можно большую по мощности подсовокупность М, в которой попарные расстояния между векторами лежат в пределах от а до Ь. В свете импликаций (3) и (4) достаточно добиться того, чтобы в известные границы попали скалярные произведения векторов из M. Но в точности такую же задачу мы решаем и в главе 2: хотя значения функций а, (3 там немного другие и величина нормировки (аналог величины t) совсем иная, однако нормировка в итоге вовсе не важна (наша задача, очевидно, равносильна задаче о построении как можно большей совокупности (0,1)-векторов, в которой каждый вектор имеет ровно [кп] единиц и скалярное произведение любых двух векторов заключено между а и (3), а все, что нужно от функций а, (3, — это то, что они имеют асимптотики (2). В результате мы гарантируем существование подсовокупности М С S с мощностью

Доказательство леммы 5. Домножим каж;дый вектор из совокупности М на t. Тогда возникнет совокупность М , состоящая из (0,1)-векторов (см. главу 2). А совокупность Q превратится в совокупность Q , в которой запрещены скалярные произведения 71 = 7i(n)? ill = li(n)- Далее, пользуемся, как и в главе 2, линейно-алгебраическим методом (см. также [54], [60], [61]). А именно, каждому вектору из совокупности Q сопоставляем некоторый полином, лежащий в пространстве размерности Pi(n)-1 г=0 и доказываем, что сопоставленные полиномы линейно независимы, откуда и следует утверждение леммы. При этом полиномы буквально такие же, как в главе 2. Но для доказательства их линейной независимости важно (см. главу 2), чтобы на отрезке от а до (3 не было тех же вычетов по модулюр\ = р\(п) что и числа 7ь 7/- Иными словами, остается проверить, что Ха,Ь,сь...,сЛ ) /7 QAT-1 Тогда и совокупность М допускает раскраску в указанное число цветов без троек точек одного цвета, образующих равнобедренный треугольник с длинами боковых сторон Q и длиной основания в пределах от а до Ь. Очевидно, найдется цвет, в который покрашены все точки из некоторой такой подсовокупности L С М, что \L\ = (/ + 2)Т2. На множестве L как на множестве вершин построим граф с ребрами / типов, соединяя две вершины ребром г-го типа, коль скоро расстояние между ними равно q. Пусть Q\ С L — максимальная по мощности подсовокупность в L, свободная от каких-либо ребер. Тогда по лемме 4 имеем \Qi\ Т . Следовательно, из каждой вершины в L\Qi идет хотя бы одно ребро в Q\. Получаем не менее (/ + 1)Т2 разных ребер. Удаляем из L совокупность Q\ и берем в оставшемся множестве максимальную по мощности совокупность Q2, свободную от ребер. Набираем еще хотя бы IT2 ребер. И так далее. Суммируя возникающую арифметическую прогрессию, получаем в итоге не менее -—ё—-Т2 ребер.Предположим теперь, что из каждой вершины в L выходят только ребра разных типов. Тогда суммарное количество ребер не превосходит величины 2 + 2)Т2. Противоречие. Значит, в L есть вершина х, из которой выходят два ребра какого-то одного г-го типа. Пусть концы этих ребер суть у, х. Тогда треугольник с вершинами x,y,z равнобедренный, причем длины его боковых сторон равны q, а длина основания лежит в пределах от а до Ь, т.к. L С М, а в М все длины находятся в этих пределах по построению. Таким образом, мы нашли одноцветный запрещенный треугольник, и это приводит нас к противоречию с исходным предположением, т.е. Х»Ась...,с,(Ж ) Л Щ - [ X +(1)J и теорема доказана. Заключение

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

В процессе построения конструкций, дающих найденные нами нижние оценки, были использованы вершины булева куба, т.е. (0,1)-векторы. Это привело к тому, что наши оценки всякий раз оказывались не большими, нежели классическая оценка Франкла-Уилсона (см. [22]) Х(ЛГ) Ц± + 0(1) j = (1.207... + 0(1))» хроматического числа пространства. В то же время наилучшая нижняя оценка хроматического числа пространства, принадлежащая A.M. Райгородско-му, основана на конструкциях из ( —1,0,1)-векторов (см. [31]). Она также экспоненциальна, но в ней константа в основании экспоненты равна 1.239...

Естественным направлением для дальнейшей деятельности является перенос разработанной в диссертации техники на случай ( —1, 0,1)-векторов. Безусловно, это сопряжено с рядом трудностей. Во-первых, для (ОД)-векторов существует теорема Франкла-Уилсона-Алсведе-Хачатряна, дающая оптимальную конструкцию, в которой попарные скалярные произведения не меньше заданной наперед величины, и мы этой конструкцией постоянно пользовались. Для ( — 1,0,1)-векторов подобной теоремы нет, хотя имеется целый ряд публикаций, в которых формулируются гипотезы о том, как должны выглядеть аналоги теоремы Франкла-Уилсона-Алсведе-Хачатряна (см. [62]-[64]). Соответственно, с одной стороны, можно было бы получить "условные результаты" в духе: "данное утверждение верно, коль скоро справедлива гипотеза..." С другой стороны, можно и попытаться доказать гипотезы. Последнее, конечно, значительно труднее.

Во-вторых, линейно-алгебраический метод для ( — 1,0,1)-векторов претерпевает существенные изменения, и это также приводит к серьезным аналитическим трудностям, которые было бы полезно преодолеть в дальнейших работах по этой тематике.

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

Лемма о мощностях подмножеств множества М Доказательство леммы

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

1. Получены новые экспоненциальные нижние оценки величины %а;ь(Мп), равной наименьшему числу цветов, в которые можно так покрасить все точки Ш.п, чтобы никакие три точки одного цвета не являлись вершинами равнобедренного треугольника с длинами боковых сторон 1 и длиной основания в пределах от а до Ь. Развита линейно-алгебраическая и вероятностная техника.

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

3. Результаты предыдущего пункта перенесены на случай, когда максимизируются величины Ха,ь,сь...,сг( п); каждая из которых определяется как наименьшее число цветов, в которые можно так покрасить все точки Шп, чтобы никакие три точки одного цвета не являлись вершинами равнобедренного треугольника с длинами боковых сторон q и длиной основания в пределах от а до Ь.

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

Благодарности. Автор признателен профессору A.M. Райгородскому за постановку задач и неоценимую помощь в работе. Глава 1 Нижние оценки хроматического числа пространства с запрещенными одноцветными треугольниками Настоящая глава посвящена нижним оценкам величины %а (Мп). Напомним ее определение. Пусть 0 а 1 & л/2- Тогда

Получается, что в пределе возникает константа из нижней оценки Франкла -Уилсона для х(Кп) (см. введение). Иными словами, мы будем работать с конструкциями, которые связаны с конструкциями из статьи [22]. Конструкции из статьи [31] (ср. введение) также можно было использовать. Однако это сопряжено со значительными трудностями, о которых мы скажем в конце работы. В следующем разделе мы докажем теорему 1. 1.2 Доказательство теоремы 1

Пусть р — наименьшее простое число такое, что выполняется неравенство [кп] —р [jn]. Известно, что такое р асимптотически ведет себя, как {к — )п (см. [52], [53]). Рассмотрим множество векторов S из Ш.п, у которых каждая координата равна либо 0, либо — =, причем ненулевых координат ровно [к,п].

Для ясности изложения мы разобьем этот параграф на три пункта. В первом пункте мы построим совокупность Л, состоящую из [кп] -элементных подмножеств множества {1,. .. , п}, для которой выполнено свойство, что мощность пересечения любых двух множеств из Л не меньше а. Во втором пункте мы выкинем часть множеств из Л так, чтобы мощность пересечения любых двух разных оставшихся множеств была меньше, чем (3. Возникнет совокупность В, в которой мощность пересечения любых двух множеств лежит в пределах от а до (3. И, наконец, в третьем пункте мы построим искомое множество векторов М.

В таблицах 3.1-3.5 ниже мы приводим полученные с помощью компьютера оптимальные оценки. Таблица с номером / построена именно для данного / из формулировки теоремы. По вертикали в таблице откладывается значение а с небольшим шагом, по горизонтали — Ь. В соответствующей клетке сверху вниз расположены 4 числа: 1) оптимальная константа в основании экспоненты, которая согласно утверждению теоремы служит нижней оценкой для изучаемого нами хроматического числа; 2) оптимальное значение параметра к; 3) оптимальное значение параметра а; 4) оптимальное значение параметра (3. Можно заметить также, что при 1 = 1 константа 1) приближается к величине 1.207 из упомянутой во введении теоремы Франкла-Уилсона. К сожалению, метод, позволивший в асимптотике заменить 1.207 на 1.239, нам в текущей задаче применить не удалось.