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

Иванов Леонид Львович

ИССЛЕДОВАНИЕ ОПТИМАЛЬНЫХ КОНФИГУРАЦИЙ В ЗАДАЧАХ О ХРОМАТИЧЕСКОМ ЧИСЛЕ ПРОСТРАНСТВА И ПРОБЛЕМЕ БОРСУКА

05.13.17 — теоретические основы информатики 01.01.09 дискретная математика и математическая кибернетика

Автореферат

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

Москва 2011

2 1 ДПР 2011

4844216

Работа выполнена на факультете физико-математических наук Российского университета дружбы народов.

Научные руководители: доктор физико-математических наук,

профессор

Арутюнов Арам Владимирович

доктор физико-математических наук, профессор

Райгородский Андрей Михайлович

Официальные оппоненты: доктор физико-математических наук,

Кабатянский Григорий Анатольевич

кандидат физико-математических наук, Дайняк Александр Борисович

Ведущая организация: Хабаровское отделение Института

прикладной математики ДВО РАН

Защита диссертации состоится "13" мая 2011 г. в 17 часов 00 минут на заседании диссертационного совета Д 212.203.28 в Российском университете дружбы народов по адресу: г. Москва, ул. Орджоникидзе, дом 3, ауд. 110.

С диссертацией можно ознакомиться в Научной библиотеке Российского унивеснтета дружбы народов по адресу: 117198, г. Москва, ул. Миклухо-Маклая, д.6. (Отзывы на автореферат просьба направлять по указанному адресу.)

Автореферат разослан " " апреля 2011 г.

Ученый секретарь диссертационного совета

С» М.Б.Фомин

Общая характеристика работы

Актуальность темы.

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

Прежде всего речь идет о хрохштических числах евклидо-

вых пространств R" с множествами запрещенных расстояний А. Здесь х(Кп; А) — минимальное число цветов, в которые можно так покрасить все точки пространства R", чтобы между одноцветными точками не было расстояния, принадлежащего множеству А.

Впервые задача о хроматическом числе была поставлена на рубеже 40ых и 50ых годов XX века Э. Нелсоном и Г. Хадвигером1,2. На тот момент эта задача воспринималась исключительно как вопрос геометрической комбинаторики. Более того, в качестве множества Л запрещенных расстояний рассматривалось только множество А — {1}, состоящее из одного элемента. Однако довольно быстро стало понятно, что, с одной стороны, задача о раскраске пространства — это очень глубокая проблема, затрагивающая самую суть дискретной геометрии, а с другой стороны, она вовсе не замкнута сравнительно узкими рамками одной лишь комбинаторно-геометрической дисциплины, но напрямую связана с различными актуальными проблемами теории графов и теории кодирования. Во многом такому развитию данной проблематики поспособствовали многочисленные работы П. Эрдеша и популяризаторская деятельность М. Гарднера3, 4' 5.

С классической теорией графов задача о раскраске пространства связана следующим образом. Назовем граф G — (V, Е) дистанционным, если множество его вершин V является набором (возможно, бесконечным) точек в К", а множество его ребер Е состоит из пар вершин, расстояние между которыми принадлежит множеству А. Очевидно, что если взять максимальное из обычных хроматических чисел дистанционных графов, то получится ровно x(]Rn;.A).

1 Н. Iladwiger, Ein Überdeckungssatz für den Euklidischen Raum, Portugaliae Math., 4 (1944), 140 - 144.

Hadwiger, Ungelöste Probleme N 40, Elemente der Math., 16 (1961), 103 - 104.

Erdos, Some unsolved problems, MTA MKI Kozl., 6 (1961), 221 - 254.

4P. Erdos, On some problems of elementary and combinatorial geometry, Ann. Math. Pure Appl., (4) 103 (1975), 99 - 108.

5M. Gardner, A new collection of brain teasers, Scientific American, 206 (Oct. 1960), 172 - 180.

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

С теорией кодирования задача о величине соприкасается сра-

зу в двух "точках". Во-первых, еще в 1972 году классики теории упаковок пространств Д. Ларман и К.А. Роджерс показали, что верхние оценки хроматического числа самым тесным образом связаны с вопросами построения плотнейших решетчатых упаковок шаров и наиболее в некотором смысле экономных разбиений Вороного, отвечающих решеткам6'7. Во-вторых, нижние оценки хроматических чисел это, по сути, верхние оценки мощности равновесного кода с одним или многими запрещенными расстояниями Хэмминга. Задача получения подобных оценок — важнейшая в теории кодирования, и ей занимались многочисленные ведущие специалисты в области8. Более того, здесь есть выход и на теорию однородных гиперграфов с запрещенными пересечениями ребер, которой посвящено огромное количество работ в мире9. Таким образом, сразу несколько важнейших проблем теоретической информатики тесно переплетаются с задачей раскраски пространства.

Если задача об одном запрещенном расстоянии появилась исторически первой, то, едва стала ясна значимость такой проблематики, как возникли и различные важные обобщения исходного хроматического числа. Среди этих обобщений наибольшую роль играют рассматриваемые нами хроматические числа с несколькими запрещенными расстояниями и изучаемые многими авторами хроматические числа метрических пространств, отличных от R". В случае нескольких запретов следует различать ситуации, когда этих запретов конечное число и когда их бесконечное количество. Конечные множества запретов исследовал Эрдеш с учениками10. Сейчас наилучшие результаты в этой области принад-

6 D.G. Larman and С.А. Rogers, The realization of distances within sets in Euclidean space, Mathematika, 19 (1972), 1 - 24.

7 Дж. Конвей и H. Слоэн, Упаковки шаров, решетки и группы, Москва, "Мир", 1990.

s Ф.Дж. Мак-Вильямс и Н.Дж.А. Слоэн, Теория кодов, исправляющих ошибки, Москва, "Связь", 1979.

»A.M. Райгородский, "Линейно-алгебраический метод в комбинаторике". Москва, МЦНМО, 2007.

10L.A. Székely, Erdôs on unit distances and the Szemerédi - Trotter theorems, Paul Brdôs and Iiis Mathematics, Bolyai Series Budapest, J. Bolyai Math. Soc., Springer, 11 (2002), 649 - 666.

лежат A.M. Рангородскому, В.Ю. Протасову, И.М. Митричевой и Е.С. Горской11. Задачи о бесконечных множествах запретов тесно примыкают к вопросам теории диофантовых приближений и потому также крайне актуальны12. Среди других метрических пространств, которыми активно занимались и продолжают заниматься крупнейшие специалисты, стоит отметить пространство R" с произвольной нормой13, пространство с метрикой 1яи и сферу S"-1 радиуса г с евклидовой метрикой13.

Также в диссертации рассматривается еще одна классическая задача комбинаторной геометрии — проблема Борсука, состоящая в отыскании минимального числа /(п) частей меньшего диаметра, на которые разбивается произвольное множество диаметра 1 в R". Эта задача была поставлена К. Борсуком в 1933 году16, и к настоящему времени она, а равно разрабатываемые для ее решения методы одинаково актуальны как в исходной области, так и в топологии, и в теории графов, и в теории кодирования.

С точки зрения теории графов, важны так называемые графы диалшп-ров G = (V, Е), у которых V С R", а Е — это множество пар вершин, отстоящих друг от друга на расстояние, равЕюе диаметру V. Хроматические числа этих графов, по сути, и равны минимальным количествам частей меньшего диаметра, на которые разбиваются их множества вершин. Задачам о графах диаметров посвящена огромная литература17.

На стыке топологии и теории графов находится топологический метод в комбинаторике, основанный на применении теоремы Борсука-Улама в задачах раскраски графов18.

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

11 Е.С. Горская, И.М. Мнтричева, В.Ю. Протасов, A.M. Райгородский, Оценка хроматических чисел евклидова пространства методами выпуклой оптимизации, Ма-тем. сборник, 200 (2009), N6, 3 - 22.

12Y. Katznelson, Chromatic numbers of Cayley graphs on Z and recurrence, Combinatorica, 21 (2001), 211 - 219.

"A.B. Kupavskii, On the chromatic number of K" with an arbitrary norm, Discrete Math., 311 (2011), 437 - 440.

"A.M. Райгородский, О хроматическом числе пространства с метрикой lq, Успехи матем. наук, 59 (2004), N5, 161 - 162.

15А.М. Райгородский, Контрпримеры к гипотезы Борсука на сферах малого радиуса, Доклады РАН, 434 (2010), N2, 1G1 - 163.

16К. Borsuk, Drei Sätze über die n-dimensional?. Rukli.difr.he Sphäre, Fundamenta Math.,

20 (1933), 177 - 190.

"P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, Springer, 2005.

™J. Matousek, Using the Borsuk - Ulam theorem, Universitcxt, Springer, Berlin, 2003.

в этих пространствах впервые был найден контрпример к гипотезе Бор-сука о том, что f(n) = п + 1. Стоит отметить, что гипотеза держалась с 1933 по 1993 год, пока ее не опровергли Дж. Кан и Г. Калаи, которые именно с помощью методов теории кодирования и теории гиперграфов показали, что /(п) > (1.203... + o(l))v^®19. Также стоит упомянуть работу Г.М. Циглера, в которой благодаря кодам наоборот доказывается гипотеза Борсука для (ОД)-многогранников в малых размерностях20. В русле этой работы находится серия статей A.M. Райгородского, в которой даются верхние оценки хроматических чисел графов диаметров с вершинами в точках решеток21,22. Наконец, тесно связаны проблемы упаковок шаров в пространстве и верхние оценки величины /(п)23.

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

Цель работы и основные задачи. Основными задачами работы являются верхние и нижние оценки хроматических чисел с одним запрещенным расстоянием и отрезками запрещенных расстояний, а также построение контрпримеров к гипотезе Борсука на сферах малого радиуса и сравнительно малой размерности. Цель работы состоит в развитии техники упаковок, восходящей к Ларману и Роджерсу, и линейно-алгебраической техники в теории кодирования и теории графов.

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

Научная новизна. Все результаты диссертации являются новыми.

Теоретическая и практическая значимость полученных ре-

lgJ. Kahn, G. Kalai, A counterexample to Borsuk's conjecture, Bulletin (new series) of the AMS, 29 (1993), N1, 60 - 62.

!0G.M. Ziegler, Coloring Hamming graphs, optimal binary codes, and the 0/1 - Borsvk problem in low dimensions, Lect. Notes Comput. Sei., 2122 (2001), 159 - 171.

21 A.M. Райгородский, Проблема Борсука для (0,1) - многогранников и кросс - политопов, Доклады РАН, 384 (2002), 593 - 597.

22A.M. Райгородский, Проблема Борсука для целочисленных многогранников, Ма-тем. сборник, 193 (2002), N10, 139 - 160.

23J. Bourgain, J. Lindenstrauss, On covering a set in by balls of the same diameter, Geometric Aspects of Functional Analysis (J. Lindenstrauss and V. Milman, eds.), Lecture Notes in Math., 1469, Springer-Verlag, Berlin, 1991, 138 - 144.

зультатов. Диссертация носит теоретический характер. Полученные в ней результаты дают новую информацию о графах расстояний и графах диаметров в Ж" и на сферах 5"-1 С Rn. Эти результаты важны для теории графов, теории кодирования и для комбинаторной геометрии. Они могут быть полезны специалистам Российского университета дружбы народов, Института проблем передачи информации им. A.A. Харкеви-ча РАН, механико-математического факультета МГУ им. М.В. Ломоносова, факультета вычислительной математики и кибернетики МГУ им. М.В. Ломоносова, факультета инноваций и высоких технологий МФТИ, Хабаровского отделения Института прикладной математики ДВО РАН и др. Они могут быть использованы при чтении обязательных и специальных курсов, связанных с теоретической информатикой и дискретной математикой.

Основные положения диссертации, выносимые на защиту.

1. Построен новый пример графа расстояний в К4 с одним запрещенным расстоянием и с хроматическим числом 7.

2. Доказана серия новых верхних оценок для хроматических чисел плоскости с отрезками запрещенных расстояний. В частности, получены неравенства

Развита техника упаковок.

3. Доказана серия новых верхних оценок для хроматических чисел М3 с отрезками запрещенных расстояний. В частности, получены неравенства

х (R3; [1,1.115]) < 18, X (R3; [1,1-133]) < 21, Х (R3; [1,1-137]) < 23.

Развита техника упаковок. 4. Построены контрпримеры к гипотезе Борсука на сферах, имеющих

мер, есть контрпример в размерности 561 на сфере радиуса 0.707..., есть контрпример в размерности 1830 на сфере радиуса 0.704..., есть контрпример в размерности 2080 на сфере радиуса 0.700..., есть контрпример в размерности 2926 на сфере радиуса 0.698... Развита линейно-алгебраическая техника.

радиусы г £

достаточно малые размерности. Напри-

Личный вклад соискателя. Все результаты диссертации получены соискателем самостоятельно.

Апробация результатов. Результаты диссертации докладывались на международной конференции "Шестой Чехословацкий Симпозиум по Комбинаторике, Теории Графов, Алгоритмам и Приложениям" в Праге (Чехия, 2006 г.), на международной конференции "Горизонты Комбинаторики" в Балатональмади (Венгрия, 2006 г.), на IX международном семинаре "Дискретная математика и ее приложения", посвященном 75-летию со дня рождения академика О.Б. Лупанова (Москва, 2007 г.), на международной конференции "Европейская Комбинаторика" в Севилье (Испания, 2007 г.), а также на кафедральном семинаре кафедры математической статистики и случайных процессов механико-математического факультета МГУ им. М.В. Ломоносова, на семинаре проф. C.B. Коняги-на в МГУ им. М.В. Ломоносова, на семинаре проф. Н.Г. Мощевитина п проф. Н.П. Долбилина в МГУ им. М.В. Ломоносова, на семинаре проф. A.M. Райгородского в МГУ им. М.В. Ломоносова и др.

Опубликованность результатов. Результаты диссертации опубликованы в шести работах. Список этих работ приведен в конце автореферата.

Структура и объем диссертации. Диссертация состоит из введения, трех глав, списка литературы. Полный объем диссертации 62 страницы, из них 6 страниц занимает список литературы (73 наименования).

Содержание работы

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

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

В параграфе 1.1 детально обсуждается задача о хроматическом числе пространства R™ и ее обобщения на произвольные метрические пространства. В параграфе 1.2 приводятся результаты соискателя. Прежде всего формулируется следующая теорема.

Теорема 1. Верна оценка x(R4; {1}) > 7.

Эта теорема воспроизводит оценку К. Кантвелла 1996 года24. Однако конструкция, доказывающая ее и состоящая в построении дистанционного графа в R4, существенно проще ранее известной.

Далее приводятся новые верхние оценки величин xi®1; £ 1, ойj), х(®2; [l,d]), х(®3; [Ijd])- Это теоремы 2-4, которые мы явно выписываем ниже.

Теорема 2. Выполнено равенство ^(К1; [1, d\) = ¡d] + 1.

Теорема 3. В случае плоскости имеют место следующие результаты:

• При всех d < ^ = 1.322... выполнено неравенство х(К2; [l,d]) < 7.

• При всех d < л/3 = 1.732... выполнено неравенство х(®2> [1, d]) < 9.

• При всех d< 2 выполнено неравенство х(®2; [1|<^]) < 12-

• При всех d < = 2.179... выполнено неравенство х(®2; [li^D ^ 13.

• При всех d < = 2.598... выполнено неравенство х(®2! 16.

• При всех d < — 2.783... выполнено неравенство x(R2;[l,d]) < 19.

• При всех d < — 3.041... выполнено неравенство х(®2! [1, < 21._

21К. Cantwell, Finite Euclidean Ramsey theory, J. Combin. Theory A, 73 (1996), N2, 273 - 285.

Теорема 4. В случае трехмерного пространства имеют место оценки:

• При всех d < .1.115 выполнено неравенство [l,d]) < 18.

• При всех d < 1.133 выполнено неравенство x(R3; [1 -, < 21.

• При всех d < 1.137 выполнено неравенство х(®3; [1 -, d\) < 23. При всех d < 1.303 выполнено неравенство х(®3; [1, à!]) < 24. При всех d < 1.549 выполнено неравенство х(Ж3; [l,d]) < 27.

В параграфе 1.3 рассказывается история проблемы Борсука, а также вводится величина /г(п), равная минимальному числу частей меньшего диаметра, на которые разбивается произвольное множество диаметра 1 на сфере 5""1 С К" радиуса г >

В параграфе 1.4 формулируется теорема 5, в которой для каждого г £ (Ц приводится оценка минимальной размерности п, обладающей свойством /г(п) > п + 1. Иными словами, выписываются размерности пространств, в которых есть контрпримеры к гипотезе Борсука, лежащие на сферах заданного радиуса.

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

В параграфе 2.1 доказывается теорема 1. Строится дистанционный граф с хроматическим числом 7 в размерности 4.

В параграфе 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 строится раскраска плоскости в 6 цветов, которые в некотором смысле "почти" избегают расстояния 1 между одноцветными точками. Наконец, в пункте 2.4.3 вводится новое понятие многоугольного хроматического чиыа разреженности. Это минимальное число цветов, в которые можно так покрасить все пространство, чтобы цвета представляли собой не более чем счетные объединения многогранников с точностью до их границ, причем диаметр каждого многогранника был бы не больше 1, а расстояния между разными многогранниками одного цвета не меньше d. В теоремах 6 и 7 из пункта 2.4.3 даются, соответственно, верхние оценки нового числа для случаев плоскости и трехмерного пространства. Эти оценки доказываются общим методом решетчатых разбиений Вороного.

В главе 3 доказывается теорема 5 о контрпримерах к гипотезе Борсука на сферах малого радиуса и малой размерности. Доказательство, целиком содержащееся в параграфе 3.1, разбито на пять пунктов. В доказательстве разрабатывается аккуратная модификация линейно-алгебраического метода в комбинаторике, позволяющая понижать размерности контрпримеров даже при очень небольших радиусах сфер, на которых они расположены. Одним из существенных ингредиентов метода является, в частности, следующая лемма 5 из пункта 3.1.4.

Лемма 5. Пусть величины п — 4k, к € N, и а связаны соотношением п = —a (mod р), где р — нечетное простое или степень нечетного простого числа. Тогда мощность подмножества Q множества

£ = {х = (хь..., хп) : Xi& {-1,1}, х\ ■... • хп = 1},

в котором для любых х, у выполнено условие (х, у) ф —а, —а + 4 (mod р), может быть оценена следующим образом:

р-2

|П|<ХХ

i=о

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

Соискатель считает своим приятным долгом поблагодарить д.ф.-м.н.

A.B. Арутюнова и д.ф.-м.н. A.M. Райгородского за постоянный интерес и внимание к его работе.

Работы автора по теме диссертации

1. Л.Л. Иванов, Оценка хроматического числа пространства R4, Успехи Математических Наук, т. 61 (2006), выи. 5 (371), стр. 181-182.

2. Л.Л. Иванов, О хроматических числах I2 и К3 с интервалами запрещенных расстояний, Вестник РУДН. Серия Математика. Информатика. Физика., № 1 (2011), стр. 14-29.

3. Л.Л. Иванов, О размерностях контрпримеров к гипотезе Борсука на сферах малого радиуса, Вестник РУДН. Серия Математика. Информатика. Физика., № 2 (2011), стр. 51-58.

4. L.L. Ivanov, An Estimate on the Chromatic Number of the space, Abstracts of the Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague

2006, p. 63.

5. L.L. Ivanov, On the Chromatic Numbers of R2 and K3 with Intervals of Forbidden Distances, Abstracts of EuroComb 07, Seville, September

2007, pp. 141-144.

6. Л.Л. Иванов, Хроматические числа пространств R2 u i3 с интервалами запрещенных расстояний, Материалы IX Международного семинара "Дискретная математика и ее приложения", Москва 2007, стр. 382-384.

п

Иванов Леонид Львович (Россия) Исследование оптимальных конфигураций в задачах

о хроматическом числе пространства и проблеме Борсука

Работа посвящена классическим задачам комбинаторной геометрии -задаче о хроматическом числе пространства и проблеме Борсука.

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

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

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

Ivanov Leonid Lvovich (Russia) Research of the optimal configurations in the problems of chromatic number of a space and the Borsuk problem

The paper is devoted to classical problems of combinatorial geometry -the chromatic number of space and the Borsuk problem.

In the space of dimension 4 one construction has been found which gives a lower bound of the classical chromatic number, that is much simpler than proofs existing before.

There is one of generalizations of the classical chromatic number of a plane or a space defined the chromatic number with an interval of forbidden distances. Upper bounds for this value with different intervals were obtained, and the method for obtaining such results is described.

There are counterexamples to Borsuk's conjecture constructed, which are sets laying on spheres of small radii. The work shows how the dimension of a counterexample depends on the radius of its sphere.

Подписано в печать: 05.04.2011

Заказ № 5272 Тираж -100 экз. Печать трафаретная. Типография «11-й ФОРМАТ» ИНН 7726330900 115230, Москва, Варшавское ш., 36 (499) 788-78-56 www. autoreferat. ru

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

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

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

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

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

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

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

2.2 Доказательство теоремы 2.24 '

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

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

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

2.3.3 Доказательство теоремы 3.30 /

2.3.4 Доказательство теоремы 4.

2.4 Комментарии.

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

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

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

3 Доказательства результатов в проблеме Борсука

3.1 Доказательство теоремы 5.

3.1.1 Общий план доказательства.

3.1.2 Конструкция множества Е

3.1.3 Отображение х х*.

3.1.4 Лемма о мощности подмножества с запретами

3.1.5 Завершение доказательства теоремы.

3.2 Дополнительные замечания.

Актуальность темы диссертации

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

Прежде всего речь идет о хроматических числах х(Мп; Л) евклидовых пространств М.п с множествами запрещенных расстояний Л. Здесь А) — минимальное число цветов, в которые можно так покрасить все точки пространства Мп, чтобы между одноцветными точками не было расстояния, принадлежащего множеству Л.

Впервые задача о хроматическом числе была поставлена на рубеже 40ых и 50ых годов XX века Э. Нелсоном и Г. Хадвигером (см. [1, 2]). На тот момент эта задача воспринималась исключительно как вопрос геометрической комбинаторики. Более того, в качестве множества Л запрещенных расстояний рассматривалось только множество Л = {1}, состоящее из одного элемента. Однако довольно быстро стало понятно, что, с одной стороны, задача о раскраске пространства — это очень глубокая проблема, затрагивающая самую суть дискретной геометрии, а с другой стороны, она вовсе не замкнута сравнительно узкими рамками одной лишь комбинаторно-геометрической дисциплины, но напрямую связана с различными актуальными проблемами теории графов и теории кодирования. Во многом такому развитию данной проблематики поспособствовали многочисленные работы П. Эрдеша и популяризаторская деятельность М. Гарднера (см. [3-5]).

С классической теорией графов задача о раскраске пространства связана следующим образом. Назовем граф = (V, Е) дистанционным, если множество его вершин V является набором (возможно, бесконечным) точек вК",а множество его ребер Е состоит из пар вершин, расстояние между которыми принадлежит множеству Л. Очевидно, что если взять максимальное из обычных хроматических чисел дистанционных графов, то получится ровно х(Мп; Л).

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

С теорией кодирования задача о величине соприкасается сразу в двух "точках". Во-первых, еще в 1972 году классики теории упаковок пространств Д. Ларман и К.А. Роджерс показали, что верхние оценки хроматического числа самым тесным образом связаны с вопросами построения плотнейших решетчатых упаковок шаров и наиболее в некотором смысле экономных разбиений Вороного, отвечающих решеткам (см. [6, 7]). Во-вторых, нижние оценки хроматических чисел — это, по сути, верхние оценки мощности равновесного кода с одним или многими запрещенными расстояниями Хэмминга. Задача получения подобных оценок — важнейшая в теории кодирования, и ей занимались многочисленные ведущие специалисты в области (см. [8]). Более того, здесь есть выход и на теорию однородных гиперграфов с запрещенными пересечениями ребер, которой посвящено огромное количество работ в мире (см. [9]). Таким образом, сразу несколько важнейших проблем теоретической информатики тесно переплетаются с задачей раскраски пространства.

Если задача об одном запрещенном расстоянии появилась исторически первой, то, едва стала ясна значимость такой проблематики, как возникли и различные важные обобщения исходного хроматического числа. Среди этих обобщений наибольшую роль играют рассматриваемые нами хроматические числа с несколькими запрещенными расстояниями и изучаемые многими авторами хроматические числа метрических пространств, отличных от Шп. В случае нескольких запретов следует различать ситуации, когда этих запретов конечное число и когда их бесконечное количество. Конечные множества запретов исследовал Эрдеш с учениками (см. [10]). Сейчас наилучшие результаты в этой области принадлежат A.M. Райгородскому, В.Ю. Протасову, И.М. Мит-ричевой и Е.С. Горской (см. [11]). Задачи о бесконечных множествах запретов тесно примыкают к вопросам теории диофантовых. приближений и потому также крайне актуальны (см. [12]). Среди других метрических пространств, которыми активно занимались и продолжают заниматься крупнейшие специалисты, стоит отметить пространство М.п с произвольной нормой (см. [13]), пространство Qn с метрикой lq (см. [14]) и сферу Sрадиуса г с евклидовой метрикой (см. [15]).

Также в диссертации рассматривается еще одна классическая задача комбинаторной геометрии — проблема Борсука, состоящая в отыскании минимального числа f(n) частей меньшего диаметра, на которые разбивается произвольное множество диаметра 1 в W1. Эта задача была поставлена К. Борсуком в 1933 году (см. [16]), и к настоящему времени она, а равно разрабатываемые для ее решения методы одинаково актуальны как в исходной области, так и в топологии, и в теории графов, и в теории кодирования.

С точки зрения теории графов, важны так называемые графы диаметров G — (V, Е), у которых V С М", а Е — это множество пар вершин, отстоящих друг от друга на расстояние, равное диаметру V. Хроматические числа этих графов, по сути, и равны минимальным количествам частей меньшего диаметра, на которые разбиваются их множества вершин. Задачам о графах диаметров посвящена огромная литература (см. [17]).

На стыке топологии и теории графов находится топологический метод в комбинаторике, основанный на применении теоремы Борсука-Улама в задачах раскраски графов (см. [18]).

Наконец, для теории кодирования исключительно важны спецификации проблемы Борсука для случаев Хэмминговых пространств. Именно в этих пространствах впервые был найден контрпример к гипотезе Борсука о том, что f(n) = п + 1. Стоит отмстить, что гипотеза держалась с 1933 по 1993 год, пока ее не опровергли Дж. Кан и Г. Калаи, которые именно с помощью методов теории кодирования и теории гиперграфов показали, что f(n) ^ (1.203. + (см. [19]). Также стоит упомянуть работу Г.М. Циглера, в которой благодаря кодам наоборот доказывается гипотеза Борсука для (ОД)-многогранников в малых размерностях (см. [20]). В русле этой работы находится серия статей A.M. Райгородского, в которой даются верхние оценки хроматических чисел графов диаметров с вершинами в точках решеток (см. [21, 22]). Наконец, тесно связаны проблемы упаковок шаров в пространстве и верхние оценки величины /(п) (см. [23]).

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

Апробация результатов

Результаты диссертации докладывались на международной конференции "Шестой Чехословацкий Симпозиум по Комбинаторике, Теории Графов, Алгоритмам и Приложениям" в Праге (Чехия, 2006 г.), на международной конференции "Горизонты Комбинаторики" в Балатональмади (Венгрия, 2006 г.), на IX международном семинаре "Дискретная математика и ее приложения", посвященном 75-летию со дня рождения академика О.Б. Лупапова (Москва, 2007 г.), на международной конференции "Европейская Комбинаторика" в Севилье (Испания, 2007 г.), а также на кафедральном семинаре кафедры математической статистики и случайных процессов механико-математического факультета МГУ им. М.В. Ломоносова, на семинаре проф. C.B. Конягина в МГУ им. М.В. Ломоносова, на семинаре проф. Н.Г. Мощевитина и проф. Н.П. Долбилина в МГУ им. М.В. Ломоносова, на семинаре проф. A.M. Райгородского в МГУ им. М.В. Ломоносова и др.

Опубликованность результатов

Результаты диссертации опубликованы в работах [68-73] списка литературы. Всего по теме диссертации опубликовано 6 работ.

Структура и объем диссертации

Диссертация состоит из введения, трех глав, списка литературы. Полный объем диссертации 62 страницы, из них 6 страниц занимает список литературы (73 наименования).

1. Н. Hadwiger, Ein Überdeckungssatz für den Euklidischen Raum, Portugaliae Math., 4 (1944), 140 - 144.

2. H. Hadwiger, Ungelöste Probleme N 40, Elemente der Math., 16 (1961), 103 104.

3. P. Erdos, Some unsolved problems, MTA MKI Kozl., 6 (1961), 221 254.

4. P. Erdos, On some problems of elementary and combinatorial geometry, Ann. Math. Pure Appl., (4) 103 (1975), 99 108.

5. M. Gardner, A new collection of brain teasers, Scientific American, 206 (Oct. 1960), 172 180.

6. D.G. Larman, C.A. Rogers, The realization of distances within sets in Euclidean space, Mathematika, 19 (1972), 1 24.

7. Дж. Конвей и H. Слоэн, Упаковки шаров, решетки и группы, "Мир", Москва, 1990.

8. Ф.Дж. Мак-Вильямс и Н.Дж.А. Слоэн, Теория кодов, исправляющих ошибки, "Связь", Москва, 1979.

9. A.M. Райгородский, Линейно-алгебраический метод в комбинаторике, МЦНМО, Москва, 2007.

10. L.A. Szekely, Erdos on unit distances and the Szemeredi -Trotter theorems, Paul Erdos and his Mathematics, Bolyai Series Budapest, J. Bolyai Math. Soc., Springer, 11 (2002), 649 666.

11. Е.С. Горская, И.М. Митричева, В.Ю. Протасов, A.M. Рай-городский, Оценки хроматических чисел евклидовых пространств методами выпуклой минимизации, Мат. сборник, 200 (2009), N6, 3-22.

12. Y. Katznelson, Chromatic numbers of Cayley graphs on Z and recurrence, Combinatorica, 21 (2001), 211 219.

13. A.B. Kupavskii, On the chromatic number of Mn with an arbitrary norm, Discrete Math., 311 (2011), 437 440.

14. A.M. Райгородский, О хроматическом числе пространства с метрикой lq, УМН, 59 (2004), N5, 161 162.

15. A.M. Райгородский, Контрпримеры к гипотезе Борсука на сферах малого радиуса, Доклады РАН, 434 (2010), N2, 161 -163.

16. К. Borsuk, Drei Sätze über die n-dimensionale euklidische Sphäre, Fundamenta Math., 20 (1933), 177 190.

17. P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, Springer, 2005.

18. J. Matousek, Using the Borsuk-Ulam theorem, Universitext, Springer, 2003.

19. J. Kahn, G. Kalai, A counterexample to Borsuk's conjecture, Bulletin (new series) of the AMS, 29 (1993), N1, 60 62.

20. G.M. Ziegler, Coloring Hamming graphs, optimal binary codes, and the 0/1-Borsuk problem in low dimensions, Lect. Notes Comput. Sei., 2122 (2001), 159 171.

21. A.M. Райгородский, Проблема Борсука для (0,1)-миогогранников и кросс-политопов, Доклады РАН, 384 (2002), 593 597.

22. A.M. Райгородский, Проблема Борсука для целочисленных многогранников, Мат. сборник, 193 (2002), N10, 139 160.

23. J. Bourgain, J. Lindenstranss, On covering a set in Rd by balls of the same diameter, Geometric Aspects of Functional Analysis (J. Lindenstrauss and V. Milman, eds.), Lecture Notes in Math., 1469, Springer, 1991, 138 144.

24. A. Soifer, Chromatic number of the plane: a historical essay, Geombinatorics (1991), 13 15.

25. А. Сойфер, Хроматическое число плоскости: его прошлое, настоящее и будущее, Мат. просвещение, N8, 2004.

26. A.M. Райгородский, Проблема Борсука и хроматические числа некоторых метрических пространств, УМН, 56 (2001), N1, 107- 146.

27. О. Nechushtan, Note on the space chromatic number, Discrete Math., 256 (2002), 499 507.

28. D. Coulson, A 15-coloring of 3-space omitting distance one, Discrete Math., 256 (2002), 83 90.

29. R. Radoicic, G. Toth, Note on the chromatic number of the space, Discrete and Computational Geometry: The Goodman -Pollack Festschrift, 695 698. (Algorithms and Combinatorics, 25), Springer, 2003.

30. K. Cantwell, Finite Euclidean Ramsey theory, J. Combin. Theory A, 73 (1996), N2, 273- 285.

31. J. Cibulka, On the chromatic number of real and rational spaces, Geombinatorics, 18 (2008), N2, 53 66.

32. А.Б. Купавский, A.M. Райгородский, О хроматическом числе R9, Фундамент, и прикл. матем., 14 (2008), N5, 139 154.

33. А.Б. Купавский, О поднятии оценки хроматического числа Rn в большую размерность, Доклады РАН, 429 (2009), N3, 305 308.

34. А.Б. Купавский, О раскраске сфер, вложенных в Мп, Мат. сборник, 2011.

35. A.M. Райгородский, О хроматическом числе пространства, УМН, 55 (2000), N2, 147 148.

36. Ф. Харари, Теория графов, "Мир", Москва, 1973.

37. N.G. de Bruijn, P. Erdos, A colour problem for infinite graphs and a problem in the theory of relations, Proc. Koninkl. Nederl. Acad. Wet., Ser. A, 54 (1951), N5, 371 373.

38. P. Erdos, Unsolved Problems, Congress Numerantium XV — Proceedings of the 5th British Comb. Conf. 1975, (1976), 681.

39. P. O'Donnell, Arbitrary girth, Achromatic unit distnace graphs in the plane. Graph descriptionGeombinatorics, 9 (2000), 145 152.

40. P. O'Donnell, Arbitrary girth, 4~chromatic unit distance graphs in the plane. Graph embedding., Geombinatorics, 9 (2000), 180 -193.

41. K.J. Falconer, The realization of distances in measurable subsets covering R", J. Combin. Theory A, 31 (1981), 187- 189.

42. L.A. Szekely, N.C. Wormald, Bounds on the measurable chromatic number ofW1, Discrete Math., 75 (1989), 343 372.

43. F.M. de Oliveira Filho, F. Vallentin, Fourier analysis, linear programming, and densities of distance avoiding sets ml", J. Eur. Math. Soc., 12 (2010), 1417- 1428.

44. D.R. Woodall, Distances realized by sets covering the plane, J. Combin. Theory A, 14 (1973), 187 200.

45. P. Frankl, R. Wilson, Intersection theorems with geometric consequences , Combinatorica, 1 (1981), 357 368.

46. M. Benda, M. Perles, Colorings of metric spaces, Geombinatorics, 9 (2000), 113 126.

47. P.D. Johnson, Coloring abelian groups, Discrete Math., 40 (1982), 219 223.

48. K.B. Chilakamarri, The unit-distance graph problem: A brief survey and some new results, Bull. Inst. Comb. Appl., 8 (1993), 39 60.

49. J.-H. Kang, Z. Füredi, Distance graphs on Zn with li-norm, Theoretical Comp. Sei. 319 (2004), N1 3, 357 - 366.

50. A.M. Райгородский, И.М. Шитова, О хроматических числах вещественных и рациональных пространств с вещественными или рациональными запрещенными расстояниями,, Мат. сборник, 199 (2008), N4, 107 142.

51. A.M. Райгородский, М.И. Абсалямова, Нижняя оценка хроматического числа пространства Мп с к запрещенными расстояниями и метрикой ¿i, Чебышевский сборник, 7 (2006), N4 (20), 105 113.

52. D. Coulson, On 18-colouring of 3-space omitting distance one, Discrete Math., 170 (1997), 241 247.

53. A. Hinrichs, C. Richter, New sets with large Borsuk numbers, Discrete Math., 270 (2003), 136 14б'.

54. P. Erdos, On sets of distances ofn points, Amer. Math. Monthly, 53 (1946), 248 250.

55. H.G. Eggleston, Covering a three-dimensional set with sets of smaller diameter, J. London Math. Soc., 30 (1955), 11 24.

56. A. Heppes, P. Revesz, Zum Borsukschen Zerteilungsproblem, Acta Math. Acad. Sei. Hung., 7 (1956), 159 162.

57. M. Lassak, An estimate concerning Borsuk's partition problem, Bull. Acad. Polon. Sei. Ser. Math., 30 (1982), 449 451.

58. H. Hadwiger, Uberdeckung einer Menge durch Mengen kleineren Durchmessers, Comm. Math. Helv., 18 (1945/46), 73 75; Mitteilung betreffend meine Note: Uberdeckung einer Menge durch Mengen kleineren Durchmessers, Comm. Math. Iielv., 19 (1946/47), 72 - 73.

59. R. Knast, An approximative theorem for Borsuk's conjecture, Proc. Cambridge Phil. Soc. (1974), N1, 75 76.

60. C.A. Rogers, Symmetrical sets of constant width and their partitions, Mathematika, 18 (1971), 105 111.

61. O. Schramm, Illuminating sets of constant width, Mathematika, 35 (1988), 180 189.

62. A.M. Райгородский, Об одной оценке в проблеме Борсука, УМН, 54 (1999), N2, 185 186.

63. JI. Данцер, Б. Грюнбаум, В. Кли, Теорема Хелли, "Мир", Москва, 1968.

64. P.M. Gruber and C.G. Lekkerkerker, Geometry of numbers, North-Holland, Amsterdam, 1987.

65. Дж. Касселс, Введение в геометрию чисел, "Мир", Москва, 1965.

66. Г. Ф. Вороной, Собрание сочинений в Зх томах, АН УССР, Киев, 1952-53.

67. A.M. Райгородский, О размерности в проблеме Борсука, УМН, 52 (1997), N6, 181 182.

68. JI.JI. Иванов, Оценка хроматического числа пространства R4, УМН, 61 (2006), N5, 181 182.

69. JI.JI. Иванов, О хроматических числах R2 и R3 с интервалами запрещенных расстояний, Вестник РУДН, Серия Математика. Физика. Информатика, N1, 2011, 14 29.

70. JI.JI. Иванов, О размерностях контрпимеров к гипотезе Борсука на сферах малого радиуса, Вестник РУДН, Серия Математика. Физика. Информатика, N2, 2011, 51 58.

71. L.L. Ivanov, An Estimate on the Chromatic Number of the 4-space, Abstracts of the Sixth Czech-Slovak International Symposium on Combinatorics, Graph Theory, Algorithms and Applications, Prague, 2006, p. 63.

72. L.L. Ivanov, On the Chromatic Numbers of K2 and R3 with Intervals of Forbidden Distances, Abstracts of EuroComb 07, Seville, September 2007, 141 144.

73. Jl.JI. Иванов, Хроматические числа пространств М2 и М3 с интервалами запрещенных расстояний, Материалы IX Международного семинара "Дискретная математика и ее приложения", Москва, 2007, 382 384.