Содержание к диссертации
Введение
1 История вопроса, постановки задач и формулировки результатов 9
1.1 Оценки хроматических чисел пространств (IRn, /2) и (Qn, Z2) при запрете одного и нескольких расстояний 9
1.1.1 Постановки задач 9
1.1.2 Известные безусловные результаты 12
1.1.3 Известные условные результаты 14
1.1.4 Новые безусловные результаты 15
1.1.5 Новые условные результаты 17
1.2 Оценки хроматических чисел пространств (Шп, /і) и (Qn, її) при запрете одного и нескольких расстояний 18
1.3 Изменение нижней оценки величины хО^П) Р\ {а}) при „непрерывном" изменении метрики ОТ її К І2 20
1.3.1 Известные результаты 20
1.3.2 Метрика pt 21
1.4 Условные нижние оценки величины хк(^п5 h] {а}) и числа Борсука 22
2 Доказательства теорем 7 и 8 24
2.1 Переформулировки задач на языке теории графов 24
2.2 Основные шаги доказательства теорем 7 и 8 26
2.3 Оптимизация оценок из раздела 2.2 32
2.3.1 Асимптотика для суммы, дающей верхнюю оценку числа независимости графа Gi 33
2.3.2 Асимптотика для суммы, дающей верхнюю оценку числа независимости графа G2 35
2.3.3 Асимптотики нижних оценок хроматических чисел графов Gi, Gi и завершение доказательств теорем 7, 8 . 36
3 Доказательства оптимальных нижних оценок величины XR(Rn, h]k) в случае к > 3 39
3.1 Метод получения оценок. Экстремальная задача 39
3.2 Численные результаты. Оценки хроматических чисел 43
4 Доказательства новых условных оценок хроматических чисел и комментарии к ним 45
4.1 Доказательства теорем 9-11 45
4.1.1 Доказательства теорем 9, 11 45
4.1.2 Доказательство теоремы 10 49
4.2 Комментарии к доказательствам теорем 9 - 11 51
4.2.1 Несколько замечаний 52
4.2.2 Общий подход к получению условных оценок 53
5 Доказательство нижней оценки величины Хк(Ж\^і; 2) 55
5.1 Доказательство теоремы 14 55
5.2 Получение нижних оценок величины Хк(^П) h\k) в случае к > 3 58
6 Изменение нижней асимптотической оценки при „непрерывном" изменении метрики ОТ 1\ К І2 61
6.1 Описание метода решения задачи и основная лемма 61
6.2 Формулировка экстремальной задачи 63
6.3 Решение экстремальной задачи 65
6.4 Практическая реализация алгоритма и новые результаты . 67
7 Доказательство условных оценок величины xG^n5 h\ {а}) и числа Борсука 70
7.1 Доказательство теоремы 15 70
- Оценки хроматических чисел пространств (Шп, /і) и (Qn, її) при запрете одного и нескольких расстояний
- Асимптотика для суммы, дающей верхнюю оценку числа независимости графа Gi
- Численные результаты. Оценки хроматических чисел
- Комментарии к доказательствам теорем 9 - 11
Введение к работе
Актуальность темы
В работе изучаются хроматические числа различных метрических пространств с к запрещенными расстояниями, т.е., минимальные количества цветов, в которые можно окрасить все точки пространства таким образом, что никакие две точки одного цвета не будут находиться на запрещенном расстоянии друг от друга.
Впервые задача отыскания хроматического числа была сформулирована в 1950 году Э. Нелсоном. Первоначально речь шла о хроматическом числе евклидова пространства с одним запрещенным расстоянием. Значительную роль в развитии науки о хроматическом числе сыграли Дж. Избелл, Г. Хадвигер :, П. Эрдеш2' 3, М. Гарднер4 и братья Мозеры5' 6.
До обсуждения произвольных метрических пространств дело дошло в 1976 году, когда М. Бенда и М. Перлес рассмотрели пространство векторов с рациональными координатами с евклидовым расстоянием в нем 7.
Развитие науки о хроматических числах шло одновременно по нескольким направлениям: множество результатов было получено для евклидова пространства Rn в малых размерностях6 ' 8. Параллельно с этим шла работа над асимптотическими верхними и нижними оценками. Первая нетривиальная (линейная по п) нижняя оценка хроматического числа евклидова пространства с одним запрещенным расстоянием была получена Д. Райским 9. Затем Д. Ларман, К. Роджерс, П. Эрдеш, В. Шош и Ж. Надь доказали квадратичную по п нижнюю оценку 8 ' 10. Позже П. Франкл и Р. Уилсон получили экспоненциальное ограничение снизу для указанной величины n. A.M. Райгородскому принадлежит наилучшая на данный момент константа в нижней экспоненциальной оценке классического хроматического числа8. Кроме того, им были получены общие верхняя и нижняя экспоненциальные оценки для произвольного числа запрещенных расстоя-
ХН. Hadwiger, Ungeloste Probleme N 40, Elemente der Math., 16 (1961), 103 - 104.
2P. Erdos, Some unsolved problems, MTA MKI Kozl, 6 (1961), 221 - 254.
3P. Erdos, On some problems of elementary and combinatorial geometry, Ann. Math. Pure Appl., (4) 103 (1975), 99-108.
4M. Gardner, A new collection of brain teasers, Scientific American, 206 (Oct. 1960), 172 - 180.
5 L. Moser and W. Moser, Solution to Problem 10, Can. Math. Bull., 4, (1961), 187-189.
6A. Сойфер, Хроматическое число плоскости: его прошлое, настоящее и будущее, Матем. просвещение, 8 (2004).
7М. Benda and М. Perles, Colorings of metric spaces, Geombinatorics, 9 (2000), 113 - 126.
8 A.M. Райгородский, Проблема Борсука и хроматические числа метрических пространств, Успехи
Матем. Наук, 56 (2001), N1, 107 - 146.
9 Д.Е. Райский, Реализация всех расстояний при разбиении пространства Rn на п + 1 часть,
Матем. заметки, 7 (1970), N3, 319 - 323.
10 D.G. Larman and С.A. Rogers, The realization of distances within sets in Euclidean space, Mathematika,
19 (1972), 1 -24.
11 P. Frankl and R. Wilson, Intersection theorems with geometric consequences, Combinatorica, 1 (1981),
357 - 368.
ний 12 ' 13. Наилучшая верхняя оценка для одного запрещенного расстояния была доказана Ларманом и Роджерсом 10.
В задаче о хроматическом числе пространства (Rn,/i), где II х II= Х^=і \хі\і наилучшая нижняя оценка принадлежит Райгород-скому 13'14 а верхняя — Дж.-Х. Канг и 3. Фюреди 15.
Таким образом, в задаче о хроматическом числе за шестьдесят лет было получено множество результатов, однако к настоящему моменту далеко не на все вопросы в этой области были получены ответы. Так, например, недостаточно изучена ситуация, когда множество запрещенных расстояний состоит более чем из одного элемента.
В диссертации мы рассматриваем, главным образом, асимптотические нижние оценки хроматических чисел вещественного пространства Rn с различными метриками при запрете нескольких расстояний и пространства векторов с рациональными координатами. Новизна нашего подхода состоит в том, что мы впервые применяем к данной задаче методы решения конечномерных экстремальных задач. С помощью методов выпуклой оптимизации удается улучшить старые оценки и получить новые.
Также в работе затрагивается еще одна задача комбинаторной геометрии — проблема Борсука. В 1933 году Борсук высказал гипотезу, согласно которой всякое ограниченное множество в Rn может быть разбито на (п+1) часть меньшего диаметра 16. В некоторых маленьких размерностях гипотеза была доказана, но для пространств размерности больше некоторого N гипотеза опровергнута 17 ' 18. В настоящее время идет борьба за уменьшение значения N. Кроме того, для числа Борсука (то есть минимального числа частей, на которое всегда можно так разбить ограниченное множество, что диаметр каждой части будет меньше диаметра исходного множества) были доказаны асимптотические верхние и нижние оценки. Верхняя (экспоненциальная) оценка принадлежит О. Шрамму 19, а нижняя была доказана Каном - Калаи и Райгородским и представляет собой константу в степени
- 8 , 17 , 20 , 21_
12 Н.Г. Мощевитин, A.M. Райгородский, О раскрасках пространства Шп с несколькими запрещен
ными расстояниями, Матем. заметки, 81 (2007), N5, 733 - 743.
13 A.M. Райгородский, О хроматическом числе пространства с метрикой lq, Успехи матем. наук,
59 (2004), N5, 161 - 162.
14 A.M. Райгородский, О хроматических числах метрических пространств, Чебышевский сборник,
5 (2004), N1(9), 175 - 185.
15 J.-H. Kang, Z. Furedi, Distance graphs on Z with l\-norm, Theoretical Сотр. Sci. 319 (2004), N1 -
3, 357 - 366.
16 K. Borsuk, Drei Satze iiber die n-dimensionale euklidische Sphare, Fund. Math., 20 (1933), 177-190
17J. Kahn, G. Kalai, A counterexample to Borsuk's conjecture. Bull. Amer. Math. Soc. (N.S.) 29 (1993),
no. 1, 60-62.
18A.M. Райгородский, О размерности в проблеме Борсука, Успехи матем. наук, 52 (1997), N6, 181 -182.
19Schramm О. Illuminating sets of constant width, Mathematika, 35 (1988), 180 - 189.
20A.M. Райгородский, Об одной оценке в проблеме Борсука, Успехи матем. наук, 54 (1999), N2, 185 -186.
21А.М. Райгородский, Проблема Борсука для (0,1)-многогранников и кросс-политопов, Доклады
В настоящей работе рассматривается связь между двумя названными задачами и доказывается условный результат, касающийся усиления оценок для хроматического числа и числа Борсука.
Цель работы
Изучение свойств хроматических чисел различных метрических пространств с одним и несколькими запрещенными расстояниями при росте размерности пространств, получение асимптотических нижних оценок этих величин;
применение современных методов выпуклой оптимизации к задачам оценки хроматических чисел;
изучение связи задачи о хроматическом числе с задачей Борсука.
Основные методы исследования
В диссертации используются методы дискретной математики, линейно-алгебраический метод в комбинаторике, методы дискретной оптимизации, методы выпуклой многомерной минимизации.
Научная новизна
Результаты работы являются новыми и состоят в следующем.
Получены новые асимптотические нижние оценки хроматических чисел конечномерного пространства с евклидовой метрикой и с метрикой /і при запрете нескольких расстояний. Доказанные оценки является наилучшими в рамках использованного метода.
Исследовано изменение асимптотической нижней оценки хроматического числа пространства (Rn,p) с одним запрещенным расстоянием при "непрерывном" изменении метрики р ОТ 1\ К І2-
Разработана техника решения специального класса задач выпуклой многомерной минимизации, применимая для получения асимптотических нижних оценок хроматических чисел.
Изучена связь задачи о хроматическом числе и задачи Борсука. Получены ограничения на сумму показателей оценок для задачи о хроматическом числе и задачи Борсука.
Теоретическая и практическая ценность
Диссертация носит теоретический характер. Результаты диссертации могут найти применение при изучении задачи о хроматическом числе мет-
РАН, 371 (2000), 600 - 603.
рического пространства, линейно-алгебраического метода в комбинаторике, проблемы Борсука, при исследовании дистанционных графов в различных метрических пространствах.
Апробация результатов
Результаты диссертации докладывались автором на следующих научных семинарах и конференциях:
Международная конференция „Шестой Чехословацкий Симпозиум по Комбинаторике, Теории Графов, Алгоритмам и Приложениям" в г. Прага (Чехия, 2006 г.).
Международная конференция „Горизонты Комбинаторики" в г. Бала-тональмади (Венгрия, 2006 г.).
IX международный семинар „Дискретная математика и ее приложения", посвященный 75-летию со дня рождения академика О.Б. Лупа-нова (Москва, 2007 г.).
Международная конференция „Фестиваль Комбинаторики и Информатики" в г. Кестхей (Венгрия, 2008 г.).
Международная конференция „Европейская Комбинаторика" в г. Бордо (Франция, 2009 г.).
Кафедральный семинар кафедры математической статистики и случайных процессов механико-математического факультета МГУ, 2007г.
Семинар под руководством д. ф.-м. н., профессора СВ. Конягина на механико-математическом факультете МГУ, 2007г.
Семинар „Дискретный анализ" под руководством д. ф.-м. н., профессора А.А. Сапоженко на факультете ВМиК МГУ, 2010г.
Семинар „Линейно - алгебраические и вероятностные методы в комбинаторике" под руководством д. ф.-м. н. A.M. Райгородского в МГУ, 2006 - 2010гг.
Публикации
Основные результаты диссертации опубликованы в 8 работах автора, список которых приведён в конце автореферата [1-8].
Структура и объем диссертации
Оценки хроматических чисел пространств (Шп, /і) и (Qn, її) при запрете одного и нескольких расстояний
В разделе 1.1 мы упомянули, что понятие хроматического числа пространства было распространено на случай произвольной метрики (ср. [7, 8]). В этом разделе мы обсудим ситуации, в рамках которых речь пойдет о метрике її. Иными словами, пас снова будут интересовать пространства Rn,Qn; однако теперь евклидову метрику мы заменим метрикой Мы введем величины, аналогичные величинам Определяться они будут в точности так же; разве что расстояние между векторами мы отныне станем измерять по-новому (см. раздел 1.1). Обозначим хроматические числа, которые нам предстоит изучить в дальнейшем, соответственно: Сперва, как и в случае метрики 12, выпишем известные безусловные результаты. Теорема 12. Для любых X, Y Є {Q, Ш} имеют место неравенства Теорема 12 доказана Райгородским в 2003 году (см. [13, 14]). Теорема 13. Для любых X, Y Є {Q, R} и для произвольного к имеют место неравенства Нижняя оценка в теореме 13 принадлежит Райгородскому (см. [13, 14]), верхняя — Каиг и Фюреди (см. [15]). Сперва в [44, 45] нам удалось уточнить второе неравенство в теореме 12, а также получить ряд новых оценок при к 2. Теорема 14. Для любых X,Y Є {Q, Ш} имеют место неравенства Эту теорему мы докажем в разделе 5.1. Затем результаты теоремы 14 были слегка улучшены в совместной работе с Е.С. Горской.
А именно, на основе конструкции, использованной при доказательстве теоремы 14, были получены оптимальные оценки в случае трех, четырех и большего числа запрещенных расстояний. Константа кч улучшена не была. В главе 5 мы опишем метод оптимизации, приведший к данному результату, и тогда же выпишем в виде таблицы все новые результаты. Отметим лишь, что теперь к3 = 2.003..., «4 = 2.334.... В этом разделе мы будем рассматривать пространства (Кп, lq), где q Є [1, +оо], а для любых точек х = (хі,..., хп), у = (?/i,..., уп) расстояние между ними определяется как Кроме уже упоминавшихся оценок известны также оценки для произвольной метрики lq: Нижняя оценка в (1.3) была фактически получена в [11] П. Франклом и P.M. Уилсоном, а верхняя доказана в [15] Канг и Фюреди. Несложно также показать справедливость равенства где а — любое вещественное число. Подробнее с историей задачи можно ознакомиться по работам [8, 22]. Из предыдущего параграфа видно, что константы в известных на сегодняшний момент нижних оценках хроматического числа достаточно хаотично зависят от q. А именно, даже если не брать в расчет q — со, мы имеем два выделенных значения — д = 1ид = 2, - при которых упомянутые константы оказываются существенно больше своих аналогов при всех остальных значениях q. Разумеется, это связано со спецификой метода, при помощи которого были получены все эти константы. Желая как можно глубже понять суть метода, мы проследим в настоящей работе то, как меняется константа в основании экспоненты при своеобразном „непрерывном" переходе от метрики її к метрике І2- Для этого нам потребуется величина Здесь t может принимать любое целое значение от 0 до п. Легко видеть, что при t = 0 данная величина совпадает с корнем из метрики 1\, а при t = п — с метрикой І2 Несложно убедиться, что функция / (х, у) является метрикой при каждом допустимом значении t. Неотрицательность, равенство нулю расстояния между совпадающими точками и симметрия очевидны. Неравенство треугольника проверяется непосредственно:
Здесь первое неравенство объясняется отбрасыванием части неотрицательных слагаемых, а второе и третье — неравенством треугольника для метрик 1\ и І2 соответственно. Заметим, что все неравенства в цепочке являются строгими только в случае совпадения векторов. Единственное нетривиальное свойство метрики для pt доказано. Отметим также, что при t п указанная метрика не порождает нормы, так как для нее не выполняется свойство однородности. В главе 6 мы получим нижние оценки величины x№-n Pt, {а}) для всевозможных значений t. Полученные результаты будут представлены в виде таблицы и графика. Заметим еще, что в данном случае (впрочем, как и в некоторых предыдущих ситуациях, когда речь шла об одном запрещенном расстоянии) значение хроматического числа не зависит от величины запрещенного расстояния а, так как любую раскраску, соответствующую запрещенному расстоянию а\, можно превратить в раскраску для запрещенного расстояния 22 масштабированием первых t координатных осей в раз, а остальных осей — в ( ] раз. Поэтому мы можем далее писать xQ n,Pt) вместо xO&n,Pt, {«}) Данный раздел посвящен формулировке результата, связывающего между собой две, на первый взгляд, достаточно далекие друг от друга задачи: задачу о хроматическом числе метрического пространства и задачу Борсука о разбиении ограниченного множества положительного диаметра на части меньшего диаметра. Задача Борсука была поставлена в 30-е годы XX века, немногим раньше задачи о хроматическом числе, и в ней были достигнуты значительные продвижения (см. [8], [16] - [21]). Числом Борсука f(n) называется минимальное число частей, на которые можно так разбить произвольное ограниченное множество положительного диаметра в Rn, чтобы диаметр каждой части был меньше диаметра исходного множества. Нас будут интересовать асимптотические нижние оценки хроматического числа х(М", h, {а}) и числа Борсука /(п) при стремлении п к бесконечности. Наряду с уже упоминавшимися оценками величины хроматического числа евклидова пространства с одним запрещенным расстоянием
Асимптотика для суммы, дающей верхнюю оценку числа независимости графа Gi
Шаг 1. Пусть фиксированы параметры v 0,... ,v 3, по которым, в зависимости от того, какое из трех утверждений мы доказываем, однозначно определена, в частности, величина р\ р\п (см. шаг 2 в разделе 2.2). Заметим, что вид запрещенных расстояний нам сейчас безразличен, т.к. множество Лі, по которому ведется интересующее нас суммирование, полностью задается через P v Очевидно, При этом І Лі І х пс, где с = const, так что, если мы установим асимптотику п! max —;—-Ц—г = (771 + о(1))п, ( о, і, 2,«з)єЛі0!і!І2! з! то автоматически мы придем и к обещанному выражению в котором лишь бесконечно малая величина будет несколько иной. Так мы и поступим. Шаг 2. Рассмотрим множество А = {(4444 : і Є (0,1) Vz, t 0 + + i3 - 1, A + 2t 2 + 3t 3 = p J. Пользуясь стандартными средствами анализа (формула Стирлинга для факториала и пр.), нетрудно показать, что т.е., что, в действительности, (последнее о(1) зависит от того, сколь точно выражение р п аппроксимирует величину р\ (см. шаг 2 в разделе 2.2)). Фактически мы делаем замену ti — t jU, і Є {0,1,2,3}, и все искусство состоит в том, чтобы „оторваться" от „границ" (т.е. от ситуаций, когда t[ = 0 при каком-нибудь г) и преобразовать неравенство t\ + 2 + 3 Pi 1 в равенство t[ + 2t 2 + 3 3 = р[. Это больших усилий не требует. Понятно теперь, что ввиду сказанного достаточно минимизировать по Л[ функцию энтропии t oln Q + + taint s. Шаг 3. Необходимое условие нужного нам минимума записывается через множители Лагранжа в виде системы уравнений ( l + ln + Ai = 0, l + lnt,1 + Вычтя поочередно из второго, третьего и четвертого уравнений системы первое, получим, что для некоторого х выполнены соотношения t[ = xt 0, t 2 = xt[, t 3 = xtr2, то есть, t[ = xt 0, t2 = XH Q, t 3 = x3t 0.
Подставив данные выражения в пятое и шестое уравнения системы и исключив t 0: получим кубическое уравнение от одной переменной которое без особого труда осуществляется с помощью классических формул Кардано. Для каждого вещественного х, удовлетворяющего указанному уравнению, получаем 3 1 + х + х2+ х3 Нетрудно убедиться в том, что в данном случае выполнены все условия теоремы Каруша - Куна - Таккера (см. [40]), и необходимого условия минимума достаточно. Таким образом, остается выбрать тот ж, для которого значение величины t 0\nt 0 -\ H3ln3 окажется наименьшим. Отметим, что все это делается „руками", если числа v Q,...,v 3 известны. Но мы их заранее фиксировали, и все в порядке: при заданных наперед v 0,...,v 3 константа 771 вычисляется явно. Действуем в точности так же, как и в предыдущем параграфе: фиксируем параметры v 0,... ,v A (а стало быть, и то или иное р2) и приходим к необходимости минимизации энтропии t Qln t 0 + + t A\n t A по A = {(і оЛЛАЛ) - І Є (0,1) У і, t 0 + --- + t A = 1. $1 + 2 + 3 + 4 =й . Опять-таки, имеем систему уравнений Преобразованиями, аналогичными проделанным на шаге 3 параграфа 2.3.1, получаем уравнение 2- 2+1 Р 2 Р2 о, X которое решаем по формулам Кардано. В результате для каждого вещественного корня х имеем и остается выбрать тот я;, для которого энтропия минимальна. Снова все это без усилий делается „руками", и константа в выражении вычисляется явно. Общая технология. Здесь все уже просто. Сперва с помощью формулы Стерлинга находим асимптотики max , , ч ,, . ,, , ч ,, . ч ,, max ,-А (У ОУКУ ІГМУКУ1 , Л {У ,)ЧУ 1)ЧУ 2)ЧУ Ъ)ЧУ АУ и сравнить их между собой. Последние вычисления осуществляются с помощью компьютера с любой наперед заданной степенью точности. Сейчас понятно (ср. шаг 1 раздела 2.2), почему выбор vi в виде Vi v\n не слишком ограничителен: дело в том, что указанное допущение как раз дает приведенные выше асимптотики; без него формулы станут более громоздкими, а в конечном итоге изменятся разве что бесконечно малые в основаниях экспонент. Ниже мы приводим значения и те v[, на которых эти значения достигаются. Этим мы завершаем доказательства теорем 7, 8.
Завершение доказательства теоремы 7. Пусть Пусть = 0.033..., v[ = 0.320..., «2 = 0.513..., и3 = 0.126..., vj = 0.006... и p 2 такое, как на шаге 2 в разделе 2.2. Тогда 5fc(R», /2; 2) xR(Qn, h; 2) f я! = (1.465... + о(1))". , . t0\tilt2lt3lU\ Таким образом, 1.465... = (2: и тут финальный максимум достигается на второй из сравниваемых величин, хотя отличие этой величины от первой крайне мало существенно. Завершение доказательства первого утверждения теоремы 8. Пусть v = 0.050..., v[ = 0.325..., v2 = 0.475..., Ug = 0.150... и р[ такое, как на шаге 2 в разделе 2.2. Тогда ! п\ Хм(Щ к; 3) xR(Qn, к\ 3) п, = (1.649... + о(1))". і0! і! 2! з! Пусть = 0.053..., vi = 0.320..., 2 = 0.460..., и3 = 0.153..., = 0.013.. и р 2 такое, как на шаге 2 в разделе 2.2. Тогда п тІ7;і \VI\VI\DA\ XR(R», г2; 3) 5fc(Q , fe; 3) "f n, = (1.664... + 0(1))". 4 ч , о! і! 2! з! 4! (Г0іЧ, 2!СЗ,Й)ЄЛ2 Таким образом, 1.664... = (, и тут финальный максимум достигается на второй из сравниваемых величин. Завершение доказательства второго утверждения теоремы 8. Пусть vj = 0.065..., «1 = 0.320..., v2 = 0.445..., v3 = 0.170... и р[ такое, как на шаге 2 в разделе 2.2. Тогда -i!?)i !»io!i;- ! Хн(К", h\ 4) XK(Qn, h\ 4) »» n, = (1.803... + о(1)У (І0, 1, 2,Із)ЄЛі Пусть и = 0.020..., = 0.173..., v2 = 0.420..., vj = 0.313..., vj = 0.073... и p 2 такое, как на шаге 2 в разделе 2.2. Тогда xR(Rn, к; 4) ЫОГ, к; 4) jf i -w n, = (1.836... + o(i))n. Z о! і! 2! з! 4! Таким образом, 1.836... = , и тут финальный максимум достигается на второй из сравниваемых величин.
Численные результаты. Оценки хроматических чисел
Вычисление констант Sd,k Для всех паР чисел d: к осуществляется по одной и той же схеме. Используя алгоритм, изложенный в [46], перебираем 2d l векторов аг, для каждого вектора численно решаем следующую систему уравнений: (3.5) Затем мы находим значения А и /х, после чего находим максимальное значение Sd,k в зависимости от этих параметров по всем г = 1,..., 2d l. Данный алгоритм может быть реализован на компьютере при небольших значениях d, например, при d 20. Результаты вычислений соберем в следующей таблице. Для каждого к = 2,..., 20 мы нашли величины Sd,k при всех d = 2,..., 20 и записали в таб лицу наибольшее из этих чисел. Как показали вычисления, при каждом к функция Sa,k возрастает по d, и максимум по всем d = 2,..., 20 достигается при d = 20. Соответственно, в таблицу занесены только значения при d = 20. С другой стороны, рост Sd,k при d, близких к 20, незначителен и практически стабилизируется. Это позволяет надеяться, что при данных к указанные значения S2o,k и Ск близки к оптимальным. В таблице выписаны значения параметров р, при которых достигается максимум в нашей задаче, а также соответствующие параметры точек минимумов А и /л при данных р. Последний столбец представляет искомые оценки Ск на показатели асимптотического роста хроматических чисел х(Кп, &) ПРИ п — оо. Как мы видим, уже при к = 3,4 они несколько улучшают оценки теоремы 8, а при к 5 являются новыми и неулучшаемыми для данного метода. В [46] мы указываем способ получения оценок Ск при любых к 21 и высказываем гипотезу, что они для данного метода также неулучшаемы. Полученные данные ставят множество вопросов и открытых задач. Например, было бы интересно оценить рост величины Ск с ростом к.
По данным таблицы можно предположить, что рост этот меньше линейного и замедляется с ростом /с, т.е., функция Ск возрастает и вогнута по к. В этой главе мы приведем доказательства теорем 9-11 (см. раздел 4.1), а также явно укажем общую технологию, позволяющую при некоторых условиях производить подобные результаты (см. раздел 4.2). В частности, будут прокомментированы слова „запас прочности" (см. раздел 1.1) и др. Ниже мы отдельно докажем теоремы 9, 11 и отдельно — теорему 10. Шаг 1. Посмотрим на доказательство второго утверждения теоремы 8. Пусть значения параметров, при которых Без ограничения общности (ср. шаг 1 раздела 2.2) положим Vj = [г п] при j Є {0,1,2,3} и г;4 = п — VQ — — v%. При соответствующих возьмем 7 = S2 2. Зафиксируем произвольную функцию f(n) = o{n) (не слишком „маленькую"; скажем, f(n) = ) и рассмотрим такую последовательность размерностей {щ} , что для любого п Є {щ} на интервале (7,7 + /(n)) есть (хотя бы одно) число р вида р = 22-7-1 (берем для определенности наименьшее) с некоторым натуральным j (/(п) влияет только на частоту, с которой числа щ встречаются в натуральном ряде). Именно с этими размерностями мы станем работать в дальнейшем, и именно они неявно присутствуют в верхних пределах, которые фигурируют в формулировках теорем 9, 11. Заметим, что S2 — Ър s2, причем р р2, г — со (ср. шаг 2 в разделе 2.2). Иными словами, р играет почти ту же роль, что и р2, с той лишь разницей, что, в отличие от р2, это число не является простым; правда, оно есть степень простого, и это важно. Положим V — V2 и напомним, что техника из раздела 2.3 дает асимптотику где в нашем случае (см. 2.3.3). Шаг 2. Пусть (ср. шаг 3 в разделе 2.2).
Справедлива Лемма 3. Какова бы ни была совокупность векторов W С V, расстояние между любыми двумя элементами которой не принадлеэюит множеству {аі, 02,03,04}; выполнено неравенство В доказательстве леммы почти дословно повторяется рассуждение, проведенное нами на шаге 5 раздела 2.2. Единственная тонкость состоит в том, что теперь число р не является простым. Однако эта трудность легко преодолевается (см. [8, 35]) за счет модификации полиномов (см. шаг 5 разделе 2.2), и мы не станем тратить на нее время в данной работе. Важно, впрочем, что р — это степень простого числа: без этого допущения ничего не получится. Нетрудно ответить и на вопрос, зачем мы так, казалось бы, усложнили себе жизнь, заменив совсем уж понятное простое Р2 на чуть более „вычурное" р. Дело в том, что иначе мы бы не смогли утверждать, что величины 01,0,4 рациональны. В то же время сравнение с обозначениями шага 3 раздела 2.2 сразу же наталкивает на мысль, что 01,...,04 еще сыграют роли запрещенных расстояний; но ведь не стоит забывать, что в теоремах 9, 11, которые мы сейчас доказываем, рациональные запреты очень нужны. Замечательно еще и то, что, поскольку р р2, технология параграфа 2.3.2 дает нам формулу
Комментарии к доказательствам теорем 9 - 11
В параграфе 4.2.1 мы сформулируем несколько замечаний, и в результате станет еще более понятным тот общий рецепт получения условных оценок, который мы вкратце изложим в параграфе 4.2.2. Замечание 1. Посмотрим внимательно на доказательство любой из теорем 9, 10, 11 — скажем, на доказательство теоремы 10. В принципе, ничто не мешало нам на шаге 3 написать „симметричное" уравнение У ,- Р г р v с положительным корнем р\ = 2.579... ф р\ (см. шаг 3 в 4.1.2). Мы бы тогда и дальше действовали „симметрично". Сперва взяли бы граф G — {V,E) с рациональным запретом, т.е. с Е = {(х, у) Є V х V : (х, у) = (у, х), Z2(x, у) = щ}, а затем (в соответствии с альтернативой „ x(G) р или a(G) /?"") - граф G — (V ,E ) с \V \ pi и с иррациональным запретом, т.е. с Е = {(х,у) Є V х V : (х,у) = (у,х), Z2(x,y) = а2}. Как следствие, снова возникла бы дилемма: либо x (R», к\ 1) + xQ(Qn, к\ 1) X + Сь Pi либо ХЕГ, /2; 1) + xQ(Q", /2; 1) - + Єї Из этой дилеммы вытекало бы по-прежнему, что Ы»". h\ 1) + XQ(Q". fe; 1) X + Сі = р- + Єї Казалось бы, может получиться, вообще говоря, другой результат. Однако, легко убедиться в том, что ничего нового здесь нет и что, опять-таки, У - Р\ У Р\ Pi V Pi Л Таким образом, „порядок альтернирования" роли не играет. То же самое верно и для теорем 9, 11. Замечание 2.
Попробуем осознать, в чем смысл выражения „запас прочности" из главы 5. Сделаем это снова на примере теоремы 10. Мы утверждаем, что для указанной теоремы роль запаса прочности выполняет разность Сг — Cii = 0.011... Этот запас, как видно, невелик; но и константа J2 весьма близка к нулю (ср. комментарий к теореме 10 в главе 1). Скажем так: если бы (,2 была меньше произведения di, то вообще ничего бы не получилось. Действительно, мы ведь хотим фактически, чтобы имели место неравенства — Сі и ь Из этих неравенств и следует, что С2 = — — Cisi V Pi V Иначе альтернирование не пройдет. Ясно теперь, что, чем больше величина Сг — &ъ тем сильнее будет наш результат и тем, стало быть, больший в нем будет „запас прочности". Аналогично, для теоремы 9 запас прочности — это С — іСг = 0.117..., а для теоремы 11 запас прочности — это (% — С,\С,2 — 0.020... В теореме 9 запас прочности был настолько велик, что даже замена і на (і в вычитаемом не позволила его полностью израсходовать. Пусть при некоторых к\, к2 Є N и Y Є {Q, Ш} имеются безусловные оценки XR(R", к\ Ь) С і, ЫУп, h; к2) С 1. Мы хотим установить неравенство ХнО ". к\ ki) + ЫУп, h\ к2) С + С + , S = const 0. Положим к = к\ + /. Зафиксируем, далее, такие d и V = V(VQ, г і,..., г ), что при них для данного к значение константы ( в оценке XR(R", к\ к) xK(Qn, h; к) (Ск + о(1)Г максимально (см. раздел 3.2). Вернее, такой максимум может и не существовать, но мы возьмем самое большое из тех &, которые на нынешнем этапе развития технологии удается вычислить явно. Такое & заведомо есть ввиду несовершенства методов. Сравним величины & и . Если, несмотря ни на какие наши усилия, Ск СС7 то ничего не получится (ср. замечание 2), т.к. запас прочности в этом случае отсутствует. Иначе произведем еще один тест. А именно, зададимся (при наших d яУ) числами s = Ц{0, ...,d-l};v0,..., vd-i), s = s({0,..., d - 1}; v0,..., vd-i) (см. раздел 2.4), положим 7 = j = и посмотрим, найдется ли такая функция /(n) = о(п) и такая последовательность размерностей {щ} , что для любого те Є {Щ}І І на интервале (7,7 + /(71)) есть V (простое или степень простого), для которого в множестве чисел присутствует не менее / рациональных элементов (ср. шаги 1 и 2 в 4.1.1 и 4.1.2). Если результат теста отрицательный, то, опять-таки, ничего не выйдет. Допустим, что тест пройден. Тогда из леммы 2 (раздела 3.1) получаем следующее утверждение (ср. 4.1.1 и 4.1.2). Лемма 5. Какова бы ни была совокупность векторов W С V, расстояние между любыми двумя элементами которой не принадлеоюит мноэюеству {oi,..., afc}; выполнено неравенство (t0,..;td-l)eA A={(t0,...,td-1) :UeNU{0}Vi, t0+ ... + td-i = те, h + 2t2 + ... + (d - l) d_i p - 1}. Вспоминаем теперь, что (ср. шаги 1 и 2 в 4.1.1 и 4.1.2, а также см. раздел 2.4) \V\ = {V + о{1))п п LQ. ... br—\. (to,...,tr-i)A (обе константы У и те вычисляются явно).
Берем положительный корень р\ уравнения Р V и аналогично тому, как это было сделано на шаге 4 параграфа 4.1.1, получаем XR(Kn,/2;A;i) + XQ(Yn,Z2;A:2) - + C, = - + C-C + C + 0; Pi V все готово. 5.1 Доказательство теоремы 14 Шаг 1. Дословно повторяется все, что сказано на шаге 1 раздела 2.2. Шаг 2. Рассматриваются величины si = s({0,1,2,3}; vo, vi,v2, v3) = max /i(x, y), х,уЄКх 52 = s({0,l,2,3,4:};vo,vi,V2,v3,v4) = max /i(x,y), x,yeV2 Si = 5((0,1,2,3) 0, 1, 2,) = min /i(x,y) = 0, s2 = s{{0,l,2,3,4};v0,vi,v2,v3,V4) = min /i(x,y) =0. Х,уЄ 2 Это первый специфический момент, обусловленный тем фактом, что в метрике її скалярного произведения нет. Ясно, впрочем, что, как и прежде, все введенные величины без труда явно вычисляются. Далее, как и на шаге 2 раздела 2.2, определяются некоторые простые числа Р\,р2- Для этого вновь фиксируется к Є {2,3,4} (количество будущих запретов) и на роль pi (г = 1,2) выбирается минимальное нечетное простое, такое, что Si — 2{к + l)pi 0 = _І. Помимо дополнительного требования нечетности (которое, правда, почти бессодержательно), здесь есть еще одно отличие: это множитель 2 в привычном произведении 2{к + l)pi (раньше было (к + l)pi). Причина его появления станет очевидной лишь на шаге 5. Финальные замечания шага 2 раздела 2.2 (о порядке роста pi) остаются, естественно, в силе. Шаг 3. Действуем так же, как на шаге 3 раздела 2.2.
Для каждого і Є {1,2} и для каждого к Є {2,3,4} полагаем o-i = 2р», а2 = 4рй ..., ак = 2kpt с соответствующим pi. Строим G\ — {Vi,E{),G2 = ІУ21Е2) по стандартной технологии. Шаг 4 (формулировка основной леммы). Лемма 6. Каковы бы ни были графы G\,Gi, имеют место неравенства min{n,pi —1} min{n,p2 —1} q=0 9=0 с соответствующими pi,Р2 Шаг 5 (доказательство основной леммы). Как и в главе 6, обсудим только первую часть леммы. Справедливо Утверждение 1. Расстояние между векторами х, у Є V\ сравнимо с 0 = sx по модулю р\ тогда и только тогда, когда либо х = у, либо 1\ (х, у) Є {ai,...,ak}. Здесь важно, что для любых х, у Є V\ величина Zi(x, у) четна, в то время какрі - нечетное простое. Отсюда и нечетность, и удвоение (см. шаг 2). Каждому вектору х Є V\ сопоставим функцию Fx : V\ — Z, задаваемую формулой Pi-i х(у) = ГІ0 - і(х,у)), у = (г/і,...,з/„). 3=1 Это пока не полином, поскольку в указанной формуле присутствуют модули вида \xv — yv\. Однако, коль скоро у Є Vi, мы заведомо имеем yv Є {0,1,2,3}, так что для каждого конкретного хи Є {0,1,2,3} функция \xv — yv\ принимает не более четырех различных (целых) значений, а стало быть, ее можно заменить (интерполировать) многочленом степени не выше третьей с коэффициентами из поля рациональных чисел. В результате все-таки возникает полином F , который можно рассматривать и как функцию F : V\ —у Z, и как элемент кольца Q[?/i,... ,уп]. Подобно тому, как это было сделано на шаге 5 раздела 2.2, профакторизуем, наконец, F по системе соотношений УзІУз - l)fe - 2)(Уз - 3) = 0, j = 1,...,п, и получим полином (функцию) Fx.
