Исследование оптимальных конфигураций в задачах о хроматическом числе пространства и проблеме Борсука

• Автор: Иванов, Леонид Львович
• Шифр специальности: 05.13.17, 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2011
• Место защиты: Москва
• Количество страниц: 62 с. : ил.

Оглавление

1 История и формулировки результатов

1.1 История задачи о хроматическом числе.

1.2 Формулировки результатов в задаче о хроматическом числе

1.3 История проблемы Борсука.

1.4 Формулировки результатов в проблеме Борсука . .

2 Доказательства результатов для хроматических чисел

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

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

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

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

2.3.2 Вспомогательные геометрические леммы . .
2.3.3 Доказательство теоремы 3
2.3.4 Доказательство теоремы 4
2.4 Комментарии
2.4.1 Примеры кубических покраскок
2.4.2 Почти правильная покраска плоскости в
цветов
2.4.3 Многоугольное хроматическое число разреженности .
3 Доказательства результатов в проблеме Борсука
3.1 Доказательство теоемы 5.
3.1.1 Общий план доказательства.
3.1.2 Конструкция множества
3.1.3 Отображение хнх
3.1.4 Лемма о мощности подмножества 2 с запретами
3.1.5 Завершение доказательства теоремы.
3.2 Дополнительные замечания
Введение
Актуальность


Однако довольно быстро стало понятно, что, с одной стороны, задача о раскраске пространства — это очень глубокая проблема, затрагивающая самую суть дискретной геометрии, а с другой стороны, она вовсе не замкнута сравнительно узкими рамками одной лишь комбинаторно-геометрической дисциплины, но напрямую связана с различными актуальными проблемами теории графов и теории кодирования. Во многом такому развитию данной проблематики поспособствовали многочисленные работы П. Эрдеша и популяризаторская деятельность М. Гарднера (см. С классической теорией графов задача о раскраске пространства связана следующим образом. V является набором (возможно, бесконечным) точек в а множество его ребер Е состоит из пар вершин, расстояние между которыми принадлежит множеству Л. Очевидно, что если взять максимальное из обычных хроматических чисел дистанционных графов, то получится ровно х(Еп; Л). Поскольку задача о раскраске графа является одной из центральных в теории графов и ее приложениях в теоретической информатике, а сами дистанционные графы служат отличными моделями для различных объектов, возникающих на практике, то задача о раскраске дистанционного графа имеет особую значимость и актуальность. С теорией кодирования задача о величине хО^;^) соприкасается сразу в двух “точках”. Во-первых, еще в году классики теории упаковок пространств Д. Ларман и К. А. Роджерс показали, что верхние оценки хроматического числа самым тесным образом связаны с вопросами построения плотнейших решетчатых упаковок шаров и наиболее в некотором смысле экономных разбиений Вороного, отвечающих решеткам (см. Во-вторых, нижние оценки хроматических чисел — это, по сути, верхние оценки мощности равновесного кода с одним или многими запрещенными расстояниями Хэмминга. Задача получения подобных оценок — важнейшая в теории кодирования, и ей занимались многочисленные ведущие специалисты в области (см. Более того, здесь есть выход и на теорию однородных гиперграфов с запрещенными пересечениями ребер, которой посвящено огромное количество работ в мире (см. Таким образом, сразу несколько важнейших проблем теоретической информатики тесно переплетаются с задачей раскраски пространства. Если задача об одном запрещенном расстоянии появилась исторически первой, то, едва стала ясна значимость такой проблематики, как возникли и различные важные обобщения исходного хроматического числа. Rn. В случае нескольких запретов следует различать ситуации, когда этих запретов конечное число и когда их бесконечное количество. Конечные множества запретов исследовал Эрдеш с учениками (см. Сейчас наилучшие результаты в этой области принадлежат А. М. Рай городскому, В. К). Протасову, И. М. Мит-ричевой и Е. С. Горской (см. И]). Задачи о бесконечных множествах запретов тесно примыкают к вопросам теории диофантовых приближений и потому также крайне актуальны (см. Среди других метрических пространств, которыми активно занимались и продолжают заниматься крупнейшие специалисты, стоит отметить пространство R7* с произвольной нормой (см. Qn с метрикой lq (см. S"“1 радиуса г с евклидовой метрикой (см. Также в диссертации рассматривается еще одна классическая задача комбинаторной геометрии — проблема Борсука, состоящая в отыскании минимального числа f(n) частей меньшего диаметра, на которые разбивается произвольное множество диаметра 1 в Мп. Эта. К. Борсуком в году (см. С точки зрения теории графов, важны так называемые графы диалютров G = (V, Е), у которых V С а Е — это множество пар вершин, отстоящих друг от друга на расстояние, равное диаметру V. Хроматические числа этих графов, по сути, и равны минимальным количествам частей меньшего диаметра, на которые разбиваются их множества вершин. Задачам о графах диаметров посвящена огромная литература (см. На стыке топологии и теории графов находится топологический метод в комбинаторике, основанный на применении теоремы Борсука-Улама в задачах раскраски графов (см. Наконец, для теории кодирования исключительно важны спецификации проблемы Борсука для случаев Хэммииговых пространств.