О хроматических числах R2 и R3 с интервалами запрещённых расстояний.

July 10, 2018 | Author: Anonymous | Category: Каталог , Без категории
Share Embed


Short Description

Download О хроматических числах R2 и R3 с интервалами запрещённых расстояний. ...

Description

УДК 514.174.5

О хроматических числах R2 и R3 с интервалами запрещённых расстояний Л. Л. Иванов Факультет физико-математических и естественных наук Российский университет дружбы народов улица Миклухо-Маклая, 6, Москва, 117198, Россия В данной статье представлено одно из обобщений классического понятия хроматического числа плоскости, или пространства, а именно, хроматического числа с интервалом запрещённых расстояний. Были получены верхние оценки для введённой величины при различных интервалах и описан метод получения подобных результатов. Ключевые слова: хроматическое число, запрещённое расстояние.

1.

Введение

В середине двадцатого столетия была сформулирована одна из наиболее ярких задач комбинаторной геометрии — задача об отыскании минимального числа цветов, необходимого для покраски плоскости, при которой любые две точки на расстоянии 1 разноцветны. Иными словами, одноцветным точкам запрещается находиться на расстоянии 1. Своим появлением эта задача обязана Э. Нельсону, Г. Хадвигеру и П. Эрдешу (см. [1–6]). Задача естественно обобщается на случай произвольного метрического пространства. Определим хроматическое число метрического пространства (𝑀, 𝜌) с множеством 𝐴 запрещённых расстояний как 𝜒((𝑀, 𝜌), 𝐴) = min{𝑘 | 𝑀 = 𝑀1 ⊔ . . . ⊔ 𝑀𝑘 , ∀𝑖 = 1, . . . , 𝑘, ∀𝑥, 𝑦 ∈ 𝑀𝑖 , 𝜌(𝑥, 𝑦) ̸∈ 𝐴}, т.е. как минимальное количество цветов, в которые можно так покрасить все пространство, чтобы между точками одного цвета не было запрещённого расстояния. В дальнейшем мы будем иметь дело только с евклидовым пространством (R𝑛 , | · |) и использовать краткую запись 𝜒𝐴 (R𝑛 ) = 𝜒((R𝑛 , | · |), 𝐴). Заметим, что хроматическое число не меняется при «растяжении» запрещённого множества, т.е. 𝜒𝜆𝐴 (R𝑛 ) = 𝜒𝐴 (R𝑛 ). Заметим также, что если запрещённое расстояние одно, то мы получаем хроматическое число для классической задачи: 𝜒{𝑎} (R𝑛 ) = 𝜒{1} (R𝑛 ) =: 𝜒(R𝑛 ). Целью этой работы является исследование хроматических чисел пространств с отрезками запрещённых расстояний, т.е. ситуаций, когда запрещённое множество 𝐴 имеет вид [𝑎, 𝑏]. Не меняя сути, можно свести отрезок к виду [1, 𝑑], где 𝑑 > 1 (случай 𝑑 = 1, конечно, вырожденный). Введём краткое обозначение 𝜒𝑑 (R𝑛 ) = 𝜒[1,𝑑] (R𝑛 ). Если 𝑑 = 1, мы снова оказываемся в рамках классического случая: 𝜒1 (R𝑛 ) = 𝜒{1} (R𝑛 ) = 𝜒(R𝑛 ). При других значениях 𝑑 до сих пор практически никаких результатов получено не было. Известны следующие оценки хроматического числа в малых размерностях: Статья поступила в редакцию 18 сентября 2010 г.

Иванов Л. Л. О хроматических числах R2 и R3 с интервалами запрещён‌ . . . 1

2

15 3

𝜒(R ) = 2 (этот факт очевиден), 4 6 𝜒(R ) 6 7 (см. [1–3]), 6 6 𝜒(R ) 6 15 (см. [7, 8]), 7 6 𝜒(R4 ) 6 49 (см. [9]). Кроме того, установлены асимптотические оценки с ростом размерности 𝑛: (1.239+𝑜(1))𝑛 6 𝜒(R𝑛 ) 6 (3+𝑜(1))𝑛 (см. [10], [11]). В следующих разделах мы сформулируем и докажем ряд новых оценок при 𝑑 > 1 в размерностях 𝑛 = 1, 2, 3.

2.

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

В одномерном случае можно точно определить хроматическое число для всех 𝑑. Теорема 1. Выполнено равенство 𝜒𝑑 (R1 ) = ⌈𝑑⌉ + 1. В случае плоскости и пространства можно установить несложные асимптотические оценки хроматического числа в зависимости от величины 𝑑. Эти оценки имеют вид 𝑐1 𝑑2 6 𝜒𝑑 (R2 ) 6 𝑐2 𝑑2 , 𝑐3 𝑑3 6 𝜒𝑑 (R3 ) 6 𝑐4 𝑑3 , где 𝑐1 , 𝑐2 , 𝑐3 , 𝑐4 — некоторые положительные константы. В общем случае эти константы можно конкретизировать. Например, справедливы неравенства 3 4 (𝑑 + 𝑜(1))2 6 𝜒𝑑 (R2 ) 6 (𝑑 + 𝑜(1))2 , 4 3 √ 5 5 5 3 3 (𝑑 + 𝑜(1)) 6 𝜒𝑑 (R ) 6 √ (𝑑 + 𝑜(1))3 . 12 3 3

Эти неравенства допускают дальнейшие уточнения, но мы на них в данной работе останавливаться не будем. Цель работы состоит в получении оптимальных верхних оценок для 𝜒𝑑 (R2 ) и 𝜒𝑑 (R3 ) для ряда конкретных значений 𝑑. Теорема 2. В √ случае плоскости имеют место следующие результаты: 7 1. При всех 𝑑 6 = 1, 322 . . . выполнено неравенство 𝜒𝑑 (R2 ) 6 7. 2 √ 2. При всех 𝑑 6 3 = 1, 732 . . . выполнено неравенство 𝜒𝑑 (R2 ) 6 9. 3. При всех 𝑑 6 2√выполнено неравенство 𝜒𝑑 (R2 ) 6 12. 19 2 √ 3 3 5. При всех 𝑑 6 √2 31 6. При всех 𝑑 6 √2 37 7. При всех 𝑑 6 2

4. При всех 𝑑 6

= 2, 179 . . . выполнено неравенство 𝜒𝑑 (R2 ) 6 13. = 2, 598 . . . выполнено неравенство 𝜒𝑑 (R2 ) 6 16. = 2, 783 . . . выполнено неравенство 𝜒𝑑 (R2 ) 6 19. = 3, 041 . . . выполнено неравенство 𝜒𝑑 (R2 ) 6 21.

Теорема 3. В случае трёхмерного пространства имеют место оценки: 1. При всех 𝑑 6 1, 115 выполнено неравенство 𝜒𝑑 (R3 ) 6 18. 2. При всех 𝑑 6 1, 133 выполнено неравенство 𝜒𝑑 (R3 ) 6 21. 3. При всех 𝑑 6 1, 137 выполнено неравенство 𝜒𝑑 (R3 ) 6 23. 4. При всех 𝑑 6 1, 303 выполнено неравенство 𝜒𝑑 (R3 ) 6 24. 5. При всех 𝑑 6 1, 549 выполнено неравенство 𝜒𝑑 (R3 ) 6 27. Отметим, что списки утверждений в теоремах 2 и 3 можно продолжить и далее. Однако в настоящей работе мы этого делать не станем. оценки 𝜒𝑑 (R3 ) 6 21 при 𝑑 < √︂ Заметим также, что в статье [12] упоминаются √︂ 7 = 1, 080 . . . и 𝜒𝑑 (R3 ) 6 18 при 𝑑 < 6

131 = 1, 076 . . .. Видно, что в утвержде113

ниях теоремы 3 эти неравенства уточняются.

16

Вестник РУДН. Серия Математика. Информатика. Физика. № 1. 2011. С. 14–29

Перед тем, как приступить к самим доказательствам, коротко скажем, в какой последовательности мы собираемся их излагать. Сперва мы обоснуем утверждение теоремы 1, т.е. докажем равенство 𝜒𝑑 (R1 ) = ⌈𝑑⌉ + 1. Этому будет посвящён раздел 3. Потом мы приступим к разбору доказательства верхних оценок в теоремах 2 и 3 (см. раздел 4). Для этого вначале (см. §4.1) будет описан общий метод построения покрасок, дающий верхние оценки. Затем (см. §4.2) будут рассмотрены некоторые свойства таких покрасок, которые помогут упростить возможный перебор и расчёты. И, наконец, будут даны доказательства конкретных неравенств для хроматического числа, как в случае плоскости, так и в случае пространства. Отметим, что ввиду однотипности рассуждений в этом разделе конкретные доказательства будут даны только для двух оценок в плоскости и одной - в случае пространства. Если говорить более точно, мы приведём полные доказательства оценок 𝜒1,322 (R2 ) 6 7, 𝜒2,598 (R2 ) 6 16, 𝜒1,115 (R3 ) 6 18. Что касается остальных неравенств, мы лишь предоставим всю необходимую информацию для того, чтобы читатель мог самостоятельно проверить все надлежащие вычисления. Теперь перейдём к самим доказательствам.

3.

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

Для обоснования равенства 𝜒𝑑 (R1 ) = ⌈𝑑⌉ + 1 докажем оценки сверху и снизу: 𝜒𝑑 (R1 ) 6 ⌈𝑑⌉ + 1 и 𝜒𝑑 (R1 ) > ⌈𝑑⌉ + 1 соответственно. Чтобы получить оценку величиной 𝑛 := ⌈𝑑⌉ + 1 сверху, приведём покраску прямой в 𝑛 цветов. Будем красить полуинтервалы вида [𝑘, 𝑘 + 1), где 𝑘 – целое число, в 𝑖-ый цвет, если 𝑘 даёт остаток 𝑖 при делении на 𝑛. Нетрудно проверить, что покраска окажется правильной (т.е. свободной от одноцветных точек на запрещённом расстоянии) для отрезка запрещённых расстояний [1, 𝑛 − 1] = [1, ⌈𝑑⌉], а значит, и для отрезка [1, 𝑑]. Теперь перейдём к нижним оценкам. Нам понадобятся следующие определения. Определение 1. Графом расстояний с отрезком запрещённых расстояний [1, 𝑑] будем называть граф 𝐺 = (𝑉, 𝐸) с множеством вершин 𝑉 ⊆ R𝑛 (при некотором 𝑛 ∈ N) и множеством рёбер 𝐸, которое определяется как 𝐸 = {(x, y)| x, y ∈ 𝑉, |x − y| ∈ [1, 𝑑]}. Определение 2. Хроматическим числом 𝜒(𝐺) графа 𝐺 называется минимальное количество цветов, необходимое для покраски множества его вершин с тем условием, что одноцветные вершины не соединены ребром. Заметим, что 𝜒𝑑 (R𝑛 ) > 𝜒(𝐺), если 𝐺 – граф расстояний в R𝑛 с отрезком запрещённых расстояний [1, 𝑑]. Пусть 𝑑 – целое число. Рассмотрим граф расстояний 𝐺 = (𝑉, 𝐸) с множеством вершин 𝑉 = {0, 1, 2, . . . , 𝑑} и отрезком запрещённых расстояний [1, 𝑑]. Данный граф, очевидно, является полным, и, следовательно, его хроматическое число равно количеству его вершин, т.е. величине 𝑑+1, что и даёт нам искомую нижнюю оценку. Пусть теперь 𝑑 – дробное. Представим его в виде 𝑑 = [𝑑] + 𝜀, где 0 < 𝜀 < 1. Рассмотрим граф расстояний Γ𝛿 = (𝑉𝛿 , 𝐸𝛿 ) с множеством вершин {0, 1, 2, . . . , [𝑑], [𝑑] + 𝛿} и отрезком запрещённых расстояний [1, 𝑑]. Здесь 𝛿 – это произвольное число в промежутке (0, 𝜀). Граф Γ𝛿 является “почти полным”: в множестве его рёбер 𝐸𝛿 = {(𝑎, 𝑏) | 𝑎, 𝑏 ∈ 𝑉𝛿 , |𝑎 − 𝑏| ∈ [1, 𝑑]} отсутствует только ребро ([𝑑], [𝑑] + 𝛿).

Иванов Л. Л. О хроматических числах R2 и R3 с интервалами запрещён‌ . . .

17

Предположим, что вся прямая покрашена не более чем в ⌈𝑑⌉ = [𝑑] + 1 цветов. Тогда вершины [𝑑] и [𝑑] + 𝛿 оказываются окрашенными в один цвет. Это рассуждение остаётся верным, если менять значение 𝛿 в диапазоне 0 < 𝛿 < 𝜀, а также параллельно переносить конструкцию Γ𝛿 вдоль прямой на любое расстояние. Выходит, что любые две точки прямой, расстояние между которыми меньше 𝜀, должны быть окрашены в один цвет, но этого не может быть. Противоречие. Теорема доказана.

4. 4.1.

Доказательство теорем 2 и 3

Общий метод получения верхних оценок

Все наши оценки будут доказаны с помощью построения некоторых периодических покрасок, основанных на решетчатых разбиениях пространства (плоскости) на многогранники (многоугольники). Напомним, что 𝑛-мерной решёткой Λ называется множество всех целочисленно-линейных комбинаций векторов некоторого базиса {a1 , . . . , a𝑛 } пространства R𝑛 . Говорят, в свою очередь, что векторы a1 , . . . , a𝑛 образуют базис решётки Λ. Решётку также можно воспринимать как (дискретную абелеву) подгруппу в R𝑛 . Подрешётку можно определить как подмножество решётки, которое в то же время само является решёткой. Индекс Γ : Λ подрешётки Γ в решётке Λ — это порядок факторгруппы Λ/Γ. Определителем решётки det Λ называется модуль определителя матрицы, составленной из базисных векторов решётки Λ. Иными словами, определитель равен объёму (площади) фундаментальной области решётки, которая представляет собой, в зависимости от размерности, параллелограмм или параллелепипед. В частности, понятно, что определитель решётки не зависит от выбора базиса, который, конечно, не обязан быть единственным. Кроме того, отношение определителя подрешётки Γ к определителю решётки Λ в точности равно индексу подрешётки: det Γ/ det Λ = Γ : Λ. Подробнее о теории решёток можно прочесть в [13], [14], [15] и др. Нам понадобится следующее важное понятие. Определение 3. Областью Вороного 𝒱Λ (a) элемента a решётки Λ называется множество всех точек пространства, которые отстоят от a не далее, чем от любой другой точки решётки Λ: 𝒱Λ (a) = {x ∈ R𝑛 : |x − a| 6 |x − b|, ∀ b ∈ Λ}. Ясно, что при помощи решётки можно разбить все пространство на области Вороного, с точностью до пересечения границ. Опишем общий метод построения периодической покраски, основанный на таких решетчатых разбиениях. Пусть дана решётка Λ и некоторая подрешётка Γ ⊂ Λ. Покрасим в первый цвет области Вороного, отвечающие элементам подрешётки Γ. То, ⋃︁что мы покрасили, в совокупности назовём базовым цветом и обозначим 𝒢0 = 𝒱Λ (a). Для краткоa∈Γ

сти будем писать 𝒢 = 𝒢0 . Остальные цвета получаются путём ⋃︁ рассмотрения элементов факторгруппы Λ/Γ и аналогичного определения 𝒢𝑖 = 𝒱Λ (a), Γ𝑖 ∈ Λ/Γ a∈Γ𝑖

(в данном контексте Γ𝑖 формально не являются решётками, однако это просто копии множества точек решётки Γ). Всего цветов получится |Λ/Γ| = det Γ/det Λ. О том, как корректно раскрасить границы областей Вороного, будет сказано позднее. Определение 4. Область Вороного, отвечающую началу координат, будем называть базовой. Итак, с помощью решётки Λ и подрешётки Γ можно построить покраску пространства, причём количество цветов определяется индексом подрешётки Γ в Λ.

18

Вестник РУДН. Серия Математика. Информатика. Физика. № 1. 2011. С. 14–29

Поскольку все цвета устроены одинаково, достаточно рассмотреть только базовый цвет, чтобы выяснить, какие расстояния реализуются между точками одного цвета. Ввиду периодичности структуры цвета достаточно рассматривать расстояния только между точками базовой области и какой-либо другой области, отвечающей элементу подрешётки. Очевидно, реализуются все расстояния, меньшие диаметра области. Таким образом, если считать диаметр области равным 1, то покраска будет правильной с запрещённым множеством (1, 𝑑), где 𝑑 — минимальное расстояние между точками разных областей одного цвета. Это и будет давать нам оценку сверху для 𝜒𝑑 . 4.2.

Вспомогательные геометрические леммы

Приведём несколько вспомогательных лемм, связанных с решетчатыми покрасками и областями Вороного. Речь пойдёт исключительно об R2 и R3 . Лемма 1. Для каждой области Вороного, отвечающей элементу решётки, выполнены свойства: 1. В зависимости от размерности область Вороного является выпуклым многоугольником или многогранником. 2. Этот многоугольник (многогранник) центрально симметричный. 3. Центрально симметричны все его стороны (грани). Лемма 1 хорошо известна (см. [16]), и мы её доказывать не станем. В последующих леммах мы будем говорить о многогранниках Вороного, или просто о многогранниках, имея в виду при этом области Вороного как в трёхмерном случае, так и, возможно, в плоском случае. В процессе доказательства верхних оценок нам придаётся рассматривать расстояния между разными многогранниками одного цвета и искать среди них минимальное. Для этого нам будет полезна следующая лемма. Лемма 2. Пусть 𝐷 — минимальное расстояние между двумя областями Вороного 𝒱Λ (a), 𝒱Λ (b), отвечающими точкам a и b некоторой решётки Λ. Тогда можно найти точки m ∈ 𝒱Λ (a) и n ∈ 𝒱Λ (b), симметричные относительно середины отрезка ab, между которыми реализуется расстояние 𝐷. Доказательство. Пусть минимальное расстояние реализуется между какимито точками x ∈ 𝒱Λ (a) и y ∈ 𝒱Λ (b), но x и y не симметричны относительно середины s отрезка ab. При симметрии относительно s точка x переходит в x′ ∈ 𝒱Λ (b), а точка y — в y′ ∈ 𝒱Λ (a), причём расстояние |x′ − y′ | = |x − y| тоже минимально. Получается параллелограмм xyx′ y′ . Рассмотрим середины m и n его сторон xy′ и yx′ , которые принадлежат нашим многогранникам ввиду их выпуклости. Верно равенство |m − n| = |x − y|, и, значит, расстояние между m и n тоже минимально. Точки m и n симметричны относительно s, что и требовалось.  Таким образом, чтобы вычислить минимальное расстояние между двумя многогранниками, достаточно найти минимальное расстояние от точки s до одного многогранника и умножить его на 2. Приведём ещё одну лемму, которая поможет сократить возможный перебор и счёт в наших доказательствах. Сперва введём несколько понятий. Будем считать, что подрешётка задана некоторым базисом. Первым слоем подрешётки в данном базисе будем называть множество всех многогранников, кроме базового, отвечающих точкам подрешётки с координатами {0, ±1} в этом базисе. Нулевым слоем условимся считать множество, состоящее из одного базового многогранника. В общем случае, 𝑁 -ый слой определим рекурсивным образом как множество всех многогранников, отвечающих точкам с координатами {0, ±1, . . . , ±𝑁 }, но не входящих ни в один из предыдущих слоев. Заметим, что точки подрешётки, которым отвечают многогранники 𝑁 -го слоя, лежат на границе некоторого параллелепипеда. Под вписанным шаром 𝑁 -го слоя будем подразумевать шар максимального радиуса, который помещается в параллелепипед, соответствующий этому слою, и имеет центр в начале координат.

Иванов Л. Л. О хроматических числах R2 и R3 с интервалами запрещён‌ . . .

19

Итак, мы разделили многогранники одного цвета на слои, каждый следующий из которых находится все «дальше» от базового многогранника. Следующая лемма даёт простую оценку расстояния между многогранниками. Лемма 3. Пусть 𝑅 — радиус вписанного шара первого слоя, 𝐷 — диаметр многогранника Вороного. Тогда расстояние между базовым многогранником и любым многогранником 𝑁 -го слоя не меньше чем 𝑁 · 𝑅 − 𝐷. Доказательство. Как уже говорилось ранее, все точки подрешётки, которым отвечают многогранники 𝑁 -го слоя, лежат на некотором параллелепипеде, и, очевидно, находятся вне вписанного шара 𝑁 -го слоя. Значит, центры многогранников 𝑁 -го слоя отстоят от начала координат не меньше чем на радиус этого вписанного шара, т.е. на 𝑁 · 𝑅. Отсюда нетрудно вывести искомую оценку. Это означает, что минимальное расстояние нужно искать среди начальных слоев. Также точность оценки из леммы 3 зависит от выбора базиса подрешётки. В некотором смысле оценка будет оптимальной, если взять приведённый базис (см. [13]).  4.3.

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

В дальнейшем будем записывать векторы базисов решётки и подрешётки в виде строк матрицы соответствующего размера. Причём векторы базиса подрешётки будем записывать в координатах базиса решётки. √ Докажем оценку 𝜒𝑑 (R2 ) 6 7 при 𝑑 6

7 . 2

(︂

)︂ 2 0 √ и подрешётку Γ с 3 1

Рассмотрим гексагональную решётку Λ с базисом (︂ )︂ 3 −1 базисом . Как было сказано раньше, решётка задаёт разбиение плоско1 2 сти на многоугольники Вороного, в данном случае это правильные шестиугольники. Индекс подрешётки Γ равен 7, следовательно, она задаёт покраску в 7 цветов. Для доказательства искомого неравенства достаточно показать, что при такой покраске отношение расстояния между шестиугольниками одного цвета к диаметру √ 7

шестиугольника не меньше чем . 2 Вершины базового шестиугольника (см. рис. 1) можно записать в координатах: {︂(︂ )︂ (︂ )︂}︂ 1 2 ±1; ± √ , 0; ± √ (шесть вершин). 3

3

4 3

Диаметр шестиугольника равен √ . Будем рассматривать расстояния между базовым шестиугольником и остальными шестиугольниками базового цвета. Обозначим начало координат через 𝑂. Рассмотрим сначала многоугольники первого слоя (всего их 8). Возьмём шестиугольник, отвечающий точке 𝑃 , где 𝑂𝑃 — это второй вектор базиса подрешётки (вектор (1; 2) в координатах базиса √ решётки Λ). Перепишем точку 𝑃 в общих координатах как (4; 2 3). Нам нужно найти расстояние между базовым шестиугольником и шестиугольником, √ отвеча√ ющим точке 𝑃 (4; 2 3). Ввиду леммы 2, достаточно взять середину 𝑆(2; 3) отрезка 𝑂𝑃 , найти расстояние от неё до базового шестиугольника и умножить на 2. В данном случае минимальное расстояние от точки 𝑆 (︂до базового шестиуголь)︂ ника будет достигаться на вершине 𝐴 с координатами равно √︃ (︂ )︂2 √︂ √ 1 7 2 1 + 3− √ = . 3

3

1 3

1; √

(см. рис. 2); оно

20

Вестник РУДН. Серия Математика. Информатика. Физика. № 1. 2011. С. 14–29

Рис. 2. Ближайшие шестиугольники

Рис. 1. Многоугольник Вороного

√︂ Следовательно, расстояние между шестиугольниками будет равно 2 ношение вычисленного расстояния к диаметру шестиугольника есть √︂ √

7 . От3

7 4 7 :√ = . 3 2 3

2

Рассмотрев ещё пять аналогичных шестиугольников, мы получим тот же самый результат ввиду симметрии (картина остаётся одинаковой при повороте на угол в 60 градусов). А два оставшихся шестиугольника находятся слишком далеко: расстояние от каждого из них до базового шестиугольника можно оценить как разность длины отрезка, соединяющего 𝑂 с центром шестиугольника (она рав√ на 2 21), и диаметра шестиугольника. Тем самым, отношение будет оцениваться снизу величиной (︂ )︂ √ √ √ 4 3 7 7 4 2 21 − √ :√ = −1> . 3

2

3

2

Расстояния до шестиугольников √ других слоев оценим по лемме 3. Радиус впи√ 3 √ санного шара первого слоя равен · 2 7 = 21. Отношение расстояния между 2 базовым шестиугольником и шестиугольником 𝑁 -го слоя к диаметру шестиугольника оценивается как (︂ )︂ √ √ √ √ 4 4 3 7 3 7 7 𝑁 · 21 − √ : √ =𝑁 −1> −1> . 3

3

4

2

2

Приведём доказательство ещё одной оценки √ для случая плоскости. А именно, докажем неравенство 𝜒𝑑 (R2 ) 6 16 при 𝑑 6

3 3 . 2

с базисом (︂ Как )︂и в первом случае, рассмотрим гексагональную решётку (︂ Λ )︂ 2 0 4 0 √ . В качестве подрешётки возьмём решётку Γ с базисом . Индекс 0 4 3 1 подрешётки Γ в данном случае равен 16, следовательно, она задаёт покраску в 16 цветов. Для доказательства искомого неравенства достаточно показать, что при

Иванов Л. Л. О хроматических числах R2 и R3 с интервалами запрещён‌ . . .

21

такой покраске отношение расстояния между √ шестиугольниками одного цвета к диаметру шестиугольника не меньше чем

3 3 . 2

Поскольку мы не меняли решётку Λ, многоугольники Вороного — это те же правильные шестиугольники. Вершины базового шестиугольника записываются в координатах {︂(︂ )︂ (︂ )︂}︂ 1 3

±1; ± √

2 3

, 0; ± √

,

4 3

диаметр шестиугольника равен √ . Далее будем в точности повторять схему рассуждений. Обозначим начало координат через 𝑂. Рассмотрим сначала многоугольники первого слоя. Возьмём шестиугольник, отвечающий точке 𝑃 , где 𝑂𝑃 — это первый вектор базиса подрешётки (вектор (4; 0) в координатах базиса решётки Λ). Перепишем точку 𝑃 в общих координатах как (8; 0). Нам хочется найти расстояние между базовым шестиугольником и шестиугольником, отвечающим точке 𝑃 (8; 0). Ввиду леммы 2, достаточно взять середину 𝑆(4; 0) отрезка 𝑂𝑃 , найти расстояние от неё до базового шестиугольника и умножить на 2. В данном случае минимальное расстояние от точки 𝑆 до базового шестиугольника будет достигаться на перпендикуляре, 1 3

опущенном из точки 𝑆 на сторону шестиугольника с вершинами (1; ± √ ) (как самую ближайшую сторону к точке 𝑆); оно равно 3. Следовательно, расстояние между шестиугольниками будет равно 6. Отношение вычисленного расстояния к диаметру шестиугольника есть √ 4 3 3 √ 6: = . 2 3

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

3 3 . 2

Во всех остальных случаях приведём решётки и подрешётки, необходимые для доказательства соответствующих неравенств. В качестве решётки везде будем (︂ )︂ 2 0 √ . рассматривать решётку 1 3 √ Для(︂доказательства оценки 𝜒𝑑 (R2 ) 6 9 при 𝑑 6 3 = 1, 732 . . . берётся подре)︂ 3 0 шётка . 0 3 (︂ )︂ 2 2 2 Для доказательства оценки 𝜒𝑑 (R ) 6 12 при 𝑑 6 2 берётся подрешётка . 4 −2 √ 19 Для доказательства оценки 𝜒𝑑 (R ) 6 13 при 𝑑 6 = 2, 179 . . . берётся 2 (︂ )︂ 2

подрешётка

1 3 . 4 −1

√ 31 Для доказательства оценки 𝜒𝑑 (R ) 6 19 при 𝑑 6 = 2, 783 . . . берётся 2 (︂ )︂ 2

подрешётка

3 2 . 7 −1

22

Вестник РУДН. Серия Математика. Информатика. Физика. № 1. 2011. С. 14–29

√ 37 = 3, 041 . . . берётся Для доказательства оценки 𝜒𝑑 (R ) 6 21 при 𝑑 6 2 (︂ )︂ 2

подрешётка

1 4 . 5 −1

4.4.

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

Как и в предыдущем доказательстве, будем записывать векторы базисов решётки и подрешётки в виде строк матрицы соответствующего размера. При этом векторы базиса подрешётки будем записывать в координатах базиса решётки. Докажем оценку 𝜒𝑑 (R3 ) 6 18 при 𝑑⎛6 1, 115. ⎞ 0, 849009 −1 −1 0, 849009 −1 ⎠ и подреРассмотрим решётку Λ с базисом ⎝ −1 −1 −1 0, 849009 ⎛ ⎞ 1 −2 1 шётку Γ с базисом ⎝−1 −1 2⎠. Решётка задаёт разбиение пространства на 2 3 1 многогранники Вороного (см. рис. 3).

Рис. 3. Многогранник Вороного

Индекс подрешётки Γ равен 18, и она определяет покраску в 18 цветов. Как и ранее, для доказательства искомого неравенства достаточно показать, что при такой покраске отношение расстояния между многогранниками одного цвета к диаметру многогранника не меньше чем 1, 115. Наши результаты были вычислены при помощи компьютерной программы, и далее мы будем представлять числовые величины в виде десятичных дробей с точностью до последнего выписанного знака после запятой. Наряду с этим соглашением будем также использовать выражение «почти равен», что будет означать равенство с точностью, описанной выше. Выпишем список вершин и граней построенного многогранника Вороного: Вершины: M: 1,046995, -0,046995, -0,424504 A: -0,046995, 1,046995, -0,424505 N: 1,046995, -0,424504, -0,046995 B: -0,424504, 1,046995, -0,046995 O: 0,424504, 0,046995, -1,046995 C: 0,046995, 0,424505, -1,04699 P: 0,424504, -1,046995, 0,046995 D: -1,046995, 0,424504, 0,046995 Q: -0,197986, -0,575495, -0,953005 E: -0,575495, -0,197986, -0,953005 R: -0,197986, -0,953005, -0,575495 F: -0,953005, -0,197986, -0,575495 S: -0,046995, -0,424505, 1,046995 G: 0,953005, 0,575496, 0,197986 T: -0,424505, -0,046995, 1,046995 H: 0,953005, 0,197986, 0,575496 U: 0,046995, -1,046995, 0,424504 I: 0,575496, 0,953005, 0,197986 V: -1,046995, 0,046995, 0,424504 J: 0,197986, 0,953005, 0,575496 K: 0,575496, 0,197986, 0,953005 W: -0,575495, -0,953005, -0,197986 X: -0,953005, -0,575495, -0,197986 L: 0,197986, 0,575496, 0,953005

Иванов Л. Л. О хроматических числах R2 и R3 с интервалами запрещён‌ . . .

23

Грани: Грань №7: J: 0,197986, 0,953005, 0,575496 L: 0,197986, 0,575496, 0,953005 B: -0,424504, 1,046995, -0,046995 T: -0,424505, -0,046995, 1,046995 D: -1,046995, 0,424504, 0,046995 V: -1,046995, 0,046995, 0,424504 Грань №8: Q: -0,197986, -0,575495, -0,953005 R: -0,197986, -0,953005, -0,575495 E: -0,575495, -0,197986, -0,953005 F: -0,953005, -0,197986, -0,575495 W: -0,575495, -0,953005, -0,197986 X: -0,953005, -0,575495, -0,197986 Грань №9: G: 0,953005, 0,575496, 0,197986 H: 0,953005, 0,197986, 0,575496 M: 1,046995, -0,046995, -0,424504 N: 1,046995, -0,424504, -0,046995 Грань №10: I: 0,575496, 0,953005, 0,197986 J: 0,197986, 0,953005, 0,575496 A: -0,046995, 1,046995, -0,424505 B: -0,424504, 1,046995, -0,046995 Грань №11: K: 0,575496, 0,197986, 0,953005 L: 0,197986, 0,575496, 0,953005 S: -0,046995, -0,424505, 1,046995 T: -0,424505, -0,046995, 1,046995 Грань №12: O: 0,424504, 0,046995, -1,046995 C: 0,046995, 0,424505, -1,046995 Q: -0,197986, -0,575495, -0,953005 E: -0,575495, -0,197986, -0,953005 Грань №13: P: 0,424504, -1,046995, 0,046995 U: 0,046995, -1,046995, 0,424504 R: -0,197986, -0,953005, -0,575495 W: -0,575495, -0,953005, -0,197986 Грань №14: D: -1,046995, 0,424504, 0,046995 V: -1,046995, 0,046995, 0,424504 F: -0,953005, -0,197986, -0,575495 X: -0,953005, -0,575495, -0,197986 Диаметр многогранника Вороного равен 2, 261514. Будем рассматривать расстояния между базовым многогранником и остальными многогранниками базового цвета. Обозначим начало координат через 𝑂. Рассмотрим многогранники первого слоя (всего их 26). Возьмём многогранник, отвечающий точке 𝑃 , где 𝑂𝑃 – это третий вектор базиса подрешётки (вектор (2; 3; 1) в координатах базиса решётки Λ). Перепишем точку 𝑃 в общих координатах: (−2, 301982; −0, 452973; −4, 150991). Нам хочется найти расстояние между базовым многогранником и многогранником, отвечающим точке 𝑃 (−2, 301982; −0, 452973; −4, 150991). Снова, ввиду леммы 2, достаточно взять середину 𝑆(−1, 150991; −0, 226486; −2, 075495) отрезка 𝑂𝑃 , найти расстояние от неё до базового многогранника и умножить на 2. В данном случае минимальное расстояние от точки 𝑆 до базового шестиугольника будет достигаться на вершине многогранника 𝐴(−0, 575495; −0, 197986; −0, 953005) (см. Грань №1: A: -0,046995, 1,046995, -0,424505 B: -0,424504, 1,046995, -0,046995 C: 0,046995, 0,424505, -1,046995 D: -1,046995, 0,424504, 0,046995 E: -0,575495, -0,197986, -0,953005 F: -0,953005, -0,197986, -0,575495 Грань №2: G: 0,953005, 0,575496, 0,197986 H: 0,953005, 0,197986, 0,575496 I: 0,575496, 0,953005, 0,197986 J: 0,197986, 0,953005, 0,575496 K: 0,575496, 0,197986, 0,953005 L: 0,197986, 0,575496, 0,953005 Грань №3: M: 1,046995, -0,046995, -0,424504 N: 1,046995, -0,424504, -0,046995 O: 0,424504, 0,046995, -1,046995 P: 0,424504, -1,046995, 0,046995 Q: -0,197986, -0,575495, -0,953005 R: -0,197986, -0,953005, -0,575495 Грань №4: S: -0,046995, -0,424505, 1,046995 T: -0,424505, -0,046995, 1,046995 U: 0,046995, -1,046995, 0,424504 V: -1,046995, 0,046995, 0,424504 W: -0,575495, -0,953005, -0,197986 X: -0,953005, -0,575495, -0,197986 Грань №5: G: 0,953005, 0,575496, 0,197986 I: 0,575496, 0,953005, 0,197986 M: 1,046995, -0,046995, -0,424504 A: -0,046995, 1,046995, -0,424505 O: 0,424504, 0,046995, -1,046995 C: 0,046995, 0,424505, -1,046995 Грань №6: H: 0,953005, 0,197986, 0,575496 K: 0,575496, 0,197986, 0,953005 N: 1,046995, -0,424504, -0,046995 S: -0,046995, -0,424505, 1,046995 P: 0,424504, -1,046995, 0,046995 U: 0,046995, -1,046995, 0,424504

24

Вестник РУДН. Серия Математика. Информатика. Физика. № 1. 2011. С. 14–29

рис. 4); оно почти равно 1, 261742.

Рис. 4. Ближайшие многогранники

Расстояние между многогранниками будет почти равно 2, 523484. Отношение вычисленного расстояния к диаметру многогранника оценивается снизу как 2, 52348 : 2, 261515 > 1, 115. Рассмотрим 11 многогранников первого слоя, отвечающих следующим вершинам с координатами, записанными в базисе подрешётки: 0, 0, −1; 1, 0, −1; 0, 1, −1; 0, −1, 0; 1, −1, 0; −1, 0, 0; 1, 0, 0; −1, 1, 0; 0, 1, 0; 0, −1, 1; −1, 0, 1. Расстояния от них до базового многогранника будут почти равны 2, 52348. Отношения этих величин к диаметру многогранника будут также больше 1, 115. Остальные многогранники находятся слишком далеко от базового. Если быть более точным, отношение расстояния от любого из них до базового к диаметру многогранника больше 2. Чтобы оценить расстояния от базового многогранника до многогранников остальных слоев, нам нужна величина радиуса 𝑅 вписанного шара певого слоя, которая почти равна 3, 772001. Обозначим диаметр многогранника через 𝐷. Тогда, исходя из леммы 3, каждое из расстояний будет оценено снизу величиной 2𝑅 − 𝐷 > 2 · 3, 772001 − 2, 261515 = 5, 282487. А отношение этой величины к диаметру больше 1, 115: 5, 282487 : 2, 261515 > 1, 115. Таким образом отношение любого расстояния между многогранниками одного цвета к диаметру многогранника не превосходит указанную в начале доказательства величину 1, 115, что и требовалось показать.

Иванов Л. Л. О хроматических числах R2 и R3 с интервалами запрещён‌ . . .

25

Во всех остальных случаях приведём решётки и подрешётки, необходимые для доказательства соответствующих неравенств. В качестве решёток будем рассматривать решётки вида ⎛ ⎞ 𝑎 𝑏 𝑏 diag(𝑎; 𝑏) = ⎝ 𝑏 𝑎 𝑏 ⎠ . 𝑏 𝑏 𝑎 3 Для доказательства оценки 𝜒 ⎛𝑑 (R ) 6 21 ⎞ при 0 −1 1 𝑑𝑖𝑎𝑔(1; −0, 246656) и подрешётка ⎝0 1 3⎠ . 3 0 1 3 Для доказательства оценки 𝜒 ⎛𝑑 (R ) 6 23 при ⎞ 0 −2 1 𝑑𝑖𝑎𝑔(1; −0, 750981) и подрешётка ⎝−3 −2 −4⎠ . 2 −1 0 3 Для доказательства оценки 𝜒 (R 𝑑 ⎞) 6 24 при ⎛ −2 1 1 ⎝ 2 3 3⎠ . 𝑑𝑖𝑎𝑔(1; −1) и подрешётка 2 3 0 Для доказательства оценки 𝜒𝑑⎞ (R3 ) 6 27 при ⎛ 3 0 0 ⎝ 𝑑𝑖𝑎𝑔(1; −1) и подрешётка 0 3 0⎠ . 0 0 3

5.

𝑑 6 1, 133 берётся решётка

𝑑 6 1, 137 берётся решётка

𝑑 6 1, 303 берётся решётка

𝑑 6 1, 549 берётся решётка

Комментарии

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

Примеры кубических покрасок

В плоскости существует наглядная покраска квадратами в 9 цветов, дающая простую оценку на классическое хроматическое число в плоскости. Её можно интерпретировать как получаемую при помощи метода (︂ )︂ решетчатую (︂покраску, )︂ 1 0 3 0 для решётки и подрешётки . 0 1 0 3 То же самое разбиение (︂ )︂ на квадраты можно раскрасить и в 8 цветов при помо3 −1 щи подрешётки . 2 2 По аналогии с плоскостью, в пространстве также существует простая покраска кубами в 27 цветов, дающая оценку на классическое хроматическое ⎛ число про⎞ 1 0 0 странства. Её можно получить описанным методом для решётки ⎝0 1 0⎠ и 0 0 1 ⎛ ⎞ 3 0 0 подрешётки ⎝0 3 0⎠ . 0 0 3 Это же разбиение можно перекрасить, задействовав⎛на один цвет ⎞ меньше. 3 −1 0 Покраска в 26 цветов задаётся при помощи подрешётки ⎝2 2 −2⎠ . 1 0 3

26

Вестник РУДН. Серия Математика. Информатика. Физика. № 1. 2011. С. 14–29

5.2.

«Почти правильная» покраска плоскости в 6 цветов

Как известно, в плоскости до сих пор не найдено правильной покраски в 6 цветов или менее с одним запрещённым расстоянием. При помощи метода решетчатых разбиений можно привести пример «почти правильной» покраски в 6 цветов. Она реализует все расстояния между точками одного цвета, но минимальное расстояние между многоугольниками одного цвета лишь на сотую долю меньше диаметра многоугольника (см. рис. 5).

Рис. 5. Почти правильная покраска плоскости в 6 цветов

(︃ √ √ )︃ (︂ )︂ 2+ 2 − 2 3 0 √ Покраска задаётся решёткой и подрешёткой . 2 1 1 3 Отношение минимального расстояния между многоугольниками одного цвета к диаметру равно √︁ 2+

5.3.

√︀ √ 2+ 3 = 0, 99144 . . . 2

Многоугольное хроматическое число «разрежённости»

Отметим, что во всей статье рассматривались раскраски плоскости (пространства), в которых множества точек одного цвета были устроены относительно просто, а именно, состояли из счётного объединения многоугольников (многогранников) с точностью до их границ. Несмотря на большую свободу при покраске, до сих пор не было придумано принципиально других раскрасок, которые позволили бы улучшить верхнюю оценку классического хроматического числа или хроматического числа с интервалом запрещённых расстояний. Ввиду этого умест𝑛 но ввести определение многоугольного хроматического числа 𝜒𝑃 𝑑 (R ) плоскости (пространства) с интервалом запрещённых расстояний, т.е. минимального числа цветов, в которые можно так покрасить всю плоскость (пространство), чтобы между точками одного цвета не было запрещённого расстояния, и вместе с этим цвета представляли бы собой не более чем счётные объединения многоугольников (многогранников) с точностью до их границ. Все приведённые нами выше верхние оценки будут также верны для многоугольного хроматического числа. В статье [17] приведено определение более общего понятия, измеримого хроматического числа пространства, в котором цвета представляют множества с измеримой по Жордану границей. В случае плоскости доказана оценка 6 снизу для

Иванов Л. Л. О хроматических числах R2 и R3 с интервалами запрещён‌ . . .

27

измеримого хроматического числа в классическом варианте, т. е. с одним запрещённым расстоянием. 𝑛 Следующее понятие введём с целью определить хроматическое число 𝜒𝑃 𝑑 (R ) для 𝑑 < 1 и представить ряд ещё некоторых результатов как оценки сверху для этой величины. Определение 5. Многоугольным хроматическим числом «разрежённости» 𝑛 𝑛 𝑛 𝜒 ̃︀𝑃 𝑑 (R ) плоскости (пространства) R R назовём минимальное число цветов, в которое можно так покрасить всю плоскость (пространство), чтобы цвета представляли собой не более чем счётные объединения многоугольников (многогранников) с точностью до их границ, причём диаметр каждого многоугольника (многогранника) был бы не больше 1, а расстояния между разными многоугольниками (многогранниками) одного цвета не меньше 𝑑. В случае 𝑑 > 1 мы получаем равенство 𝑛 𝑃 𝑛 𝜒 ̃︀𝑃 𝑑 (R ) = 𝜒𝑑 (R ).

Приведём оценки на хроматическое число разрежённости в плоскости и пространстве для разных значений 𝑑 < 1. В каждом случае укажем решётку и подрешётку, с помощью которых было получено неравенство. Теорема 4. В случае плоскости имеют место следующие результаты: (︂ )︂ 2 0 1 𝑃 2 √ , 1. При всех 𝑑 6 = 0.5 выполнено неравенство 𝜒 ̃︀𝑑 (R ) 6 3. Решётка 2 1 3 (︂ )︂ 2 −1 подрешётка . 1 1 √ 3 2 2. При всех 𝑑 6 = 0, 866 . . . выполнено неравенство 𝜒 ̃︀𝑃 𝑑 (R ) 6 4. Решётка 2 )︂ (︂ )︂ (︂

2 0 √ , подрешётка 3 1 √︁ 2+

2 0

0 . 2

√︀ √ 2+ 3 2 = 0, 991 . . . выполнено неравенство 𝜒 ̃︀𝑃 𝑑 (R ) 6 6. 2 √ )︃ (︂ )︂

3. При всех 𝑑 6 (︃ √ 2+ 2 − 2 √ Решётка , подрешётка 1 3

2 0

1 . 3

Теорема 5. В случае трёхмерного пространства имеют место оценки: 𝑃 3 1. При всех 𝑑 6 0, 316 выполнено неравенство 𝜒 ̃︀ ⎛ ⎞𝑑 (R ) 6 4. 1 0 3 ⎝ Решётка 𝑑𝑖𝑎𝑔(1; −1), подрешётка 0 1 3⎠ . 0 0 4 3 2. При всех 𝑑 6 0, 404 выполнено неравенство⎛𝜒 ̃︀𝑃 𝑑 (R ) 6 ⎞ 5. 1 0 4 Решётка 𝑑𝑖𝑎𝑔(1; −0, 816322), подрешётка ⎝0 1 4⎠ . 0 0 5 3 3. При всех 𝑑 6 0, 447 выполнено неравенство⎛𝜒 ̃︀𝑃 𝑑 (R ) 6 ⎞ 6. 1 0 2 Решётка 𝑑𝑖𝑎𝑔(1; −0, 718788), подрешётка ⎝0 1 2⎠ . 0 0 6 3 4. При всех 𝑑 6 0, 468 выполнено неравенство⎛𝜒 ̃︀𝑃 𝑑 (R ) 6 ⎞ 7. 1 0 6 Решётка 𝑑𝑖𝑎𝑔(1; −0, 366288), подрешётка ⎝0 1 6⎠ . 0 0 7

28

Вестник РУДН. Серия Математика. Информатика. Физика. № 1. 2011. С. 14–29

3 𝑃 5. При всех 𝑑 6 0, 774 выполнено неравенство 𝜒 ̃︀ ⎛ ⎞𝑑 (R ) 6 8. 2 0 0 ⎝ Решётка 𝑑𝑖𝑎𝑔(1; −1), подрешётка 0 2 0⎠ . 0 0 2 3 6. При всех 𝑑 6 0, 844 выполнено 𝜒 ̃︀𝑃 𝑑 (R ) 6 12. Решётка ⎛ неравенство ⎞ 1 1 3 𝑑𝑖𝑎𝑔(1; −0, 703622), подрешётка ⎝0 2 0⎠ . 0 0 6 3 7. При всех 𝑑 6 0, 876 выполнено 𝜒 ̃︀𝑃 𝑑 (R ) 6 14. Решётка ⎛ неравенство ⎞ 1 0 3 𝑑𝑖𝑎𝑔(1; −0, 147065), подрешётка ⎝0 1 7 ⎠ . 0 0 14

6.

Заключение

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

Литература 1. Демидович Б. П. Лекции по математической теории устойчивости. — М.: Наука, 1967. — 472 с. [Demidovich B. P. Lekcii po matematicheskoyj teorii ustoyjchivosti. — M.: Nauka, 1967. — 472 s.] 2. Soifer A. Chromatic Number of the Plane: a Historical Essay // Geombinatorics. — 1991. — Pp. 13–15. 3. Сойфер А. Хроматическое число плоскости: его прошлое, настоящее и будущее // Матем. просвещение. — 2004. — № 8. [Soyjfer A. Khromaticheskoe chislo ploskosti: ego proshloe, nastoyathee i buduthee // Matem. prosvethenie. — 2004. — No 8.] 4. Brass P., Moser W., Pach J. Research Problems in Discrete Geometry // Springer. — 2005. 5. Райгородский А. М. Проблема Борсука и хроматические числа метрических пространств // Успехи Мат. Наук. — 2001. — № 56. — С. 107–146. [Rayjgorodskiyj A. M. Problema Borsuka i khromaticheskie chisla metricheskikh prostranstv // Uspekhi Mat. Nauk. — 2001. — No 56. — S. 107–146.] 6. Sz´ekely L. A. Erd¨os on Unit Distances and the Szemer´edi – Trotter Theorems // Paul Erd¨os and his Mathematics, Bolyai Series Budapest, J. Bolyai Math. Soc., Springer. — 2002. — No 11. — Pp. 649–666. 7. Nechushtan O. Note on the Space Chromatic Number // Discrete Mathematics. — 2002. — No 256. — Pp. 499–507. 8. Coulson D. A 15-coloring of 3-space Omitting Distance One // Discrete Mathematics. — 2002. — No 256. — Pp. 83–90. 9. Иванов Л. Л. Оценка хроматического числа пространства R4 // Успехи Мат. Наук. — 2006. — № 61. — С. 371–372. [Ivanov L. L. Ocenka khromaticheskogo chisla prostranstva R4 // Uspekhi Mat. Nauk. — 2006. — No 61. — S. 371–372.]

Иванов Л. Л. О хроматических числах R2 и R3 с интервалами запрещён‌ . . .

29

10. Райгородский А. М. О хроматическом числе пространства // Успехи Мат. Наук. — 2000. — № 55. — С. 147–148. [Rayjgorodskiyj A. M. O khromaticheskom chisle prostranstva // Uspekhi Mat. Nauk. — 2000. — No 55. — S. 147–148.] 11. Larman D. G., Rogers C. A. The Realization of Distances within Sets in Euclidean Space // Mathematika. — 1972. — No 19. — Pp. 1–24. 12. Coulson D. On 18-colouring of 3-space Omitting Distance One // Discrete Mathematics. — 1997. — No 170. — Pp. 241–247. 13. Конвей Дж., Слоэн Н. Упаковки шаров, решетки и группы. — Москва: Мир, 1990. [Konveyj Dzh., Sloehn N. Upakovki sharov, reshetki i gruppih. — Moskva: Mir, 1990.] 14. Gruber P. M., Lekkerkerker C. G. Geometry of Numbers. — Amsterdam: NorthHolland, 1987. 15. Касселс Дж. Введение в геометрию чисел. — Москва: Мир, 1965. [Kassels Dzh. Vvedenie v geometriyu chisel. — Moskva: Mir, 1965.] 16. Вороной Г. Ф. Собрание сочинений в 3-х томах. — Киев: АН УССР, 1952. 17. Woodall D. R. Distances Realized by Sets Covering the Plane // Combinatorics Theory Ser. A, year = 1973, number = 14, pages = 187–200, language = english. —

UDC 514.174.5

On the Chromatic Numbers of R2 and R3 with an Interval of Forbidden Distances L. L. Ivanov Department of Physical, Mathematical and Natural Sciences Peoples’ Friendship University of Russia 6, Miklukho–Maklaya str., Moscow, 117198, Russia

In this article there defined one of generalization of classical notion of chromatic number of a plane or a space defined, that is chromatic number with an interval of forbidden distances. Some upper bounds are obtained for this value with different intervals and the method of finding these results are described. Key words and phrases: chromatic number, forbidden distance.

View more...

Comments

Copyright © 2017 UPDOC Inc.