Московский государственный университет

им. М.В. Ломоносова

Механико-математический факультет

На правах рукописи

УДК 519.112.4+519.174

+519.176+519.179.4

Рубанов Олег Игоревич

ЭКСТРЕМАЛЬНЫЕ СВОЙСТВА ДИСТАНЦИОННЫХ

ГРАФОВ

Специальность 01.01.09 — «дискретная математика и математическая кибернетика»

Диссертация на соискание учёной степени кандидата физико-математических наук

Научный руководитель:

д.ф.-м.н. А.М. Райгородский Москва – Содержание Обозначения Введение 1 История вопроса и формулировки результатов 1.1 История вопроса........................... 1.2 Нижние оценки хроматических чисел трёхмерных графов расстояний с запретами на клики................. 1.3 Нижние оценки хроматических чисел графов расстояний с запретами на клики в растущей размерности........... 1.3.1 Результаты с одним запрещённым расстоянием..... Сравнение оценок clique () в теоремах 4, 5, 6 и 7....

1.3.2 1.3.3 Результаты с несколькими запрещёнными расстояниями 1.3.4 Таблицы результатов теоремы 8.............. 2 Хроматические числа трёхмерных графов расстояний без тетраэдров и треугольников 2.1 Доказательство теоремы 2..................... 2.2 Доказательство теоремы 3..................... 2.2.1 Основная часть доказательства теоремы 3........ 2.2.2 Доказательство предложения 2.............. Построение графа «шевелением»: вспомогательные 2.2. леммы............................ 2.2.4 Процедура «шевеления».................. 3 Асимптотика хроматических чисел графов расстояний с несколькими запрещёнными расстояниями и без больших клик при росте размерности пространства 3.1 Доказательство теоремы 6..................... 3.2 Доказательство теоремы 7..................... 3.3 Доказательство теоремы 8..................... 3.4 Небольшой комментарий к теореме 8............... 3.5 Решение экстремальной задачи................... Список литературы Обозначения R — -мерное евклидово пространство x, y — скалярное произведение векторов x и y |x|, | | — модуль вектора x, 0 — вектор из начала координат в точку E — математическое ожидание случайной величины P() — вероятность события.

1 — глава 1.2 — раздел 2 главы 1.2.3 — пункт 3 раздела 2 главы Введение В работе изучаются классы графов расстояний с несколькими специальными свойствами. Задача данной работы — найти графы расстояний с большим хроматическим числом и без больших клик. Граф расстояний — это граф, вершинами которого являются точки некоторого метрического пространства, а рёбра проведены между теми и только теми вершинами, расстояние между которыми равно некоторому фиксированному числу (так называемое «запрещённое расстояние»). Под хроматическим числом понимается минимальное количество цветов, в которые можно покрасить вершины графа так, чтобы любые две вершины, соединённые ребром, были покрашены в разные цвета. Клика — это набор вершин, попарно соединённых рёбрами (другими словами, полный подграф). Рассматриваются как графы расстояний с одним, так и с несколькими запрещёнными расстояниями.

Задача тесно связана с задачей нижней оценки хроматических чисел пространств. Хроматическим числом метрического пространства называется минимальное количество цветов, в которые можно покрасить все точки этого пространства так, чтобы никакие две точки одного цвета не находились на единичном расстоянии друг от друга. Обобщением этой задачи является задача нахождения хроматического числа пространства с запрещёнными расстояниями. В этом случае вершины не должны быть одного цвета, если расстояние между ними запрещённое.

Графы расстояний как с одним, так и с несколькими запрещёнными расстояниями естественным образом дают нижнюю оценку хроматического числа соответствующего пространства, поскольку если вершины графа нельзя покрасить в цветов правильным образом, то и все точки метрического пространства (а множество вершин графа — это подмножество точек метрического пространства) тоже нельзя покрасить правильным образом. Именно нижние оценки хроматических чисел графов расстояний с определёнными свойствами и будут основным объектом исследования в этой работе.

Проблема хроматического числа пространства впервые была озвучена Э. Нельсоном в 1950 году, который пришёл к ней, изучая проблему четырёх красок (в своей книге [1] А. Сойфер приводит небольшое исследование истории вопроса, включая свидетельства самого Э. Нельсона и его профессоров, однако долгое время вопрос авторства этой задачи оставался открытым). Э. Нельсон сформулировал её для случая плоскости.

Своей популярностью задача во многом обязана Г. Хадвигеру, П. Эрдёшу, М. Гарднеру и братьями Л. и В. Мозерам. Поэтому в литературе проблема получила название проблемы Нельсона–Хадвигера или Нельсона–Эрдёша– Хадвигера.

Мы поговорим про результаты в этой области более подробно в основной части работы, а здесь заметим лишь, что для проблемы одного запрещённого расстояния в R2 доказано только, что хроматическое число (обозначаемое образом, не известны точные оценки для пространств больших размерностей.

Получено, что в асимптотике хроматическое число растёт экспоненциально в зависимости от размерности пространства, но точное значение основания экспоненты также не определено до сих пор1.

В 1976 году П. Эрдёш (см. [2]) поставил вопрос: существует ли на плоскости граф расстояний с хроматическим числом четыре и не содержащий треугольников? Надо сказать, что П. Эрдёш предполагал, что ответ будет отрицательным. Однако эта задача была решена (с положительным ответом) Н. Уормалдом (см. [3]), а позднее — П. О’Доннеллом и Р. Хохбергом (см.

[4]) в более общей постановке. В 2000 году П. О’Доннелл показал, что для произвольного наперед заданного числа можно построить граф расстояний на плоскости без циклов длины, меньшей (размер кратчайшего простого цикла в графе называется обхватом этого графа).

Подробнее об этом будет сказано в основной части работы, заметим лишь, что на данный момент известно, что (1.239 + (1)) (R ) (3 + (1)).

П. Эрдёш не случайно задал вопрос именно таким образом. Наличие треугольника естественно повышает хроматическое число графа до трёх, поэтому можно предположить, что наличие треугольников упрощает построение графов с большим хроматическим числом. Аналогично, в больших размерностях бывают симплексы (в нашем случае симплексы и клики — это одно и то же) больших размеров, поэтому можно ожидать, что в примерах графов с большим хроматическим числом содержатся клики большого размера. Таким образом, естественным обобщением задачи П.

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

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

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

[5]). В больших же размерностях борьба идёт за улучшение основания экспоненты в асимптотике нижней оценки хроматического числа. К примеру, А.М. Райгородскому в 2000 году (см. [6]) удалось улучшить нижнюю оценку (R ) с (1.207... + (1)) до (1.239... + (1)) при.

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

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

Глава История вопроса и формулировки результатов 1.1 История вопроса Прежде чем приступить к освещению истории вопроса и основных результатов данной работы, мы определим основные объекты исследования, которые необходимы для этого описания.

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

Определение 1. Графом = (, ) называется пара множеств и, где — это произвольное множество1, а — это некоторое множество пар элементов 2. Элементы множества называются вершинами, а элементами множества называются рёбрами.

Определение 2. Хроматическим числом метрического пространства M называется минимальное такое число, что множество M можно разбить Хотя в большинстве случаев рассматриваются конечные множества.

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

что любые два элемента этого пространства, находящиеся на единичном расстоянии, находятся в разных подмножествах. То есть если |1 2 | = 1 и 1, то 2. Обозначается хроматическое число (M).

Определение 3. Хроматическим числом графа = (, ) называется минимальное такое число, что множество вершин можно разбить на непересекающихся подмножеств = 1 2 · · · так, что любые две вершины графа, соединённые ребром, находятся в разных подмножествах.

Иными словами, если {1, 2 } и 1, то 2. Обозначается хроматическое число графа ().

Подмножества, на которые разбиваются множества точек пространства или вершин в определениях 2 и 3, соответственно, часто называются «цветами». Отсюда и пошло название «хроматического числа» ( погречески — «цвет»).

Несложно заметить, что два определения очень похожи друг на друга.

Действительно, если в качестве множества вершин графа в определении взять множество точек пространства M, а в качестве его рёбер — те пары точек, расстояние между которыми равно единице, то получится в точности определение 2.

Хроматические числа графов изучались ещё, по крайней мере, полтора века назад, но точное происхождение термина проследить сейчас сложно.

Поначалу ими занимались в связи с проблемой пяти красок, а впоследствии — проблемой четырёх красок (см., например, [7]). Именно когда Э. Нельсон размышлял над проблемой четырёх красок, ему пришла идея рассмотреть проблему хроматического числа плоскости. Это было в 1950 году, и тогда же он показал, что это хроматическое число не меньше четырёх, а Д. Исбеллу, с которым он обсуждал эту проблему, удалось показать, что оно не превосходит семи. Эти результаты, однако, ими опубликованы не были. Подробное исследование истории этого вопроса с письмами и свидетельствами участников обсуждения проделано А. Сойфером в его книге [1].

Также достаточно легко видеть, что хроматическое число прямой R равно двум ((R) = 2). Действительно, достаточно для всех целых раскрасить интервалы вида [2, 2 + 1) в белый цвет, а интервалы вида [2 + 1, 2 + 2) — в чёрный. Как это ни удивительно, оценки для хроматического числа плоскости так и не были улучшены со времени формулировки проблемы, и таким образом, Для доказательства нижних оценок -мерного евклидова пространства R чаще всего прибегают к построению конечных графов, вершинами которых являются точки пространства, а рёбрами — точки, находящиеся на единичном расстоянии друг от друга. Очевидно, что если хроматическое число такого графа равно, то хроматическое число соответствующего евклидова пространства не меньше. Действительно, в противном случае все точки пространства R, а в частности, точки, соответствующие вершинам графа, можно было бы покрасить в 1 цвет. Никакие из них, находящиеся на единичном расстоянии друг от друга (то есть, соединённые ребром), не покрашены в один цвет, а значит, хроматическое число графа не превосходило бы 1. В результате, такие графы очень удобны для получения нижних оценок хроматического числа. Они называются «геометрическими».

Определение 4. Геометрическим графом называется такое расположение графа (, ) в евклидовом пространстве, что множество его вершин является подмножеством точек евклидова пространства ( R ), а рёбра представлены отрезками, соединяющими соответствующие вершины.

Нас будет интересовать более конкретный класс геометрических графов.

А именно, речь пойдёт о графах единичных расстояний и графах расстояний с запрещёнными расстояниями.

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

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

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

Кроме того, в 1959 году П. Эрдёш (см. [9]) доказал красивый и довольно неожиданный факт.

числа. Тогда существует граф, у которого хроматическое число больше, а длина минимального простого цикла больше.

хроматическим числом () и обхватом () (длиной кратчайшего цикла).

Это соображение привело П. Эрдёша к вопросу, возможно ли построение графа, подобного Мозеровскому веретену, то есть такого графа единичных расстояний на плоскости, чтобы с одной стороны его хроматическое число равнялось четырём, а с другой — чтобы он не содержал треугольников. Он Граф назван так в честь братьев Л. и В. Мозеров, которые использовали его в своей работе [8]. В этой статье они показывают, что это минимальный (в плане количества вершин) пример графа единичных расстояний на плоскости с хроматическим числом четыре.

задал этот вопрос в 1976 году в [2], а затем поставил более общий вопрос про существование графа расстояний c () = 4 и () для любого наперед заданного. Надо сказать, что сам П. Эрдёш не ожидал, что у задачи будет положительное решение.

Уже в 1979 году Н. Уормалд (см. [3]) показал, что существует граф с обхватом пять и с хроматическим числом четыре. Позднее, в 1999 году в своей кандидатской диссертации (а также в опубликованных на год позже статьях [10] и [11]) П. О’Доннелл показал, что для любого наперёд заданного числа существует граф единичных расстояний с обхватом и хроматическим числом четыре.

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

О’Доннеллу и Р. Хохбергу удалось построить пример графа без треугольников на 23 вершинах4, который приведён на рисунке 1.2.

Модификация этого графа пригодится нам при построении графа без треугольников в трёхмерном пространстве.

В данной диссертации рассматривается обобщение задачи, поставленной П. Эрдёшем, на случай многомерных пространств. А именно, исследуется следующая задача.

Задача 1. В -мерном евклидовом пространстве построить граф с как можно большим хроматическим числом (в идеале — равном хроматическому числу этого пространства) без клик как можно меньшего размера.

На самом деле, эту задачу можно подразделить на две задачи: построение примеров в пространствах малой размерности и исследование асимптотики хроматического числа при росте размерности пространства.

В дальнейшем нам потребуется определение кликового числа.

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

подмножества, все вершины которого соединены друг с другом ребром.

Обозначается кликовое число ().

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

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

(R1 ) = 2. Этот результат очевиден и уже был обсуждён во Введении.

4 7. Оба результата довольно простые. Доказательства их можно найти в работах [8], [12] и в брошюре [13]. Заметим, в частности, что каждый из приведённых выше на рисунках 1.1 и 1.2 графов также является доказательством нижней оценки.

6 15. Нижняя оценка принадлежит О. Нечуштану (см. [5]), а верхняя — Д. Кулсону (см. [14]).

7 54. Нижняя оценка принадлежит К. Кантвеллу (см. [15]) и Л.Л. Иванову (см. [16]), а верхняя – Г. Тоту и Р. Радойчичу (см. [17]).

(1.239... + (1)) (R ) (3 + (1)). Нижняя оценка принадлежит А.М. Райгородскому (см. [6]), а верхняя — Д. Ларману и К.А.

Роджерсу (см. [18]). Заметим, что приведенная нижняя оценка является модификацией первоначальной экспоненциальной оценки П. Франкла и Р.М. Уилсона, имевшей вид (R ) (1.207... + (1)) (см. [19]).

Таким образом, мы видим, что с ростом размерности хроматическое число пространства растет экспоненциально.

Нас интересуют обобщения задачи П. Эрдёша на случай размерности 3. Разумеется, здесь речь идет о построении графов с хроматическим числом, максимально близким к наибольшему из известных. Так, в размерности три имеет смысл говорить о хроматическом числе пять или шесть. В растущей размерности правильным аналогом четверки служит экспонента.

Ранее мы ввели определение графа единичных расстояний, который изначально рассматривался в связи с задачей хроматического числа плоскости. Аналогичным образом можно рассмотреть задачу хроматического пространства с несколькими запрещёнными расстояниями. Обобщать эту задачу можно несколькими способами. Действительно, в случае с одним запрещённым расстоянием было не важно, запрещать расстояние 1 или некоторое другое расстояние = 1. Если же мы запретим, скажем, два расстояния, то хроматическое число может различаться в зависимости от соотношения между запрещёнными расстояниями. Эта же проблема с определением переносится и на графы расстояний с несколькими запрещёнными расстояниями, которые мы определяем ниже.

Определение 7. Графом с запрещёнными расстояниями называется геометрический граф = (, ), для которого существует такое множество R+ из элементов, что если {1, 2 }, то |1 2 |.

Определение 8. Хроматическим числом евклидова пространства R с множеством запретов (обозначается (R, )) называется минимальное такое число, что множество точек R можно представить в виде объединения непересекающихся подмножеств R = 1 2 · · · так, что любые две точки, расположенные на расстоянии друг от друга, не лежат в одном и том же множестве.

Как уже было сказано, даже если мы знаем размер и даже если он равен двум, хроматические числа (R, ) могут быть достаточно разными.

Мы рассмотрим задачу о наибольшем хроматическом числе для данного количества запретов:

Величину (R ; ) рассматривал еще П. Эрдёш, который знал, например, что Подобные результаты описаны в обзоре [20].

Аккуратно подсчитанные нижние оценки для хроматических чисел (R ; ), коль скоро, впервые были приведены в статье [21]. Там было доказано, что Кроме того, там была установлена общая нижняя оценка, справедливая даже в случае любой функции = ():

Константы 1, 2 были чрезвычайно маленькими (порядка 210000 ), поэтому позже указанный результат уточнялся (см. [22]). А в работах [23] и [24] была развита оптимизационная техника, позволившая найти оптимальные (в рамках некоторого метода) константы типа 1.239 и 1.439. Перечислим эти результаты:

Список можно продолжать и дальше.

Что касается верхних оценок величин (R ; ), то ничего лучшего не придумано, нежели оценка мгновенно вытекающая из неравенства (R ; 1) (3 + (1)), которое мы уже цитировали выше. Понятно, что с ростом эта оценка катастрофически удаляется от имеющихся нижних оценок. Впрочем, по-видимому, именно верхние оценки подлежат дальнейшему усилению.

Как и в предшествующей части работы, нас будут интересовать графы расстояний с ограниченным кликовым числом. При этом теперь наши графы расстояний — это подграфы в графах G = (V, E ), у которых Основным объектом нашего исследования в задаче с несколькими запрещёнными расстояниями будет величина clique (, ) = sup{ : функция = () такая, что lim () = и мощности и в G, у которого () <, () трёхмерных графов расстояний с запретами В главе 2 мы приведём примеры таких двух графов единичных расстояний с хроматическим числом пять в трёхмерном пространстве, что в первом примере граф не содержит тетраэдров, а во втором — треугольников. А именно, мы докажем следующие теоремы.

Теорема 2. В пространстве R3 существует граф расстояний, имеющий хроматическое число пять и не содержащий тетраэдров.

Теорема 3. В пространстве R3 существует граф расстояний без треугольников (циклов длины три) и с хроматическим числом пять.

Результат теоремы 2 был опубликован в нашей статье [32].

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

1.3 Нижние оценки хроматических чисел графов расстояний с запретами на клики в растущей 1.3.1 Результаты с одним запрещённым расстоянием Для удобства формулировки результатов в этой части диссертации мы введём обозначения clique ():

clique () = sup : функция = (), такая, что lim () = Разумеется, для некоторых эти величины могут оказаться меньше единицы, и тогда смысла в их рассмотрении нет. Основная цель настоящей работы состоит в том, чтобы доказать неравенства clique () > 1 для всех и, более того, найти оптимальные значения в правых частях этих неравенств.

Как уже было сказано, без запрета на клики лучшая известная нижняя оценка хроматического числа — это (1.239... + (1)), поэтому можно ожидать, что 1 clique () 1.239... и lim clique () = 1.239....

В нашей совместной работе [33] Е. Е. Демёхин доказал следующую теорему.

Теорема 4 (Е.Е. Демёхин). Имеет место оценка В той же работе он получил и оценку на clique () для произвольного с помощью границ равновесных кодов.

Пусть, далее, и — произвольные вещественные числа, удовлетворяющие ограничениям Тогда В серии работ [33], [34], [35], [36] нами получена нижняя оценка величины clique (), которая при больших работает лучше оценки из теоремы 5.

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

Наиболее эффективным окажется здесь вероятностный метод (см. [25], [26], [27]).

А именно, в главе 3 мы доказываем теоремы, дающие общий рецепт получения «оптимальных» оценок для величин clique ().

произвольное вещественное число. Положим Рассмотрим Теорема 7. Пусть 5 — произвольное натуральное число, а 1, 1 — произвольные вещественные числа, удовлетворяющие ограничениям Положим Пусть, далее, Рассмотрим Положим = (1, 1, ) = inf, если =, и = 1 иначе. Тогда clique () Нетрудно проверить, что в условиях теоремы 6 величина 0 всегда меньше величины 1, а потому множество определено корректно. В конечном счете имеем Аналогичный комментарий верен и относительно теоремы 7. Правда, там не столь очевидно неравенство 0 < 1 ; доказательство этого неравенства можно найти в [28]. В итоге Сравнение оценок clique() в теоремах 4, 5, 6 и 1.3. Мы собрали оптимальные результаты в таблицах 1.1 и 1.2, которые мы приводим ниже. В таблице 1.1 в первом столбце указано, во втором и третьем — 1, 1 (параметры из теоремы 7), в четвертом — наилучшая оценка в теореме 7. В таблице 1.2 в первом столбце указано, во втором столбце указано 0 (параметр из теоремы 6), в третьем — наилучшая оценка в теореме 6, в четвёртом для сравнения ещё раз приведена наилучшая оценка в теореме 7, в пятом — лучшая из оценок теорем 6 и 7; при этом в третьем и четвёртом столбцах таблицы 1.2 жирным шрифтом выделена та оценка, которая попала в пятый столбец. Все оценки даны с восемью точными знаками после запятой.

6 0.00071800 0.08438940 1. 7 0.00270696 0.12703569 1. 8 0.00553133 0.15711445 1. 9 0.00869977 0.17904575 1. 10 0.01190629 0.19555639 1. 11 0.01498920 0.20833110 1. 12 0.01787410 0.21844807 1. 13 0.02053497 0.22662152 1. 14 0.02297102 0.23333932 1. 15 0.02519380 0.23894375 1. 16 0.02722013 0.24368069 1. 17 0.02906839 0.24773059 1. 18 0.03075664 0.25122837 1. 19 0.03230179 0.25427658 1. 20 0.03371912 0.25695447 1. 25 0.03931602 0.26656957 1. 30 0.04321023 0.27249456 1. 35 0.04605883 0.27649512 1. 40 0.04822699 0.27937171 1. 45 0.04992995 0.28153709 1. 50 0.05130175 0.28322476 1. 55 0.05242980 0.28457649 1. 100 0.05755871 0.29034354 1. 1000 0.06326998 0.29611686 1. 10000 0.06384354 0.29666283 1. 100000 0.06390091 0.29671712 1. Таблица 1.1: Результаты в теореме 5 0.02825291 1.00297305 1.00280720 1. 6 0.09659179 1.01838640 1.01694361 1. 7 0.14157882 1.03626539 1.03395854 1. 8 0.17051644 1.05242870 1.05011426 1. 9 0.19035277 1.06632451 1.06460594 1. 10 0.20472195 1.07816823 1.07739346 1. 11 0.21558694 1.08829570 1.08864080 1. 12 0.22408139 1.09701591 1.09855184 1. 13 0.23090096 1.10458387 1.10731983 1. 14 0.23649470 1.11120346 1.11511348 1. 15 0.24116490 1.11703654 1.12207552 1. 16 0.24512232 1.12221184 1.12832523 1. 17 0.24851823 1.12683247 1.13396195 1. 18 0.25146404 1.13098160 1.13906849 1. 19 0.25404355 1.13472693 1.14371408 1. 20 0.25632099 1.13812400 1.14795689 1. 25 0.26461281 1.15125524 1.16461196 1. 30 0.26984084 1.16020045 1.17618197 1. 35 0.27343793 1.16668123 1.18467380 1. 40 0.27606415 1.17159101 1.19116666 1. 45 0.27806578 1.17543859 1.19628994 1. 50 0.27964192 1.17853468 1.20043462 1. 55 0.28091520 1.18107971 1.20385612 1. 100 0.28647009 1.19266305 1.21959032 1. 1000 0.29226811 1.20564840 1.23753236 1. 10000 0.29283085 1.20696080 1.23936294 1. 100000 0.29288697 1.20709218 1.23954636 1. Таблица 1.2: Результаты в теореме 6 и сравнение с теоремой в третьей колонке таблицы 1.2, очевидно, стремится к 1.207..., а число в четвертой колонке становится все ближе к 1.239... Это и суть константы из работ [19] и [6], в которых получены самые сильные из известных нижние оценки для (R ) (см. раздел 1.1). Таким образом, в асимптотике по наши теоремы 6 и 7 дают очень сильные результаты.

Результат теоремы 5 Е.Е. Демёхина в указанном смысле слабее. Оценки в теореме 5 не стремятся ни к 1.207..., ни к 1.239.... Их пределом является величина (см. [33]) В то же время при малых теорема 5 всё-таки лучше. А именно, она сильнее теорем 6 и 7 при всех 13.

Таким образом, в этой области подход теоремы 4 становится незаменим.

Как и в пункте 1.3.1, нас будут интересовать графы расстояний с ограниченным кликовым числом. При этом теперь наши графы расстояний — это подграфы в графах G = (V, E ), у которых Основным объектом нашего исследования будет величина clique (, ) = sup : функция = (), такая, что lim () = Разумеется, clique (, 1) = clique (), так что тут мы сконцентрируемся на случаях 2.

В [33] нам удалось доказать следующую теорему.

натуральное число. Рассмотрим симплекс Для каждого v положим Тогда Следствием из теоремы является утверждение о том, что Теорему 8 мы докажем в разделе 3.3.

1.3.4 Таблицы результатов теоремы В таблицах 1.3, 1.4, 1.5, 1.6 и 1.7, которые мы приводим ниже, отражены от 1 до 20. Для каждого величина меняется в пределах 1 — 20, и при величина искомой константы стремится ровно к той величине, полученной в [24], которая для данного выписана в разделе 1.1. При > начинаются небольшие расхождения, связанные с тем, что мы не брали > 15. Последнее обстоятельство обусловлено, в свою очередь, нехваткой мощности персонального компьютера. Если написать программу, делающую распределенные вычисления, и запустить ее на кластере, то можно будет брать порядка 20, а это и есть та величина, которую использовали авторы работы [24].

Стоит отметить, что есть три клетки в первой таблице, где стоит точная единица. Это соответствует тому, что наш метод дает экспоненциальные оценки хроматического числа не при всех.

3 1.000000 0 1.000000 0 1.001271 1 1. 4 1.000000 0 1.016665 1 1.055782 2 1. 5 1.002973 1 1.058718 2 1.122702 3 1. 6 1.018386 1 1.099706 2 1.180723 3 1. 7 1.036265 1 1.134785 2 1.229070 4 1. 8 1.052429 1 1.164501 3 1.269349 4 1. 9 1.066325 1 1.189781 3 1.303175 4 1. 10 1.078168 1 1.211347 3 1.331877 4 1. 11 1.088641 2 1.229900 3 1.356502 5 1. 12 1.098552 2 1.245997 3 1.377831 5 1. 13 1.107320 2 1.260076 3 1.396467 5 1. 14 1.115113 2 1.272482 3 1.412880 5 1. 15 1.122076 2 1.283491 3 1.427439 5 1. 16 1.128325 2 1.293319 3 1.440437 5 1. 17 1.133962 2 1.302145 3 1.452111 5 1. 18 1.139068 2 1.310113 3 1.462651 5 1. 19 1.143714 2 1.317370 4 1.472213 5 1. 20 1.147957 2 1.324001 4 1.480927 5 1. 25 1.164612 2 1.349947 4 1.514987 5 1. 50 1.200435 2 1.405522 4 1.587854 6 1. 100 1.219590 2 1.435237 4 1.626797 6 1. 1000 1.237532 2 1.463131 4 1.663355 6 1. 10000 1.239363 2 1.465982 4 1.667092 6 1. 100000 1.239546 2 1.466267 4 1.667467 6 1. 1000000 1.239565 2 1.466296 4 1.667504 6 1. 10000000 1.239567 2 1.466299 4 1.667508 6 1. 100000000 1.239567 2 1.466299 4 1.667508 6 1. 1000000000 1.239567 2 1.466299 4 1.667508 6 1. Таблица 1.3: Оценки clique (, ) для от 1 до 100 1.955191 10 2.099939 12 2.235094 13 2. 1000 2.007171 10 2.158976 12 2.300865 14 2. 10000 2.012487 10 2.165016 12 2.307597 14 2. 100000 2.013020 10 2.165622 12 2.308271 14 2. 1000000 2.013073 10 2.165682 12 2.308339 14 2. 10000000 2.013079 10 2.165688 12 2.308346 14 2. 100000000 2.013079 10 2.165689 12 2.308346 14 2. 1000000000 2.013079 10 2.165689 12 2.308346 14 2. 5 1.414155 15 1.451537 14 1.486840 13 1. 6 1.539514 13 1.585569 15 1.629130 15 1. 7 1.642088 13 1.695284 15 1.745668 14 1. 8 1.726939 15 1.786094 14 1.842183 15 1. 9 1.798033 14 1.862220 14 1.923136 15 1. 10 1.858336 14 1.926823 15 1.991869 15 2. 11 1.910066 14 1.982264 15 2.050879 15 2. 12 1.954893 14 2.030325 15 2.102051 15 2. 13 1.994088 15 2.072362 15 2.146824 15 2. 14 2.028638 15 2.109426 15 2.186312 15 2. 15 2.059313 15 2.142341 15 2.221388 15 2. 16 2.086724 15 2.171761 15 2.252745 15 2. 17 2.111361 15 2.198210 15 2.280941 15 2. 18 2.133624 15 2.222112 15 2.306427 15 2. 19 2.153836 15 2.243818 15 2.329573 15 2. 20 2.172268 15 2.263614 15 2.350687 15 2. 25 2.244444 15 2.341157 15 2.433418 15 2. 50 2.399520 15 2.507905 15 2.611462 15 2. 100 2.482803 15 2.597533 15 2.707238 15 2. 1000 2.561264 15 2.682017 15 2.797565 15 2. 10000 2.569299 15 2.690671 15 2.806820 15 2. 100000 2.570104 15 2.691539 15 2.807748 15 2. 1000000 2.570185 15 2.691626 15 2.807841 15 2. 10000000 2.570193 15 2.691634 15 2.807850 15 2. 100000000 2.570194 15 2.691635 15 2.807851 15 2. 1000000000 2.570194 15 2.691635 15 2.807851 15 2. 4 1.359334 14 1.380954 14 1.401621 11 1. 5 1.552185 15 1.582609 15 1.611740 14 1. 6 1.709944 14 1.747658 15 1.783823 15 1. 7 1.839321 15 1.883109 15 1.925148 15 1. 8 1.946605 15 1.995502 15 2.042490 15 2. 9 2.036690 15 2.089929 15 2.141126 15 2. 10 2.113249 15 2.170213 15 2.225028 15 2. 11 2.179032 15 2.239224 15 2.297174 15 2. 12 2.236116 15 2.299129 15 2.359822 15 2. 13 2.286091 15 2.351589 15 2.414698 15 2. 14 2.330190 15 2.397892 15 2.463144 15 2. 15 2.369380 15 2.439049 15 2.506216 15 2. 16 2.404429 15 2.475864 15 2.544751 15 2. 17 2.435956 15 2.508985 15 2.579425 15 2. 18 2.464462 15 2.538937 15 2.610785 15 2. 19 2.490359 15 2.566152 15 2.639283 15 2. 20 2.513987 15 2.590985 15 2.665291 15 2. 25 2.606628 15 2.688378 15 2.767316 15 2. 50 2.806291 15 2.898425 15 2.987496 15 3. 100 2.913856 15 3.011661 15 3.106272 15 3. 1000 3.015398 15 3.118605 15 3.218494 15 3. 10000 3.025809 15 3.129572 15 3.230004 15 3. 100000 3.026852 15 3.130671 15 3.231158 15 3. 1000000 3.026957 15 3.130781 15 3.231274 15 3. 10000000 3.026967 15 3.130792 15 3.231285 15 3. 100000000 3.026968 15 3.130793 15 3.231287 15 3. 1000000000 3.026968 15 3.130793 15 3.231287 15 3. 3 1.174400 15 1.183687 14 1.192635 15 1. 4 1.440444 15 1.458746 15 1.476392 15 1. 5 1.666601 15 1.692530 15 1.717569 15 1. 6 1.852077 15 1.884404 15 1.915663 15 1. 7 2.004623 15 2.042324 15 2.078817 15 2. 8 2.131437 15 2.173685 15 2.214612 15 2. 9 2.238145 15 2.284273 15 2.328987 15 2. 10 2.328989 15 2.378460 15 2.426437 15 2. 11 2.407162 15 2.459535 15 2.510348 15 2. 12 2.475082 15 2.529998 15 2.583296 15 2. 13 2.534608 15 2.591766 15 2.647258 15 2. 14 2.587183 15 2.646334 15 2.703775 15 2. 15 2.633943 15 2.694875 15 2.754058 15 2. 16 2.675793 15 2.738325 15 2.799075 15 2. 17 2.713460 15 2.777438 15 2.839604 15 2. 18 2.747537 15 2.812828 15 2.876280 15 2. 19 2.778511 15 2.844999 15 2.909622 15 2. 20 2.806784 15 2.874368 15 2.940064 15 3. 25 2.917753 15 2.989663 15 3.059597 15 3. 50 3.157521 15 3.238917 15 3.318147 15 3. 100 3.287017 15 3.373608 15 3.457932 15 3. 1000 3.409460 15 3.501007 15 3.590190 15 3. 10000 3.422024 15 3.514081 15 3.603765 15 3. 100000 3.423283 15 3.515392 15 3.605126 15 3. 1000000 3.423409 15 3.515523 15 3.605262 15 3. 10000000 3.423422 15 3.515536 15 3.605276 15 3. 100000000 3.423423 15 3.515538 15 3.605277 15 3. 1000000000 3.423423 15 3.515538 15 3.605278 15 3. Глава Хроматические числа трёхмерных графов расстояний без тетраэдров и треугольников 2.1 Доказательство теоремы В главе 1 на рисунке 1.1 мы показали граф, который называется «Мозеровское веретено». Это граф, который состоит из двух пар равносторонних треугольников. Треугольники в каждой паре имеют одну общую сторону, образуя так называемую «иглу». Две «иглы» расположены таким образом, что один «конец» каждой иглы совпадает с «концом» другой, а вторые «концы» удалены на расстояние 1 друг от друга.

Очевидно, что хроматическое число Мозеровского веретена равно четырём.

удовлетворяющего условию теоремы. Введём в пространстве декартову систему координат, зафиксируем плоскость = 0. Отметим точку с координатами ( 1, 0, 0), точку с координатами ( 1, 0, 0) и точку c координатами (0, 1, 0). Затем отметим точку, удалённую на расстояние. И, наконец, отметим на оси ординат точку, симметричную точке Далее, построим пары точек 1 и 2, 1 и 2, которые удалены Заметим, что точки 1 и 2 удалены от точек, и на расстояние 1, а точки 1 и 2 удалены от точек, и на расстояние 1.

Кроме того, построим точку, удалённую от точек, и на расстояние (0, 0, 0) — это проекция точки на плоскость = 0. Отметим также, что | | = 2. На рисунках 2.1 и 2.2 изображены проекции описанного графа на плоскости = 0 и = 0.

Заметим, что вершины,, 1, 2, 1, 2 и образуют Мозеровское веретено (две «иглы»:, 1, 2, и, 1, 2, ; || = 1). Также отметим, что точка удалена на расстояние 1 от точек, и, а точка удалена на расстояние 1 от точек 1, 2, 1 и 2. Таким образом, каждая точка Мозеровского веретена соединена ребром либо с, либо c.

Перейдём к завершающему этапу построения. Вначале построим правильную четырёхугольную пирамиду со стороной 1. Она изображена на рисунке 2.3.

До полного графа на пяти вершинах четырёхугольной пирамиде «не достаёт» двух рёбер (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, и 2, 4, и небольшим перебором.

Теорема доказана. Добавим, что полученный граф имеет 19 вершин и ребра.

2.2 Доказательство теоремы 2.2.1 Основная часть доказательства теоремы В нашей конструкции в качестве одной из составных частей мы будем использовать модификацию графа расстояний, построенного П. О’Доннеллом и Р. Хохбергом (см. [4], сам граф изображён на рисунке 1.2). Мы обозначим его (см. рисунок 2.4).

представляют вершины, а отрезки и дуги, как сплошные, так и пунктирные, которые их соединяют, представляют рёбра. Граф состоит из 4-цикла {1, 2, 3, 4 } и 5-циклов 1, 2, 1 и 2, которые представлены сплошными линиями, а также нескольких рёбер, которые проведены между этими циклами.

Лемма 1. Хроматическое число графа, изображённого на рисунке 2.4, равняется четырём. Кроме того, он не содержит треугольников.

Доказательство. Утверждение об отсутствии треугольников очевидно.

Достаточно заметить, что граф состоит из 4-цикла {1, 2, 3, 4 } и 5-циклов 1, 2, 1 и 2, соединённых рёбрами, причём рёбра из одной вершины одного цикла никогда не ведут в соседние вершины другого.

Теперь докажем от противного, что покрасить вершины графа в три цвета нельзя. Предположим, что это удалось, тогда, поскольку вершины {1, 2, 3, 4 } образуют цикл, по крайней мере, одна из пар вершин {1, 3 } и {2, 4 } одноцветна. Без ограничения общности (картинка симметрична) будем считать, что это {1, 3 } и покрашены они в цвет 1. Тогда все вершины 1, кроме 5, покрашены в цвета 2 и 3. Значит, 5 смежна с вершинами обоих цветов, то есть она может быть покрашена только в цвет 1. Теперь заметим, что все вершины 1 соединены с одной из вершин цвета 1, а именно {1, 3, 5 }, следовательно, они могут быть только цвета 2 и 3. Но покрасить нечётный цикл в 2 цвета невозможно. Противоречие, и лемма 1 доказана.

В своей работе [4] П. О’Доннелл и Р. Хохберг разместили дистанционный граф, изоморфный построенному нами (за исключением того, что в их работе вершины 5 и 5 совпадают), на плоскости, и таким образом привели наименьший известный пример графа, являющегося ответом на вопрос П.

Эрдёша о существовании графа на плоскости с хроматическим числом четыре и без циклов.

Теперь мы построим граф, который является надграфом. Как мы уже выяснили, () = 4, поэтому множество вершин можно разбить на четыре подмножества 1, 2, 3, 4, так что никакие две вершины из одного подмножества не соединены ребром. Возьмём одну из таких раскрасок (разбиений множества вершин на четыре подмножества). Теперь, чтобы получить граф, мы добавляем к графу четыре вершины 1, 2, 3, и для каждого {1, 2, 3, 4} соединяем ребрами со всеми вершинами из и только с ними. Одна из возможных раскрасок приведена на рисунке 2.5.

Полученный граф выглядит следующим образом:

Для данного графа верны следующие факты.

достаточно покрасить вершины 1, 2, 3 и 4 в пятый цвет, а остальные вершины в четыре цвета уже покрашены.

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

Основная идея дальнейших рассуждений содержится в предложении 1.

Предложение 1. Если в некоторой раскраске вершины 1, 2, 3 и 4 графа покрашены в один цвет, то для покраски всех его вершин использовано не менее пяти цветов.

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

Покажем теперь, что верна следующая лемма.

Лемма 2. Граф можно разместить в пространстве1 таким образом, что вершины 1, 2, 3 и 4 окажутся в одной точке.

Доказательство. Заметим, что для доказательства леммы достаточно разместить граф на сфере единичного радиуса, поскольку тогда можно будет поместить все точки 1, 2, 3 и 4 в центр сферы, расположенный в начале координат, соединив их с соответствующими точками на сфере. Ниже дан пример того, как это можно сделать.

Под «размещением графа = (, ) в пространстве» здесь и далее мы будем понимать сопоставление модифицированного геометрического графа обычному графу, то есть процедуру, при которой вершины выбираются из точек трёхмерного пространства в качестве вершин графа ( R3 ), а рёбра проводятся только между вершинами, расположенными на единичном расстоянии друг от друга. На этом этапе мы используем модифицированное определение графа расстояний. Модификация состоит в том, что мы не требуем, чтобы все вершины были различны и те и только те вершины, которые находятся на расстоянии 1, были соединены рёбрами.

Координаты точек округлены до шести знаков после запятой.

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

Рисунок 2.7: Расположение графа на единичной сфере Лемма 2 доказана.

Построенный дистанционный граф обладает следующими свойствами.

Минимальное расстояние между любыми двумя различными вершинами Максимальное расстояние между вершинами, имеющими общего соседа, не превосходит 3 0.0025.

Построенный граф и его размещение в пространстве (обозначим его 0 ) станут составными блоками графа, который является примером для доказательства теоремы. Граф устроен следующим образом. Рассмотрим множество из тринадцати вершин = {1, 2,..., 13 }. Теперь к каждому из 13 = 715 подмножеств из четырёх вершин добавим по копии графа таким образом, чтобы для каждых (1, 2, 3, 4 ) [1; 13] N, < : < вершины 1, 2, 3 и 4 и добавленный к ним граф 1 2 3 4 образовывали граф 1 2 3 4, изоморфный графу.

Если бы различные вершины могли находиться в одной точке при размещении графа в пространстве, то можно было бы расположить граф в пространстве, просто поместив все точки из в начало координат, а все графы 1 2 3 4 в точки с координатами, указанными выше. Однако нам требуется, чтобы эти разные вершины в пространстве соответствовали разным точкам. Далее мы покажем, как можно достичь этого некоторым «шевелением» вершин. Мы будем делать это в несколько шагов, при этом на каждом шаге граф, расположенный в пространстве, изоморфен графу, но расположение его в пространстве меняется. Обозначим текущее его расположение в пространстве (граф расстояний в обобщённом смысле – разрешается совпадение вершин) 0.

Шаг 1. Вначале мы разместим 13 копий графа, пронумерованных 1 2 3 4, на сфере единичного радиуса, воспользовавшись следующим предложением.

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

Предложение 2 будет доказано в пункте 2.2.2. Расстояние до вершин 1 2 3 4 от вершин множества по-прежнему равно 1, а о том, чтобы остальные вершины не совпадали и не возникало расстояния 1 между вершинами, которые не соединены ребром в графе, мы позаботились.

подграфам 1 2 3 4 графа, мы обозначим 1 2 3 4.

Шаг 2. Теперь мы «пошевелим» вершины 1, 2,..., 13 так, чтобы они перестали совпадать, сохраняя при этом все проведённые рёбра. Чтобы сделать это, мы поместим их в разные точки в малой окрестности начала координат. Строгое объяснение, как выбрать эту окрестность и окончательно построить граф, требуемый для доказательства теоремы, мы дадим в пунктах 2.2.3 и 2.2.4.

Лемма 3. Построенный граф расстояний в R3 удовлетворяет условиям теоремы, то есть его хроматическое число равно пяти и он не содержит треугольников.

Доказательство. Для доказательства леммы заметим, что покрасить граф в пять цветов не составляет труда. Достаточно покрасить все вершины в красный цвет. При этом мы знаем, что каждый из графов 1 2 3 4 красится в четыре не красных цвета. Покрасим каждый из этих графов в четыре цвета.

Вершины подграфа 1 2 3 4 соединены только друг с другом и с, таким образом, вершины одного цвета не соединены ребром, то есть нам удалось покрасить граф в пять цветов. Покажем теперь, что в нём нет треугольников и что его нельзя покрасить в четыре цвета.

В исходном графе не было треугольников. Мы не соединяли рёбрами два различных графа 1 2 3 4 и 1 2 3 4, поэтому треугольника, в котором есть вершины из двух различных подграфов 1 2 3 4, возникнуть не могло.

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

Покажем теперь, что граф нельзя покрасить в четыре цвета. Предположим противное и рассмотрим раскраску графа в четыре цвета. В множестве тринадцать вершин, значит по принципу Дирихле при покраске в четыре цвета по крайней мере четыре из них будут одного цвета. Без ограничения общности будем считать, что это 1, 2, 3 и 4 и покрашены они в красный цвет. Каждая вершина графа 1234 соединена с одной из вершин 1, 2, 3 и 4, а значит, не может быть покрашена в красный цвет. Получается, что граф 1234 покрашен в три цвета. Противоречие. Таким образом, покраска графа в четыре цвета невозможна.

В результате мы построили дистанционный граф в трёхмерном пространстве, хроматическое число которого равно пяти и который не содержит треугольников.

Теорема 3 доказана.

2.2.2 Доказательство предложения Доказательство. Вначале расположим все копии графа на сфере единичного радиуса с центром в начале координат в соответствии с координатами, приведёнными в доказательстве леммы 2. Затем повернём каждый из графов на некоторый угол вокруг оси так, чтобы никакие из вершин различных графов 1 и 2 не совпадали. Для каждого от 1 до обозначим угол, на который поворачивается граф, > 0, причём для каждого выберем +1 >. Обозначим также 1 = 1 и для всех от 2 до положим = 1.

Теперь покажем, что если выбрать углы 1, 2,..., достаточно малыми, то при этом никакие вершины из разных копий графа не совпадут. Действительно, при вращении вокруг оси могут совпасть только вершины, которые изначально находились на одной окружности в плоскости, перпендикулярной. Множество точек, куда данная точка может перейти при вращении вокруг оси, является окружностью, которая получается при пересечении плоскости, перпендикулярной и проходящей через точку, со сферой. Эту окружность мы обозначим. Однако, поскольку количество точек во всех копиях графах конечно, мы можем найти минимальное расстояние между точками, лежащими на одной окружности в плоскости, перпендикулярной. Таким образом, существует такое, что если для любого выполнено <, то никакие вершины из разных копий графа не совпадут.

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

Тогда для каждой вершины 1 множество точек, удалённых от на единичное расстояние, — это окружность. Для каждой вершины графа +1 окружность пересекается с максимум по двум точкам2. Поэтому для каждой пары и есть не более двух углов +1, при повороте на которые расстояние между этими вершинами равно единице. Всего количество таких пар конечно, значит в любой окрестности нуля можно найти угол +1, что при повороте на него все вершины графа +1 не находятся на расстоянии от всех уже отмеченных ранее вершин.

Построение графа «шевелением»: вспомогательные 2.2. Прежде чем перейти к непосредственному процессу «шевеления», мы докажем следующую лемму.

Лемма 4. Пусть 0, 0 и 0 — три точки в пространстве, такие что они не лежат на одной прямой и радиус окружности, описанной вокруг треугольника 0 0 0, меньше 1. Тогда положение каждой из двух точек 1 и 2, которые удалены от каждой из точек 1, 2 и 3 на расстояние 1, непрерывно зависит от положения точек 1, 2 и 3 в пространстве в некоторой окрестности точек 0, 0, 0. Другими словами, если координаты точек суть (1, 1, 1 ), (2, 2, 2 ) и (3, 3, 3 ), то координаты 1 и 2 — непрерывные функции от переменных 1, 1, 1, 2, 2, 2, 3, 3, 3 в некоторой 9-мерной окрестности точки (0, 1, 1, 0, 2, 2, 0, 3, 3 ).

Доказательство. Чтобы увидеть, что эта лемма верна, вначале заметим, как можно найти координаты 1 и 2. Во-первых, множество точек, равноудалённых от трёх данных точек, — это прямая, перпендикулярная плоскости 1 2 3 и проходящая через центр описанной окружности треугольника 1 2 3 :

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

Если нормализовать вектор так, чтобы у него был единичный модуль, то определяется с точностью до знака из теоремы Пифагора:

откуда мы имеем два возможных положения точки : 1 и 2, в случае, если радиус описанной окружности треугольника меньше 1 (| 1 | < 1). Наша задача — показать, что зависимость каждого элемента в этой конструкции от положения точек 1, 2, 3 непрерывна.

Покажем вначале, что центр окружности меняется непрерывно.

Обозначим радиус-векторы вершин треугольника := 01, := 02, := 03.

Тогда центр описанной окружности треугольника 1 2 3 можно найти по формуле:

Здесь обозначает площадь треугольника 1 2 3. Легко видеть, что все участвующие в формуле векторы непрерывно зависят от координат точек 1, 2, 3 (разности координат). Соответственно, скалярные произведения — тоже непрерывные функции своих компонентов, как и суммы и произведения.

Площадь треугольника 1 2 3 также непрерывно зависит от координат вершин. Единственная возможная проблема — это деление на ноль, но этого тоже не происходит в некоторой окрестности, поскольку вершины 1, 2 и не лежат на одной прямой. Мы показали, что = (1, 2, 3 ), : R R3 R3 R3 — это непрерывная функция в некоторой 9-мерной окрестности точки 1, 2, 3, удовлетворяющей условию леммы.

Теперь покажем, что вектор меняется непрерывно как функция от координат вершин 1, 2, 3. Действительно, этот вектор можно представить с помощью векторного произведения: если := [1 2, 1 3 ], то = Модуль не равен нулю в некоторой окрестности (0, 0, 0 ), и он непрерывно зависит от координат вектора, значит, для непрерывности достаточно, чтобы непрерывно зависел от (1, 2, 3 ), что выполнено.

непрерывно зависит от радиуса описанной окружности | 1 | = 1 2 3, а тот в свою очередь непрерывно зависит от координат (1, 2, 3 ), поскольку его можно найти из формулы где,, — это длины сторон треугольника. Поскольку у нас начальные точки общего положения, то знаменатель не обращается в ноль, то есть радиус тоже непрерывно зависит от координат (1, 2, 3 ) в некоторой окрестности (0, 0, 0 ). По теореме Кантора–Гейне отсюда, в частности, следует, что координаты точек 1 и 2 — равномерно непрерывные функции в некоторой окрестности (0, 0, 0 ).

По аналогии с леммой 4 можно сформулировать лемму, где есть больше степеней свободы в отношении положения точки.

Лемма 5. Пусть 0 и 0 — две точки в пространстве, расстояние между которыми меньше двух, но больше нуля. Также, пусть 0 — некоторая точка, такая, что |0 0 | = |0 0 | = 1. Определим множество O(1, 2 ) точек, которые удалены от каждой из точек 1 и 2 на расстояние 1. Тогда существует такая функция (1, 2 ), что (1, 2 ) O(1, 2 ) и непрерывно зависит от положения точек 1 и 2 в пространстве в некоторой окрестности точек 0 и 0 соответственно, причём (0, 0 ) = 0. Другими словами, если координаты точек суть (1, 1, 1 ) и (2, 2, 2 ), то координаты точки — непрерывные функции от переменных 1, 1, 1, 2, 2, 2 в некоторой 6-мерной окрестности точки Доказательство. Поскольку расстояние между 0 и 0 по условию меньше двух, множество точек O(1, 2 ), равноудалённых от них на единичное расстояние, является окружностью вращения вокруг оси, соединяющей точки 0 и 0. То же будет верно для точек 1 и 2 в некоторой окрестности 0 и 0, достаточно лишь выбрать окрестности так, чтобы расстояние между наиболее удалёнными точками из двух окрестностей было меньше двух, а между ближайшими — больше нуля. Заметим, что положение окружности O(1, 2 ) меняется непрерывно. Осталось лишь выбрать точку на этой окружности некоторым способом, чтобы её положение непрерывно зависело от положения Один из способов сделать это такой. Возьмём вектор 0, соответствующий направлению от оси 0 к вершине 0.3 Вектор 0 перпендикулярен оси 0 0, поэтому для точек 1 и 2 из некоторых окрестностей 0 и 0 вектор 0 не будет коллинеарен 1 2. Тогда в этих окрестностях однозначно определена точка где — это середина отрезка 1 2.

Заметим, что скалярное произведение — непрерывная функция, множество O(1, 2 ) также меняется непрерывно, и решение единственно для 1 и 2 в некоторой окрестности точек 0 и 0, поэтому функция (1, 2 ) — однозначно определённая и непрерывная функция в этой окрестности, причём сформулировать и для одной точки 1.

Лемма 6. Пусть 0 и 0 таковы, что |0 0 | = 1. Тогда существует такая функция (1 ), что |1 (1 )| = 1 и непрерывно зависит от положения точки 1 в пространстве, причём (0 ) = 0. Другими словами, если (1, 1, 1 ) — это координаты точки 1, то координаты точки — непрерывные функции от переменных 1, 1, 1 в некоторой окрестности точки (0, 1, 1 ).

Доказательство. Достаточно взять (1 ) = 1 + 0 0.

Главное, что мы сделали здесь, — это определили начало координат на окружности (в лемме 5) и сфере (в лемме 6). Теперь дополним эту окружности и сферу системой координат так, чтобы точки с соответствующими координатами менялись непрерывно в зависимости от положения точек и 2. В случае с окружностью координата начала координат на окружности уже задана точкой (1, 2 ), а направление на окружности мы зададим так, что тройка векторов 1 2, и, где — это направление, в котором возрастают координаты в точке, является правой и координата каждой точки на окружности задаётся величиной дуги между и этой точкой в направлении. Подобным способом можно задать координаты и на сфере, но это не понадобится нам в этой работе.

Заданная таким образом система координат на окружности будет непрерывна относительно положения точек 1 и 2 в некоторой окрестности 0 и 0 (которая задаётся в лемме 5).

2.2.4 Процедура «шевеления»

Как было сказано в пункте 2.2.1, мы хотим разнести положения тринадцати точек 1,..., 13, которые находятся в одной точке, так, чтобы оставшиеся вершины, соединённые рёбрами, остались соединёнными рёбрами. Можно представить себе граф в виде каркаса с шарнирами в вершинах, соединёнными планками, соответствующими рёбрам. Тогда в этом пункте мы покажем, что можно немного подвигать тринадцать из этих шарниров, чтобы конструкция не развалилась, а эти тринадцать шарниров, положение которых изначально совпадало, оказались в разных точках. Как уже было сказано, «шевелим»

мы только вершины 1,..., 13. Здесь будут описаны правила, по которым меняется положение остальных вершин.

Мы введём функции, выражающие зависимость положения вершин графов 1 2 3 4 от положения вершин 1, 2, 3, 4. В таблице 2.1 показана последовательность, в которой положения вершин графа зависят друг от друга.

В таблице 2.1 показан порядок присоединения вершин в графе 1 2 3 4.

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

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

Таблица 2.1: Порядок присоединения вершин Например, в первой строчке таблицы написано, что положение вершины 1 зависит от вершины 1. Это означает, что для каждого данного положения вершины 1 мы разместим вершину 1 таким образом, чтобы расстояние между 1 и 1 равнялось единице. В шестой строке таблицы написано, что положение вершины 2 зависит от положения вершин 1, 3 и 1. Таким образом, зная расположения вершин 1, 3 и 1 в пространстве, мы хотим расположить 2 так, чтобы она находилась на единичном расстоянии от 1, и 1. В соответствии с леммой 4 это можно сделать, если 1, 3 и 1 находятся достаточно близко к своим начальным положениям 01, 0 и 1.

Мы последовательно проделаем эту операцию со всеми вершинами.

Такой набор положения вершин существует, если 1, 2, 3 и 4 находятся в некоторой достаточно малой окрестности нуля, поскольку изначально, когда все точки были в нуле, такое расположение существовало, а значит, в соответствии с леммами 4, 5 и 6 оно существует и в некоторой окрестности начальных положений точек, поскольку положение каждой вершины в таблице зависит от положения одной, двух или трёх других вершин. Таким образом, мы построили все вершины подграфа 1 2 3 4 и убедились, что расстояние между всеми парами вершин, соединёнными ребром, кроме пар {1, 5 } и {1, 5 }, равно единице.

Как видно из таблицы 2.1, положение всех вершин однозначно определяется по координатам точек {1,..., 13 }, когда все эти точки находятся в некоторой окрестности начала координат, с точностью до 8 параметров (степени свободы в последнем столбце таблицы 2.1). С другой стороны, положение точек 5 и 5 может быть таково, что расстояние до 4 и соответственно отличается от единицы. Воспользовавшись леммами 5 и 6, мы зафиксируем положение всех точек, кроме 1 и 1. Теперь расстояние (4, 5 ) = |4 5 | — это функция от положения точек 1, 2, 3 и 4, а также — координаты точки 1, заданной в лемме 5, причём зависимость эта непрерывная.

Функция непрерывна по всем координатам в некоторой окрестности нуля (все переменные равны нулю).

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

Задав таким способом с помощью неявной функции (1, 2, 3, 4 ) координаты точки 1 (и аналогичным образом — координаты точки 1 ), мы получим, что все вершины, соединённые ребром в графе, находятся на единичном расстоянии друг от друга. Осталось выбрать такие точки {1,..., 13 }, в окрестности нуля, чтобы они не совпадали, а расстояние между всеми остальными вершинами (не соединёнными ребром) не было равно нулю или единице. Кроме того, требуется, чтобы, если три вершины таковы, что они все соединены с некоторой четвёртой вершиной ребром, то радиус описанной окружности был меньше единицы. Все эти условия соблюдены в начальном положении точек. Зависимость непрерывная, а значит, то же будет верно и в некоторой (3 · 13 = 39-мерной) окрестности начальной точки. Нам подойдут любые различные точки {1,..., 13 } из этой окрестности.

Глава Асимптотика хроматических чисел графов расстояний с несколькими запрещёнными расстояниями и без больших клик при росте размерности пространства 3.1 Доказательство теоремы Для доказательства нам потребуется определить (). Это величина, в некотором смысле двойственная величине () (отсюда и обозначение):

Эта величина называется числом независимости графа; в свою очередь, все множества вершин графа, свободные от его ребер, называются независимыми.

Таким образом, число независимости — это мощность самого большого независимого множества вершин.

Число независимости и хроматическое число графа связывает следующее неравенство:

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

Сложив количество вершин в этих () множествах, мы получим общее Перейдём непосредственно к доказательству теоремы. Зафиксируем, 0, а стало быть, и 0, 1,,. Легко видеть, что либо =, либо = {1 }, либо = [, 1 ], 0. В первых двух случаях утверждение теоремы тривиально.

Возьмем произвольное (, 1 ). Здесь важно, что строго больше, инфимум обеих частей неравенства по, мы получим искомое утверждение Итак, нам нужно убедиться в существовании такой функции () = (1), что при всех найдется граф расстояний = (, ) в R, у которого Положим для каждого достаточно большого N Пусть — минимальное простое число, удовлетворяющее условию [0 ]2 < 0. Известно, что с ростом справедлива асимптотика = () 0. Это обусловлено тем, что между и + всегда есть простое число (см.

[29]). Положим С помощью формулы Стирлинга легко показать, что Для дальнейших рассуждений используем следующую лемму.

Рассмотрим граф = (, ), у которого Тогда для числа независимости графа выполнено следующее неравенство:

Доказательство. Мы докажем лемму с помощью линейно-алгебраического метода в комбинаторике (см. [28], [30]). Каждому вектору x мы сопоставляем некоторый полином x Z/Z[1,..., ]. В данном случае мы полагаем неотрицательным вычетам по модулю, кроме остатка от деления на Полиномы подобраны так, чтобы выполнялось следующее Свойство 1. Для любых x, y условие x, y (mod ) равносильно условию x (y) 0 (mod ).

Свойство очевидно, и мы его не доказываем. Ясно, далее, что степень каждого полинома не превосходит 1. Сейчас мы еще упростим полиномы, причем так, что свойство 1 для новых полиномов останется верным. Раскроем в данном полиноме x скобки. Получится линейная комбинация мономов, каждый из которых имеет вид Формально заменим всякий такой моном мономом Поскольку в свойстве 1 фигурируют лишь векторы y, т.е. векторы, все координаты которых суть 0 или 1, то значение полинома не поменяется, а стало быть, свойство 1 для новых полиномов x снова выполнено.

Полиномы x хороши тем, что, хотя их степени по-прежнему могут достигать значения 1, все они содержатся в пространстве полиномов размерности сыграем.

Рассмотрим произвольное независимое множество = {x1,..., x }.

Иначе говоря, для любых, выполнено x, x =. Возьмем полиномы x1,..., x. Предположим, что для некоторых 1,..., Z/Z имеет место сравнение Пусть y = x, — любое. Тогда Значит, ввиду свойства 1, x (y) 0 (mod ). В то же время x, y =.

Разумеется, x, y <. Но очевидно, что 2 < 0, т.е. x, y > 2. В итоге x, y (mod ), а стало быть, опять же за счет свойства 1, x (y) 0 (mod ) для всех =. Поскольку — простое, имеем 0 (mod ) при любом.

Приведенное выше рассуждение показывает, что полиномы x1,..., x линейно независимы над Z/Z. Следовательно, не превосходит размерности пространства, порожденного этими полиномами, а она, как мы помним, не больше, чем. Множество было произвольным, так что выполнено и с некоторой 2 = (1), и это, на первый взгляд, даже лучше заявленного в теореме результата. Неприятность в том, что граф расстояний вполне может содержать (и содержит) клики размера больше.

Воспользуемся вероятностным методом (см. [25], [26], [27]). Рассмотрим произвольное число 0, 1. Такое существует, поскольку > 0. Положим =, где по-прежнему достаточно велико. Построим случайный подграф = (, ) графа, «кладя» в каждое ребро из с вероятностью независимо от остальных ребер. Образуется вероятностное пространство (,, ), в котором для = (, ).

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

Пусть = [( ) ]. Ясно, что, за счет неравенства < 1, при больших выполнено < = | |, а стало быть, величина корректно определена.

Допустим, мы показали, что где через E обозначено математическое ожидание случайной величины.

Тогда по неравенству Маркова (Чебышёва) имеют место оценки (см. [31]) размера. Удалим из каждой клики в по одной вершине, получится граф и теорема доказана. (Cледует только заметить, что при малых доказывать нечего, ведь мы вольны на начальном отрезке натурального ряда выбрать значения () сколь угодно большими по модулю.) Что ж, будем оценивать математические ожидания.

Начнём с E. За счет линейности математического ожидания, имеем Ясно, что, поскольку > 0, то > = ( ) при всех достаточно больших, и, стало быть, для каждого, | | =, выполнено ( ) > 0.

верное при > (см. [35]).

Заметим, что Таким образом, полагая имеем (с некоторыми () = (1)) Следовательно, при всех достаточно больших выполнено E < 2, и нам За счет линейности математического ожидания имеем E Далее, поскольку — константа (т.е. не зависит от ), Из определения и из условия < видно, что настолько близким к своей нижней границе, чтобы оказалась справедливой оценка > Тогда, c учетом отрицательности величины ln, Таким образом, E = ( ) при, и нужное нам неравенство при больших имеет место.

Теорема доказана.

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

Пусть, далее, — минимальное простое число, удовлетворяющее условию [1 ] + [1 ] 2 < 2[1 ]. Положим По Стирлингу, | | = (1 + (1)). Кроме того, известно (см. [28]), что рассуждения ясны, и теорема доказана.

3.3 Доказательство теоремы утверждение теоремы 8 тривиально. Поэтому будем считать, что (v) > 0.

Иными словами, число координат величины в каждом векторе из асимптотически равно. Нетрудно видеть, что тем самым Положим, далее, Несложно убедиться в том, что, (см. также [24]).

Пусть — минимальное простое число, удовлетворяющее условию (+ В работе [23] показано, что где Стандартный анализ с участием формулы Стирлинга дает запись Далее, следует применить вероятностный метод. Для этого выберем что min { ()} ln < (v). Последнему условию можно удовлетворить, поскольку (v) > 0, т.е.

а значит, нужно просто брать любое, при котором ln достаточно близок одновременно Так, опять же, можно сделать, поскольку, ввиду неравенства min { ()} ln < (v), интервал не пуст.

Положим =, = [ ] (ср. раздел 3.1). Построим на основе графа случайный граф с вероятностью ребра. Определим случайные величины и в точности так же, как одноименные величины определялись в разделе 3.1. Корректность и нетривиальность определения величины следует из Разумеется, мы всюду далее будем считать, что достаточно велико, опуская упоминание об этом.

знакомые выкладки:

Мы знаем, что ln > min { ()}ln. Значит, ln +ln > min { ()}, Теорема 8 доказана.

3.4 Небольшой комментарий к теореме Из общих соображений понятно, что теоремы 6 и 7 должны быть частными случаями теоремы 8. В действительности, так оно, конечно, и есть. Разница заключается в том, что в теоремах 6 и 7 мы смогли в явном виде отыскать минимум, возникающий в формулировке теоремы 8. Иными словами, если в теореме 8 величина (v) включает в себя минимизацию по, то в теоремах 6 и 7 эта минимизация произведена заранее. При этом в последних двух теоремах = 2 и = 3 соответственно. Разумеется, мы с таким же успехом могли в тех теоремах полагать = 4 и т.д., рассматривая не (0,1)-векторы и не (-1,0,1)векторы (которые с точки зрения нашей задачи равносильны (0,1,2)-векторам), а (0,1,2,3)-векторы и т.д. Разумеется, такое усложнение привело бы к тому, что надлежащий минимум по мы не смогли бы найти явно. Но суть не в том. А суть в том, что непосредственная проверка показывает отсутствие сколь-нибудь заметных улучшений результатов теорем 6 и 7 при переходе к большему количеству значений координат в каждом векторе конструкции.

Именно поэтому мы выделили случай = 1: в нем достаточно брать = 2, = 3, и это позволяет упростить вычисления.

Напротив, в теореме 8 величина произвольная, и на поверку оказывается, что чем больше, тем больше оптимальное значение.

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

Аналогичную проблему в иной ситуации преодолели авторы статьи [24]. В следующем разделе мы напомним экстремальную задачу, которую им удалось решить, и увидим, что наша задача практически с ней совпадает. В итоге нам останется лишь напомнить основные идеи из работы [24], дабы прояснить возникновение численных данных в пункте 1.3.4.

3.5 Решение экстремальной задачи Итак, нам хочется численно отыскать Однако в работе [24] изложена технология отыскания Там слегка иные обозначения, но смысл именно такой.

Понятно, что разница между задачами отсутствует, ведь — это константа.

Ниже мы лишь напомним основную схему оптимизации.

Прежде всего при каждом ищем Далее, замечаем, что в неравенство можно заменить равенством, т.е. нам нужно найти Вводим векторы a, исходя из утверждения (предложение 2 из [24]):

неотрицательными векторами a, не зависящими от. Получаем (теорема 1 из [24]), что где Для любого > 0 полагаем А для любого вектора a = (1,..., ) с целыми неотрицательными координатами полагаем Оказывается, что (теорема 2 из [24]) где — единственный положительный корень полинома единственный положительный корень полинома + Такая задача решается достаточно легко. Ее численное решение описано в параграфе 4 статьи [24], его мы и реализуем при получении таблиц пункта 1.3.4, который завершает настоящий раздел, а с ним и всю нашу работу.

Список литературы [1] Soifer A. Chromatic number of the plane: a historical essay // Geombinatorics.

[2] Erd s P. Unsolved Problems // Congress Numerantium XV — Proceedings of the 5th British Comb. Conf. 1975. 1976. p. 681.

[3] Wormald N. A 4-Chromatic Graph With a Special Plane Drawing // Australian Mathematics Society (Series A). 1979. Vol. 28. P. 1 – 8.

[4] O’Donnel P., Hochberg R. Some 4-chromatic Unit-Distance Graphs without small cycles // Geombinatorics. 1996. Vol. 5. P. 137 – 142.

[5] Nechushtan O. Note on the space chromatic number // Discrete Mathematics.

2002. Vol. 256. P. 499 – 507.

[6] Райгородский А.М. О хроматическом числе пространства // Успехи математических наук. 2000. Т. 55. С. 147 – 148.

[7] Гарднер М. Математические головоломки и развелчения. «Мир», 1999.

[8] Moser L., Moser W. Solution to problem 10 // Canad. Math. Bull. 1961.

[9] Erd s P. Graph theory and probability // Canadian Journal of Mathematics.

1959. Vol. 11, no. 1. P. 34 – 38.

[10] O’Donnell P. Arbitrary girth, 4-chromatic unit distance graphs in the plane. I.

Graph description // Geombinatorics. 2000. Vol. 9, no. 3. P. 145 – 152.

[11] O’Donnell P. Arbitrary girth, 4-chromatic unit distance graphs in the plane. II.

Graph embedding // Geombinatorics. 2000. Vol. 9, no. 4. P. 180 – 193.

[12] Hadwiger H. Ungel ste Probleme N 40 // Proc. Koninkl. Nederl. Acad. Wet., Ser. A. 1961. Vol. 16. P. 103 – 104.

[13] Райгородский А.М. Хроматические числа. Библиотека «Математическое просвещение». Москва: МЦНМО, 2003.

[14] Coulson D. A 15-colouring of 3-space omitting distance one // Discrete mathematics. 2002. Vol. 256, no. 1. P. 83 – 90.

[15] Cantwell K. Finite Euclidean Ramsey theory // Journal of Combinatorial Theory, Series A. 1996. Vol. 73, no. 2. P. 273 – 285.

[16] Иванов Л.Л. Оценка хроматического числа пространства R4 // Успехи математических наук. 2006. Т. 61, № 5. С. 371 – 372.

[17] Radoi i R., T th G. Note on the chromatic number of the space // Discrete and Computational Geometry. Springer, 2003. P. 695 – 698.

[18] Larman D., Rogers C. The realization of distances within sets in Euclidean space // Mathematika. 1972. Vol. 19, no. 1. P. 1 – 24.

[19] Frankl P., Wilson R. Intersection theorems with geometric consequences // Combinatorica. 1981. Vol. 1. P. 358 – 368.

[20] Sz kely L. Erd s on unit distances and the Szemer di–Trotter theorems // Paul Erd s and his Mathematics, Bolyai Series Budapest. 2002. Vol. 11. P. 649 – [21] Райгородский А.М. Проблема Борсука и хроматические числа некоторых метрических пространств // Успехи математических наук. 2001. Т. 56, [22] Райгородский А.М., Абсалямова М.И. О нижней оценке хроматического числа пространства R с запрещёнными расстояниями и метрикой 1 // Чебышёвский сборник. 2006. № 4. С. 105 – 112.

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

[24] Оценка хроматических чисел евклидова пространства методами выпуклой минимизации / Е.С. Горская, И.М. Митричева, В.Ю. Протасов [и др.] // Математический сборник. 2009. Т. 200, № 6. С. 3 – 22.

[25] Алон Н., Спенсер Дж.Н. Вероятностный метод. Москва: Бином. Лаборатория знаний, 2007.

[26] Bollob s B. Random graphs. Cambridge university press, 2001.

[27] Райгородский А.М. Вероятность и алгебра в комбинаторике. Москва:

МЦНМО, 2008.

[28] Райгородский А.М. Линейно-алгебраический метод в комбинаторике.

Москва: МЦНМО, 2007.

[29] Baker R., Harman G., Pintz J. The difference between consecutive primes, II // Proceedings of the London Mathematical Society. 2001. Vol. 83, no. 3.

[30] Babai L., Frankl P. Linear algebra methods in combinatorics with applications to geometry and computer science. Department of Computer Science, The University of Chicago, 1992.

[31] Гнеденко Б.В. Курс теории вероятностей. Москва: Физматлит, 1961.

Работы автора по теме диссертации [32] Рубанов О.И. Хроматические числа трехмерных графов расстояний, не содержащих тетраэдров // Математические заметки. 2007. Т. 82, № 5.

[33] Демёхин Е.Е., Райгородский А.М., Рубанов О.И. Дистанционные графы, имеющие большое хроматическое число и не содержащие клик или циклов заданного размера // Математический сборник. 2013. Т. 204, № 4.

[34] Raigorodskii A., Rubanov O. On the clique and the chromatic numbers of highdimensional distance graphs // Number Theory and Applications: Proceedings of the International Conferences on Number Theory and Cryptography. SD Adhikari and B. Ramakrishnan, Harish-Chandra Research Institute, Editors — A publication of Hindustan Book Agency, 2009. P. 149 – 157.

[35] Райгородский А.М., Рубанов О.И. О графах расстояний с большим хроматическим числом и без больших клик // Математические заметки. 2010.

[36] Raigorodskii A., Rubanov O. Small clique and large chromatic number // Electronic Notes in Discrete Mathematics. 2009. Vol. 34. P. 441 – 445.