Содержание к диссертации
Введение
1 История вопросаиформулировки результатов 9
1.1 История вопроса 9
1.2 Нижние оценки хроматических чисел трёхмерных графов расстояний с запретами на клики 18
1.3 Нижние оценки хроматических чисел графов расстояний с запретами на клики в растущей размерности 19
1.3.1 Результаты с одним запрещённым расстоянием 19
1.3.2 Сравнение оценок clique() в теоремах 4, 5, 6 и 7 21
1.3.3 Результаты с несколькими запрещёнными расстояниями 24
1.3.4 Таблицы результатов теоремы 8 25
2 Хроматические числа трёхмерных графов расстояний без тетраэдровитреугольников 32
2.1 Доказательство теоремы 2 32
2.2 Доказательство теоремы 3 35
2.2.1 Основная часть доказательства теоремы 3 35
2.2.2 Доказательство предложения 2 43
2.2.3 Построение графа «шевелением»: вспомогательные леммы 44
2.2.4 Процедура «шевеления» 48
3 Асимптотика хроматических чисел графов расстояний с несколькими запрещёнными расстояниями и без больших клик при росте размерности пространства 52
3.1 Доказательство теоремы 6 52
3.2 Доказательство теоремы 7 58
3.3 Доказательство теоремы 8 59
3.4 Небольшой комментарий к теореме 8 61
3.5 Решение экстремальной задачи 62
Список литературы
- Нижние оценки хроматических чисел трёхмерных графов расстояний с запретами на клики
- Нижние оценки хроматических чисел графов расстояний с запретами на клики в растущей размерности
- Основная часть доказательства теоремы 3
- Доказательство теоремы 7
Введение к работе
Актуальность темы диссертации
В работе получены результаты, связанные с классической проблемой Нельсона-Эрдёша-Хадвигера о хроматическом числе пространства. Эта проблема впервые была сформулирована Э. Нельсоном1 в 1950 году, а П. Эр-дёш2 и Г. Хадвигер3 сыграли важную роль в популяризации этой проблемы. Проблема заключается в нахождении минимального количества цветов, такого, что существует покраска всех точек пространства Шп в это количество цветов, при которой точки, находящиеся на единичном расстоянии друг от друга, покрашены в разные цвета. Для пространств с размерностями не менее двух проблема остаётся открытой, и до сих пор она очень популярна4'5'6. Для плоскости известно, что хроматическое число лежит между четырьмя и семью. Минимальный пример графа расстояний (или, что то же самое, дистанционного графа) с хроматическим числом четыре на плоскости получен братьями Л. и В. Мозерами7.
В 1976 году Эрдёш8 задал вопрос, существует ли дистанционный граф на плоскости с хроматическим числом четыре и не содержащий треугольников (поскольку все известные на тот момент примеры таких графов треуголь-
1A. Soifer, The Mathematical Coloring Book, Springer, 2009.
2L.A. Szekely, Erdos on unit distances and the Szemeredi-Trotter theorems, Paul Erdos and his Mathematics,
Bolyai Series Budapest, J. Bolyai Math. Soc, Springer, 11 (2002), 649 - 666.
3H. Hadwiger, Ein Uberdeckungssatz fur den Euklidischen Raum, Portugaliae Math., 4 (1944), 140 - 144.
4А. Сойфер, Хроматическое число плоскости: его прошлое, настоящее и будущее, Матем. просвещение, 8 (2004).
5А.М. Райгородский, Хроматические числа, Москва, МЦНМО, 2003.
6P.K. Agarwal, J. Pach, Combinatorial geometry, John Wiley and Sons Inc., New York, 1995.
7L. Moser, W. Moser Solution to problem 10, Canad. Math. Bull. Vol. 4 (1961), 187 - 189.
8P. Erdos, Unsolved Problems, Congress Numerantium XV — Proceedings of the 5th British Comb. Conf.
ники содержали). Задача была решена в 1979 году Н. Уормалдом9, а позднее примеры с меньшим количеством вершин были построены П. О’Доннеллом и Р. Хохбергом10. Также в 1999 году в своей кандидатской диссертации (а на год позже — в других своих работах11'12) П. О’Доннелл нашёл решение обобщённого варианта этой задачи, а именно, что на плоскости существуют дистанционные графы с хроматическим числом четыре и произвольным обхватом (длиной минимального цикла). В данной работе рассматривается обобщение задачи на дистанционные графы в пространствах произвольной размерности.
В растущей размерности известно, что хроматическое число ведёт себя, как экспонента13'14. Доказательства лучших нижних оценок хроматического числа используют линейно-алгебраический метод на целочисленных решётках. Этот метод также использутеся в классической задаче Борсука15 о нахождении минимального числа частей, на которое можно разбить любое неодноточечное множество в Шп так, чтобы диаметр каждой части был меньше диаметра исходного множества16'17.
Поскольку рассматриваются графы, вершины которых — узлы целочисленной решётки, а рёбра задаются определёнными расстояниями между вершинами, то задачи, о которых шла речь выше, оказываются естественно связанными с центральной проблематикой теорией кодирования. В частности, когда узлы решётки — это (0,1)-векторы, описанные выше задачи комбинаторной геометрии — это по сути задачи об экстремальных свойствах рав-
9N. Wormald, A 4-Chromatic Graph With a Special Plane Drawing, Australian Mathematics Society (Series A), 28 (1979), 1-8.
10P. O’Donnel, R. Hochberg, Some 4-chromatic Unit-Distance Graphs without small cycles, Geombinatorics, 5 (1996), 137 - 142.
11P. O’Donnell, Arbitrary girth, 4-chromatic unit distance graphs in the plane. I. Graph description, Geombinatorics, 9 (2000), №3, 145 - 152.
12P. O’Donnell, Arbitrary girth, 4-chromatic unit distance graphs in the plane. II. Graph embedding, Geombinatorics, 9 (2000), №4, 180 - 193.
13A.M. Райгородский, О хроматическом числе пространства, Успехи мат. наук, 55 (2000), 147 - 148.
14D. Larman, С. Rogers The realization of distances within sets in Euclidean space, Mathematika, 19 (1972),
№1, 1 - 24.
15K. Borsuk Drei Satze uber die n-dimensionale Euklidische Sphare, Fund. Math., 20 (1933), 177 - 190.
16P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, Springer, 2005.
17A.M. Райгородский, Вокруг гипотезы Борсука, Геометрия и механика, СМФН, 23 (2007), 147 - 164.
новесных кодов18.
Также отметим, что есть и ряд других важных задач экстремальной геометрической комбинаторики, напрямую связанных с понятием дистанционного графа, а стало быть, с тематикой настоящей работы. Такова, например, проблема нахождения максимального количества рёбер в дистанционном графе19. О ней имеется обширная литература20.
Цель и задачи исследования
Целью диссертационной работы является решение следующих задач.
-
Поиск графов единичных расстояний в Rn с как можно большим хроматическим числом и как можно меньшим кликовым числом (т.е. размером максимального полного подграфа).
-
Обобщение задачи на случай графов, ребра которых определяются несколькими расстояниями.
Научная новизна полученных результатов Все результаты диссертации являются новыми.
Практическая значимость полученных результатов
Диссертация носит теоретический характер. Результаты работы дают существенное продвижение в известной задаче об отыскании трудно раскрашиваемых графов в простанствах без клик данного размера. Эти результаты могут быть использованы для улучшения нижних оценок хроматического числа пространства, в проблеме Борсука и в других задачах комбинаторной геометрии и смежных вопросах теории кодирования.
18Ф.Дж. Мак-Вильямс, Н.Дж.А. Слоэн, Теория кодов, исправляющих ошибки, Связь, 1979. 19P. Erdos, On sets of distances of n points, American Mathematical Monthly, 53 (1946), 248 – 250. 20J. Spencer, E. Szemeredi, W.T. Trotter, Unit distances in the Euclidean plane, Graph theory and combinatorics, 1984, 293 – 303.
Основные результаты, выносимые на защиту
-
В пространстве R3 существует дистанционный граф, имеющий хроматическое число пять и не содержащий тетраэдров. В качестве примера построен граф на девятнадцати вершинах. (Теорема 2)
-
В пространстве R3 существует дистанционный граф без треугольников (циклов длины три) и с хроматическим числом пять. (Теорема 3)
-
Для произвольного натурального k 5 существует последовательность дистанционных графов без клик размера k с экспоненциально растущими хроматическими числами (в зависимости от размерности пространства). (Теоремы 6 и 7)
-
Получены оценки хроматических чисел дистанционных графов, ребра которых порождаются m расстояниями. Показано, что при m = 2 существуют последовательности графов с хроматическими числами, экспоненциально зависящими от размерности пространства, и без клик размера четыре. Также показано, что при m 3 существуют последовательности графов с хроматическими числами, экспоненциально зависящими от размерности пространства, и без треугольников. (Теорема 8)
Личный вклад соискателя
Все результаты диссертации получены соискателем самостоятельно.
Апробация результатов
Результаты, полученные в диссертации, докладывались и обсуждались на 9-ом Международном научном семинаре “Дискретная математика и приложения” (Москва, 2007 г.), международной конференции “Фестиваль комбинаторики и информатики” (Венгрия, 2008 г.), на международной конференции “EuroComb 2009: Европейская конференция по комбинаторике, теории графов и приложеням” (Франция, 2009 г.), на международной конференции “8-ая Французская комбинаторная конференция” (Франция, 2010 г.), на семинаре профессора А.М. Райгородского в МГУ имени М.В. Ломоносова, на семинаре профессора С.В. Конягина в МГУ имени М.В. Ломоносова, а также на научном семинаре “Дискретная математика и математическая кибернетика” кафедры математической кибернетики факультета вычислительной математики и кибернетики МГУ имени М.В. Ломоносова.
Публикации по теме диссертации
Результаты диссертации опубликованы в работах [1]–[5] списка литературы. Всего по теме диссертации опубликовано 5 работ. Из них 4 работы входят в список научных журналов, рекомендованный ВАК Минобрнауки РФ.
Структура и объем диссертации
Нижние оценки хроматических чисел трёхмерных графов расстояний с запретами на клики
В работе изучаются классы графов расстояний с несколькими специальными свойствами. Задача данной работы — найти графы расстояний с большим хроматическим числом и без больших клик. Граф расстояний — это граф, вершинами которого являются точки некоторого метрического пространства, а рёбра проведены между теми и только теми вершинами, расстояние между которыми равно некоторому фиксированному числу (так называемое «запрещённое расстояние»). Под хроматическим числом понимается минимальное количество цветов, в которые можно покрасить вершины графа так, чтобы любые две вершины, соединённые ребром, были покрашены в разные цвета. Клика — это набор вершин, попарно соединённых рёбрами (другими словами, полный подграф). Рассматриваются как графы расстояний с одним, так и с несколькими запрещёнными расстояниями.
Задача тесно связана с задачей нижней оценки хроматических чисел пространств. Хроматическим числом метрического пространства называется минимальное количество цветов, в которые можно покрасить все точки этого пространства так, чтобы никакие две точки одного цвета не находились на единичном расстоянии друг от друга. Обобщением этой задачи является задача нахождения хроматического числа пространства с запрещёнными расстояниями. В этом случае вершины не должны быть одного цвета, если расстояние между ними запрещённое.
Графы расстояний как с одним, так и с несколькими запрещёнными расстояниями естественным образом дают нижнюю оценку хроматического числа соответствующего пространства, поскольку если вершины графа нельзя покрасить в цветов правильным образом, то и все точки метрического пространства (а множество вершин графа — это подмножество точек метрического пространства) тоже нельзя покрасить правильным образом. Именно нижние оценки хроматических чисел графов расстояний с определёнными свойствами и будут основным объектом исследования в этой работе.
Проблема хроматического числа пространства впервые была озвучена Э. Нельсоном в 1950 году, который пришёл к ней, изучая проблему четырёх красок (в своей книге [1] А. Сойфер приводит небольшое исследование истории вопроса, включая свидетельства самого Э. Нельсона и его профессоров, однако долгое время вопрос авторства этой задачи оставался открытым). Э. Нельсон сформулировал её для случая плоскости. Своей популярностью задача во многом обязана Г. Хадвигеру, П. Эрдёшу, М. Гарднеру и братьями Л. и В. Мозерам. Поэтому в литературе проблема получила название проблемы Нельсона-Хадвигера или Нельсона-Эрдёша-Хадвигера.
Мы поговорим про результаты в этой области более подробно в основной части работы, а здесь заметим лишь, что для проблемы одного запрещённого расстояния в Ш2 доказано только, что хроматическое число (обозначаемое х(М2)) лежит между четырьмя и семью (4 х(Ж2) 7). Подобным образом, не известны точные оценки для пространств больших размерностей. Получено, что в асимптотике хроматическое число растёт экспоненциально в зависимости от размерности пространства, но точное значение основания экспоненты также не определено до сих пор1.
В 1976 году П. Эрдёш (см. [2]) поставил вопрос: существует ли на плоскости граф расстояний с хроматическим числом четыре и не содержащий треугольников? Надо сказать, что П. Эрдёш предполагал, что ответ будет отрицательным. Однако эта задача была решена (с положительным ответом) Н. Уормалдом (см. [3]), а позднее - П. О Доннеллом и Р. Хохбергом (см. [4]) в более общей постановке. В 2000 году П. О Доннелл показал, что для произвольного наперед заданного числа к можно построить граф расстояний на плоскости без циклов длины, меньшей к (размер кратчайшего простого цикла в графе называется обхватом этого графа).
Подробнее об этом будет сказано в основной части работы, заметим лишь, что на данный момент известно, что (1.239 + о(1))п х(Кп) (3 + о(1))п. П. Эрдёш не случайно задал вопрос именно таким образом. Наличие треугольника естественно повышает хроматическое число графа до трёх, поэтому можно предположить, что наличие треугольников упрощает построение графов с большим хроматическим числом. Аналогично, в больших размерностях бывают симплексы (в нашем случае симплексы и клики — это одно и то же) больших размеров, поэтому можно ожидать, что в примерах графов с большим хроматическим числом содержатся клики большого размера. Таким образом, естественным обобщением задачи П. Эрдёша является задача построения графов расстояний в пространствах больших размерностей, которые не содержат клик как можно меньшего размера и при этом имеют как можно большее хроматическое число.
В первой главе мы более подробно поговорим об истории проблемы и ранее полученных результатах, а также введём необходимые обозначения и сформулируем результаты диссертации, которые будут доказаны в последующих главах.
Подходы к получению нижних оценок хроматического числа в малых и больших размерностях принципиально различаются. В малых размерностях улучшение результатов связано с увеличением оценки хроматического числа на единицу (или изредка большее целое число). Так, например, в 2002 году О. Нечуштан улучшил нижнюю оценку (R3) с пяти до шести (см. [5]). В больших же размерностях борьба идёт за улучшение основания экспоненты в асимптотике нижней оценки хроматического числа. К примеру, А.М. Райгородскому в 2000 году (см. [6]) удалось улучшить нижнюю оценку (R) с (1.207... + (1)) до (1.239... + (1)) при .
Нижние оценки хроматических чисел графов расстояний с запретами на клики в растущей размерности
До полного графа на пяти вершинах четырёхугольной пирамиде «не достаёт» двух рёбер ( 1 3 и 2 4). Построим на парах вершин 1, 3 и 2, 4 описанную выше конструкцию. Один экземпляр этой конструкции будет построен на вершинах 1 и 3, и этим вершинам будут соответствовать вершины и конструкции. Второй экземпляр мы построим, соответственно, на вершинах 2 и 4. Это построение возможно, поскольку 1 3 = 2 4 = = 2. Теперь искомый граф расстояний окончательно построен, осталось лишь доказать, что его хроматическое число не меньше пяти и что он не содержит тетраэдров.
Докажем вначале, что хроматическое число построенного графа не меньше пяти. Действительно, предположим, что нам удалось покрасить вершины графа в четыре цвета. Тогда очевидно, что хотя бы в одной из пар вершин 1, 3 и 2, 4 обе вершины имеют один и тот же цвет (скажем, «красный»). Пусть, без ограничения общности, это пара вершин 1, 3. Рассмотрим теперь Мозеровское веретено, которое соответствовало этой паре одноцветных вершин. Заметим, что каждая вершина этого веретена соединена ребром с одной из вершин 1, 3, поэтому ни одна вершина веретена не может быть покрашена в красный цвет. Таким образом, Мозеровское веретено покрашено в три оставшихся цвета. Но, как мы знаем, хроматическое число Мозеровского веретена равно четырём. Противоречие. Значит, хроматическое число графа не меньше пяти.
Осталось отметить, что этот граф не содержит тетраэдров. Действительно, отсутствие в графе тетраэдров достигается вращением добавляемых Мозеровских веретён относительно осей, проходящих через пары точек 1, 3 и 2, 4, и небольшим перебором.
В нашей конструкции в качестве одной из составных частей мы будем использовать модификацию графа расстояний, построенного П. О Доннеллом и Р. Хохбергом (см. [4], сам граф изображён на рисунке 1.2). Мы обозначим его (см. рисунок 2.4).
Все отмеченные здесь точки, обозначенные строчными буквами, представляют вершины, а отрезки и дуги, как сплошные, так и пунктирные, которые их соединяют, представляют рёбра. Граф состоит из 4-цикла {Лі, 2, Лз, Лі} и 5-циклов Г ь Г 2, Si и 2, которые представлены сплошными линиями, а также нескольких рёбер, которые проведены между этими циклами.
Лемма 1. Хроматическое число графа, изображённого на рисунке 2.4, равняется четырём. Кроме того, он не содержит треугольников.
Доказательство. Утверждение об отсутствии треугольников очевидно. Достаточно заметить, что граф состоит из 4-цикла {Лі, Л2, Лз, А } и 5-циклов і, 2, i и 2, соединённых рёбрами, причём рёбра из одной вершины одного цикла никогда не ведут в соседние вершины другого.
Теперь докажем от противного, что покрасить вершины графа V в три цвета нельзя. Предположим, что это удалось, тогда, поскольку вершины {Лі, 2, Аз, Лі} образуют цикл, по крайней мере, одна из пар вершин {Аі, Аз} и {АЪАА} одноцветна. Без ограничения общности (картинка симметрична) будем считать, что это {Аі, Аз} и покрашены они в цвет 1. Тогда все вершины \, кроме 1, покрашены в цвета 2 и 3. Значит, g смежна с вершинами обоих цветов, то есть она может быть покрашена только в цвет 1. Теперь заметим, что все вершины \ соединены с одной из вершин цвета 1, а именно {Ai, A3, ,1}, следовательно, они могут быть только цвета 2 и 3. Но покрасить нечётный цикл в 2 цвета невозможно. Противоречие, и лемма 1 доказана.
В своей работе [4] П. О Доннелл и Р. Хохберг разместили дистанционный граф, изоморфный построенному нами (за исключением того, что в их работе вершины и совпадают), на плоскости, и таким образом привели наименьший известный пример графа, являющегося ответом на вопрос П. Эрдёша о существовании графа на плоскости с хроматическим числом четыре и без циклов.
Теперь мы построим граф 8, который является надграфом V. Как мы уже выяснили, х(Р) = 4, поэтому множество вершин V можно разбить на четыре подмножества В\, В2, Вз, ВА, так что никакие две вершины из одного подмножества не соединены ребром. Возьмём одну из таких раскрасок (разбиений множества вершин на четыре подмножества). Теперь, чтобы получить граф 8, мы добавляем к графу V четыре вершины t\, t2, t , 4 и для каждого і Є {1, 2, 3,4} соединяем t{ ребрами со всеми вершинами из В І и только с ними. Одна из возможных раскрасок приведена на рисунке 2.5. г г 9 9 Ъ п г
Для данного графа верны следующие факты. Хроматическое число () не больше пяти. Действительно, достаточно покрасить вершины 1, 2, 3 и 4 в пятый цвет, а остальные вершины в четыре цвета уже покрашены. Граф не содержит треугольников, поскольку исходный граф не содержал треугольников, а новые рёбра соединяют только вершины со старыми вершинами, причём рёбра из одной вершины проводились только в вершины одного цвета, а значит, такие вершины не были соединены ребром и не могли образовать новый треугольник. Основная идея дальнейших рассуждений содержится в предложении 1.
Предложение 1. Если в некоторой раскраске вершины h 2, и графа Е покрашены в один цвет, то для покраски всех его вершин использовано не менее пяти цветов.
Это утверждение следует из леммы 1. Пускай вершины \, 2, и 4 покрашены в коричневый цвет. Так как хроматическое число V равно четырём и каждая из вершин V соединена с одной из коричневых вершин, то потребуется ещё по крайней мере четыре цвета для покраски оставшихся вершин (в коричневый они покрашены быть не могут).
Покажем теперь, что верна следующая лемма.
Лемма 2. Граф можно разместить в пространстве1 таким образом, что вершины \, 2, :i и 4 окажутся в одной точке.
Доказательство. Заметим, что для доказательства леммы достаточно разместить граф V на сфере единичного радиуса, поскольку тогда можно будет поместить все точки u 2, :i и 4 в центр сферы, расположенный в начале координат, соединив их с соответствующими точками на сфере. Ниже дан пример того, как это можно сделать.
Основная часть доказательства теоремы 3
Как было сказано в пункте 2.2.1, мы хотим разнести положения тринадцати точек і,...,із, которые находятся в одной точке, так, чтобы оставшиеся вершины, соединённые рёбрами, остались соединёнными рёбрами. Можно представить себе граф в виде каркаса с шарнирами в вершинах, соединёнными планками, соответствующими рёбрам. Тогда в этом пункте мы покажем, что можно немного подвигать тринадцать из этих шарниров, чтобы конструкция не развалилась, а эти тринадцать шарниров, положение которых изначально совпадало, оказались в разных точках. Как уже было сказано, «шевелим» мы только вершины і,...,із. Здесь будут описаны правила, по которым меняется положение остальных вершин.
Мы введём функции, выражающие зависимость положения вершин графов 2 4 от положения вершин 15 2, 3, 4. В таблице 2.1 показана последовательность, в которой положения вершин графа зависят друг от друга.
В таблице 2.1 показан порядок присоединения вершин в графе 2 4. В первом столбце обозначена вершина, которую мы добавляем. Во втором столбце указывается, к каким ранее добавленным вершинам мы прикрепляем вершину из первого столбца. В третьем столбце написано, функцией от положения каких вершин является положение вершины из первого столбца. В четвёртом столбце показано, сколько ещё параметров надо добавить в функцию из третьего столбца, чтобы она однозначно определяла положение вершины из первого столбца. вершина прикреплена к вершинам зависимость степеней свободы
Например, в первой строчке таблицы написано, что положение вершины 1 зависит от вершины. Это означает, что для каждого данного положения вершины 1 мы разместим вершину таким образом, чтобы расстояние между tix и А\ равнялось единице. В шестой строке таблицы написано, что положение вершины 2 зависит от положения вершин t{x, A3 и \. Таким образом, зная расположения вершин t , A3 и {} в пространстве, мы хотим расположить так, чтобы она находилась на единичном расстоянии от t , A3 и {. В соответствии с леммой 4 это можно сделать, если t , A3 и { находятся достаточно близко к своим начальным положениям t , Аи { .
Мы последовательно проделаем эту операцию со всеми вершинами. Такой набор положения вершин существует, если 15 2, 3 и t,i4 находятся в некоторой достаточно малой окрестности нуля, поскольку изначально, когда все точки были в нуле, такое расположение существовало, а значит, в соответствии с леммами 4, 5 и 6 оно существует и в некоторой окрестности начальных положений точек, поскольку положение каждой вершины в таблице зависит от положения одной, двух или трёх других вершин. Таким образом, мы построили все вершины подграфа V4l244 и убедились, что расстояние между всеми парами вершин, соединёнными ребром, кроме пар {бо ,бо 5} и {ші,ш$}, равно единице.
Как видно из таблицы 2.1, положение всех вершин однозначно определяется по координатам точек {t\,..., 13}, когда все эти точки находятся в некоторой окрестности начала координат, с точностью до 8 параметров (степени свободы в последнем столбце таблицы 2.1). С другой стороны, положение точек ш\ и бо 5 может быть таково, что расстояние до ш\ и ш\ соответственно отличается от единицы. Воспользовавшись леммами 5 и 6, мы зафиксируем положение всех точек, кроме ш\ и ш\. Теперь расстояние d(uj\,Lj\) = \UJ\UJI\ — это функция от положения точек tix, U2, ti3 и ti4, а также a — координаты точки ш\, заданной в лемме 5, причём зависимость эта непрерывная.
Также известно, что эта зависимость строго монотонна по а в ttl = t{2 = t{3 = ti4 = (0,0,0) (проверено численными методами для координат, указанных в доказательстве леммы 2) и i(0, 0,0, 0,0) = 1. Таким образом, неявно можно задать функцию а , , , ) так, что По теореме о неявной функции, функции a(ti ti2,ti3,ti4) и а;{( 1, 2, t{3, ti4) непрерывны. Задав таким способом с помощью неявной функции a(t4,tn,U3,t4) координаты точки ш\ (и аналогичным образом — координаты точки ш\), мы получим, что все вершины, соединённые ребром в графе, находятся на единичном расстоянии друг от друга. Осталось выбрать такие точки { i,..., із}, в окрестности нуля, чтобы они не совпадали, а расстояние между всеми остальными вершинами (не соединёнными ребром) не было равно нулю или единице. Кроме того, требуется, чтобы, если три вершины таковы, что они все соединены с некоторой четвёртой вершиной ребром, то радиус описанной окружности был меньше единицы. Все эти условия соблюдены в начальном положении точек. Зависимость непрерывная, а значит, то же будет верно и в некоторой (3 13 = 39-мерной) окрестности начальной точки. Нам подойдут любые различные точки {t\,..., 13} из этой окрестности. Глава 3
Асимптотика хроматических чисел графов расстояний с несколькими запрещёнными расстояниями и без больших клик при росте размерности пространства
Для доказательства нам потребуется определить a(G). Это величина, в некотором смысле двойственная величине UJ{G) (отсюда и обозначение):
Эта величина называется числом независимости графа; в свою очередь, все множества вершин графа, свободные от его ребер, называются независимыми. Таким образом, число независимости — это мощность самого большого независимого множества вершин. Число независимости и хроматическое число графа связывает следующее неравенство:
Действительно, если удалось покрасить граф в х(С) цветов, то множество вершин каждого цвета — это независимое множество, ведь по определению хроматического числа вершины одного цвета не должны быть соединены ребром. Поэтому мощность множества вершин каждого цвета не больше a(G). Сложив количество вершин в этих х(С) множествах, мы получим общее количество вершин \V\, а значит, \V\ х(С) a(G).
Перейдём непосредственно к доказательству теоремы. Зафиксируем к, Ъ0, а стало быть, и т0, ть С, с. Легко видеть, что либо С = 0, либо С = {п}, либо С = [с, ті], с го. В первых двух случаях утверждение теоремы тривиально. Рассмотрим ситуацию, когда то с т\.
Возьмем произвольное с Є (с, ті). Здесь важно, что с строго больше с, хотя и сколь угодно близко к с. Если мы покажем, что Сclique(к) Ц, то, беря инфимум обеих частей неравенства по с , мы получим искомое утверждение
Доказательство теоремы 7
Как было сказано в пункте 2.2.1, мы хотим разнести положения тринадцати точек і,...,із, которые находятся в одной точке, так, чтобы оставшиеся вершины, соединённые рёбрами, остались соединёнными рёбрами. Можно представить себе граф в виде каркаса с шарнирами в вершинах, соединёнными планками, соответствующими рёбрам. Тогда в этом пункте мы покажем, что можно немного подвигать тринадцать из этих шарниров, чтобы конструкция не развалилась, а эти тринадцать шарниров, положение которых изначально совпадало, оказались в разных точках. Как уже было сказано, «шевелим» мы только вершины і,...,із. Здесь будут описаны правила, по которым меняется положение остальных вершин.
Мы введём функции, выражающие зависимость положения вершин графов 2 4 от положения вершин 15 2, 3, 4. В таблице 2.1 показана последовательность, в которой положения вершин графа зависят друг от друга.
В таблице 2.1 показан порядок присоединения вершин в графе 2 4. В первом столбце обозначена вершина, которую мы добавляем. Во втором столбце указывается, к каким ранее добавленным вершинам мы прикрепляем вершину из первого столбца. В третьем столбце написано, функцией от положения каких вершин является положение вершины из первого столбца. В четвёртом столбце показано, сколько ещё параметров надо добавить в функцию из третьего столбца, чтобы она однозначно определяла положение вершины из первого столбца.
Например, в первой строчке таблицы написано, что положение вершины 1 зависит от вершины Это означает, что для каждого данного положения вершины 1 мы разместим вершину таким образом, чтобы расстояние между tix и А\ равнялось единице. В шестой строке таблицы написано, что положение вершины 2 зависит от положения вершин t{x, A3 и \. Таким образом, зная расположения вершин t , A3 и {} в пространстве, мы хотим расположить так, чтобы она находилась на единичном расстоянии от t , A3 и {. В соответствии с леммой 4 это можно сделать, если t , A3 и { находятся достаточно близко к своим начальным положениям t , Аи { .
Мы последовательно проделаем эту операцию со всеми вершинами. Такой набор положения вершин существует, если 15 2, 3 и t,i4 находятся в некоторой достаточно малой окрестности нуля, поскольку изначально, когда все точки были в нуле, такое расположение существовало, а значит, в соответствии с леммами 4, 5 и 6 оно существует и в некоторой окрестности начальных положений точек, поскольку положение каждой вершины в таблице зависит от положения одной, двух или трёх других вершин. Таким образом, мы построили все вершины подграфа V4l244 и убедились, что расстояние между всеми парами вершин, соединёнными ребром, кроме пар {бо ,бо 5} и {ші,ш$}, равно единице.
Как видно из таблицы 2.1, положение всех вершин однозначно определяется по координатам точек {t\,..., 13}, когда все эти точки находятся в некоторой окрестности начала координат, с точностью до 8 параметров (степени свободы в последнем столбце таблицы 2.1). С другой стороны, положение точек ш\ и бо 5 может быть таково, что расстояние до ш\ и ш\ соответственно отличается от единицы. Воспользовавшись леммами 5 и 6, мы зафиксируем положение всех точек, кроме ш\ и ш\. Теперь расстояние d(uj\,Lj\) = \UJ\UJI\ — это функция от положения точек tix, U2, ti3 и ti4, а также a — координаты точки ш\, заданной в лемме 5, причём зависимость эта непрерывная.
Задав таким способом с помощью неявной функции a(t4,tn,U3,t4) координаты точки ш\ (и аналогичным образом — координаты точки ш\), мы получим, что все вершины, соединённые ребром в графе, находятся на единичном расстоянии друг от друга. Осталось выбрать такие точки { i,..., із}, в окрестности нуля, чтобы они не совпадали, а расстояние между всеми остальными вершинами (не соединёнными ребром) не было равно нулю или единице. Кроме того, требуется, чтобы, если три вершины таковы, что они все соединены с некоторой четвёртой вершиной ребром, то радиус описанной окружности был меньше единицы. Все эти условия соблюдены в начальном положении точек. Зависимость непрерывная, а значит, то же будет верно и в некоторой (3 13 = 39-мерной) окрестности начальной точки. Нам подойдут любые различные точки {t\,..., 13} из этой окрестности. Глава 3
Асимптотика хроматических чисел графов расстояний с несколькими запрещёнными расстояниями и без больших клик при росте размерности пространства Доказательство теоремы 6 Для доказательства нам потребуется определить a(G). Это величина, в некотором смысле двойственная величине UJ{G) (отсюда и обозначение):
Эта величина называется числом независимости графа; в свою очередь, все множества вершин графа, свободные от его ребер, называются независимыми. Таким образом, число независимости — это мощность самого большого независимого множества вершин. Число независимости и хроматическое число графа связывает следующее неравенство:
Действительно, если удалось покрасить граф в х(С) цветов, то множество вершин каждого цвета — это независимое множество, ведь по определению хроматического числа вершины одного цвета не должны быть соединены ребром. Поэтому мощность множества вершин каждого цвета не больше a(G). Сложив количество вершин в этих х(С) множествах, мы получим общее количество вершин \V\, а значит, \V\ х(С) a(G).
Перейдём непосредственно к доказательству теоремы. Зафиксируем к, Ъ0, а стало быть, и т0, ть С, с. Легко видеть, что либо С = 0, либо С = {п}, либо С = [с, ті], с го. В первых двух случаях утверждение теоремы тривиально. Рассмотрим ситуацию, когда то с т\.
