Экстремальные свойства дистанционных графов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

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

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

Экстремальные свойства дистанционных

графов

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

31 ИЮП 2014

Москва - 2014

005551622

005551622

Работа выполнена на кафедре общих проблем управления механико-математического факультета Московского государственного университета им. М.В. Ломоносова.

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

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

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

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

математики Дальневосточного отделения РАН.

Защита диссертации состоится 10 октября 2014 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, Москва, ГСП-1, Ленинские горы, 2-й учебный корпус, факультет ВМК, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за два дня по тел. 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М. В. Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http://cs.msu.ru/.

Автореферат разослан « ''» ///<?/^ 2014 г. Учёный секретарь

диссертационного совета Д 501.001.44

профессор Московского государственного технического университета им. Н.Э. Баумана Мантуров Василий Олегович;

кандидат физико-математических наук, доцент Нижегородского государственного университета им. Н.И. Лобачевского Малышев Дмитрий Сергеевич.

к.т.н., в.н.с.

Костенко В.А.

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

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

В работе получены результаты, связанные с классической проблемой Нельсона-Эрдёша-Хадвигера о хроматическом числе пространства. Эта проблема впервые была сформулирована Э. Нельсоном1 в 1950 году, а П. Эр-дёш2 и Г. Хадвигер3 сыграли важную роль в популяризации этой проблемы. Проблема заключается в нахождении минимального количества цветов, такого, что существует покраска всех точек пространства R" в это количество цветов, при которой точки, находящиеся на единичном расстоянии друг от друга, покрашены в разные цвета. Для пространств с размерностями не менее двух проблема остаётся открытой, и до сих пор она очень популярна4'5'6. Для плоскости известно, что хроматическое число лежит между четырьмя и семью. Минимальный пример графа расстояний (или, что то же самое, дистанционного графа) с хроматическим числом четыре на плоскости получен

братьями JI. и В. Мозерами7.

В 1976 году Эрдёш8 задал вопрос, существует ли дистанционный граф на плоскости с хроматическим числом четыре и не содержащий треугольников (поскольку все известные на тот момент примеры таких графов треуголь-

'А. Soifer, The Mathematical Coloring Book, Springer, 2009.

2L.A. Székely, ErdSs on wit distances and the Szemerédi-Trotter theorems, Paul Erd6s and his Mathematics,

Bolyai Series Budapest, J. Bolyai Math. Soc., Springer, 11 (2002), 649 - 666.

3H Hadwiger, Ein Überdeckungssatz für den Euklidischen Raum, Portugaliae Math., 4 (1944), 140 - 144. «А. Сойфер, Хроматическое число плоскости: его прошлое, настоящее и будущее, Матем. просвещение, 8 (2004).

6А М. Райгородский, Хроматические числа, Москва, МЦНМО, 2003.

ePK. Agaiwal, J. Pach, Combinatorial geometry, John Wiley and Sons Inc., New York, 1995.

7L Moser, W. Moser Solution to problem 10, Canad. Math. Bull. Vol. 4 (1961), 187 - 189.

s p. ErdeS, Unsolved Problems, Congress Numerantium XV - Proceedings of the 5th British Comb. Conf.

1975,1976, 681.

С*

ники содержали). Задача была решена в 1979 году Н. Уормалдок^, а позднее примеры с меньшим количеством вершин были построены П. О'Доннеллом и Р. Хохбергом10. Также в 1999 году в своей кандидатской диссертации (а на год позже — в других своих работах11,12) П. О'Доннелл нашёл решение обобщённого варианта этой задачи, а именно, что на плоскости существуют дистанционные графы с хроматическим числом четыре и произвольным обхватом (длиной минимального цикла). В данной работе рассматривается обобщение задачи на дистанционные графы в пространствах произвольной размерности.

В растущей размерности известно, что хроматическое число ведёт себя, как экспонента13,14. Доказательства лучших нижних оценок хроматического числа используют линейно-алгебраический метод на целочисленных решётках. Этот метод также использутеся в классической задаче Борсука15 о нахождении минимального числа частей, на которое можно разбить любое неодноточечное множество в R" так, чтобы диаметр каждой части был меньше диаметра исходного множества16,17.

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

®N. Wonnald, A 4-Chromatic Graph With a Special Plane Drawing, Australian Mathematics Society (Series A), 28 (1979), 1 - 8.

10P. O'Donnel, R. Hochberg, Some 4-chromatic Unit-Distance Graphs without small cycles, Geombinatorics, 5 (1996), 137- 142.

"P. O'Donnell, Arbitrary girth, 4-chromatic unit distance graphs in the plane. I. Graph description,

Geombinatorics, 9 (2000), №3,145 - 152.

"P. O'Donnell, Arbitrary girth, 4-chromatic unit distance graphs in the plane. II. Graph embedding,

Geombinatorics, 9 (2000), »4,180 - 193.

ISA.M. Райгородский, О хроматическом числе пространства, Успехи мат. наук, 55 (2000), 147 - 148.

UD. Larman, С. Rogers The realization of distances within sets in Euclidean space, Mathematika, 19 (1972),

№1, 1 - 24.

15K. Borsuk Drei Sätze über die n-dimensionale Euklidische Sphäre, Fund. Math., 20 (1933), 177 - 190.

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

17A.M. Райгородский, Вокруг гипотезы Борсука, Геометрия и механика, СМФН, 23 (2007), 147 - 164.

новесных кодов18.

Также отметим, что есть и ряд других важных задач экстремальной

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

20

графе19. О ней имеется обширная литература .

Цель и задачи исследования

Целью диссертационной работы является решение следующих задач.

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

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

Научная новизна полученных результатов

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

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

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

18Ф.Дж. Мак-Вильямс, Н.Дж.А. Слоэн, Теория ходов, исправляющих 250

"Р ErdSs On sets of distances of n points, American Mathematical Monthly, 53 (1946) 248 - m »S З^еГв. sxemerfdi, W.T. better. Unit distances in Ле Euclidean plane, Graph theory and

combinatorics, 1984, 293 - 303.

Основные результаты, выносимые на защиту

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

(Теорема 2)

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

(Теорема 3)

3. Для произвольного натурального к > 5 существует последовательность дистанционных графов без клик размера к с экспоненциально растущими хроматическими числами (в зависимости от размерности пространства).

(Теоремы 6 и 7)

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

(Теорема 8)

Личный вклад соискателя

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

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

Результаты, полученные в диссертации, докладывались и обсуждались на 9-ом Международном научном семинаре "Дискретная математика и приложения" (Москва, 2007 г.), международной конференции "Фестиваль комбинаторики и информатики" (Венгрия, 2008 г.), на международной конференции "EuroComb 2009: Европейская конференция по комбинаторике, теории графов и приложеням" (Франция, 2009 г.), на международной конференции "8-ая Французская комбинаторная конференция" (Франция, 2010 г.), на семинаре профессора A.M. Райгородского в МГУ имени М.В. Ломоносова, на семинаре профессора C.B. Конягина в МГУ имени М.В. Ломоносова, а также на научном семинаре "Дискретная математика и математическая кибернетика" кафедры математической кибернетики факультета вычислительной математики и кибернетики МГУ имени М.В. Ломоносова.

Публикации по теме диссертации

Результаты диссертации опубликованы в работах [1]-[5] списка литературы. Всего по теме диссертации опубликовано 5 работ. Из них 4 работы входят в список научных журналов, рекомендованный ВАК Минобрнауки РФ.

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

В диссертации имеется введение, три главы, список литературы. Полный объем 68 страниц, из них 4 страницы занимает список литературы (36 наименований).

Краткое содержание диссертации

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

Определение. Хроматическим числом метрического пространства М называется минимальное такое число к, что множество М можно разбить на к непересекающихся подмножеств М = М\ и Мг и ... и Мь так, что любые два элемента этого пространства, находящиеся па единичном расстоянии, находятся в разных подмножествах. Иными словами, если |а1аг| = 1 и а\ € М,-, то а2 £ М{. Обозначается хроматическое число Х(М).

Определение. Хроматическим числом графа в = (V, Е) называется минимальное такое число к, что множество вершин V можно разбить на к непересекающихся подмножеств V = VI и ^ и... и 14 так, что любые две вершины графа, соединённые ребром, находятся в разных подмножествах. Иными словами, если {г^х,^} £ Е и £ Ц, то г>2 & Ц. Обозначается хроматическое число графа

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

Определение. Графом единичных расстояний называется такой геометрический граф (7 = (V, Е), что если две его вершины Уг,Ь2 Е V соединены ребром {иь^г} 6 Е, то расстояние между этими вершинами равно единице (\У\ — =

Определение. Графом с т запрещёнными расстояниями называется

геометрический граф С? = (V, Е), для которого существует такое множе-

6

', мини-

ство ЛсК+ изт элементов, что если {vi,u2} 6 Е, то |i>i - v2\ G Л. Определение. Хроматическим числом евклидова пространства с множеством запретов Л (обозначается x(R", Л)) называется малъное такое число к, что множество точек R" можно представить в виде объединения к непересекающихся подмножеств R" = Vi U V2 U ... U Vk так, что любые две точки, расположенные на расстоянии d е А друг от друга, не лежат в одном и том же множестве Vi. Максимальное из таких хроматических чисел для данного количества запретов т обозначается

x(R";m)= max А,\А\=т

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

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

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

Для удобства записи в этой главе напоминается определение кликового

числа.

Определение. Кликовым числом графа G = (V, Е) называется размер максимальной клики в этом графе, то есть максимальная мощность подмножества V, каждые две вершины которого соединены друг с другом ребром. Обозначается кликовое число w(G).

В этих обозначениях обобщение задачи П. Эрдёша переформулирует-

7

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

Сформулированы две теоремы для трёхмерных графов единичных расстояний (здесь и далее сохранена нумерация теорем из диссертации).

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

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

Теорема 2 вытекает, конечно, из теоремы 3. Ее самостоятельное значение состоит в том, что граф, построенный в ней, имеет всего 19 вершин, тогда как граф, доказывающий теорему 3, на порядки больше.

Поскольку известно, что хроматическое число пространства R" при росте п растёт экспоненциально ((1.239 + о(1))" < х(Кп) < (3 + о(1))"), то можно ожидать (как максимум) экспоненциального роста хроматических чисел дистанционных графов с дополнительными ограничениями на размеры максимальных клик.

В связи в этим вводятся величины

Cciique(fc) = sup {С : 3 функция S = 5(п), такая, что ^lim 6(п) = О

и Vn 3 GbR", у которого w(G) < k, x(G) > (С + $(п))п}.

и

Cclique(fc,ro) = sup{C : 3 функция 5 = 5(п), такая, что ^lirn ё(п) = О и Vn ЗА мощности m и 3G в R" с множеством запретов Л,

у которого w(G) < к, x(G) > (С + ¿(п))"}.

С помощью этих величин сформулированы основные теоремы, показывающие, что существуют последовательности графов единичных расстояний без больших клик и с экспоненциально растущими хроматическими числами (при размере клики не больше пяти, то есть Cciique(^) > 1 при к > 5). В

частности, сформулированы следующие результаты.

8

Теорема 6. Пусть к > 5 — произвольное натуральное число, а 60 £ (0, — произвольное вещественное число. Положим

(!)-*(.-I)4"".

Г! = п(Ьо) = - Ьо)Ч1"ад.

Положим с = с(Ь0,к) = т£С, если С ф 0, и с = Т\ иначе. Тогда СсИЧие(*0 > Теорема 7. Пусть к > 5 — произвольное натуральное число, а 6-1,61 — произвольные вещественные числа, удовлетворяющие ограничениям

Рассмотрим

6_ь Ьх е (0,1), 6_1 + 6-1 < &!•

Положим

А =

2 + 9Ь_1 + ЗЬг - у/(2 + 96-, + 36^ - 12(36-! + б])2

12

В = 3±1±Ь-2А, С = 1 +

Пусть, далее,

ро - = А АВ ВС с,

/31 = р! (6-1, бх) - ы^а - Ь-1 - бо-^-6-1-60-

Рассмотрим

( Г 21п Р1

С = С(Ь-иЬ1,к)=![с'е[Ро,р1]:к> 1пс,_1про

Положим с = с(6_1,&1,/с) = ШС, если С ф 0, и с = рг иначе. Тогда СсНяие(^) ^ ^Г-

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

Теорема 8. Пусть даны числа кит. Пусть также г > 1 — произвольное натуральное число. Рассмотрим симплекс

Д = {у = (ио,и1,...,иг): г>»е[0,1], + ^ + ... + ьг = 1}.

9

Для каждого V е Д положим

№ = V) = ¿1{<>ц.=0^.} Ю, * = ад = ¿=0

¿ = э>(у)= /%(%(1 -

ио

Ь = (0,1,... , г), е = (1,..., 1),

Г — э' \

Н' = Н'(\) = | Т7 = {г)о,..., »7г) : т*б[0,1], (»7,е) = 1, (»?. Ь) < ,

Г

/(а) = ^аДпа^ а = (ао, аь ..., аг),

¡=о

Тогда

Сс1щие(£,т) > е"(у).

История задачи и основные определения содержатся в параграфе 1.1. В параграфе 1.2 сформулированы результаты диссертации для трёхмерных графов расстояний. В параграфе 1.3 сформулированы результаты диссертации в растущей размерности. В пункте 1.3.2 сравниваются результаты расчётов в теоремах б и 7. Пункт 1.3.4 содержит численные следствия из теоремы 8 для разных количеств запрещённых расстояний и кликовых чисел. Для получения этих результатов используется нетривиальная оптимизационная техника.

Вторая глава посвящена доказательству теорем о дистанционных графах в трёхмерном пространстве. В параграфе 2.1 приведён пример дистанционного графа в трёхмерном пространстве без тетраэдров и с хроматическим числом 5. Полученный граф состоит из 19 вершин и 44 рёбер.

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

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

Формальное доказательство того, что можно расположить несколько дистанционных графов на сфере, приведено в пункте 2.2.2. Пункт 2.2.3 содержит некоторые вспомогательные леммы, необходимые для описания процедуры "шевеления", которая проводится в пункте 2.2.4.

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

В параграфе 3.1 содержится доказательство теоремы 6, параграф 3.2 посвящён доказательству теоремы 7, а параграф 3.3 — доказательству теоремы 8. В параграфе 3-4 обсуждается связь между теоремами о графах с одним и несколькими запрещёнными расстояниями. В параграфе 3.5 представлен способ решения экстремальной задачи, возникающей в теореме 8.

Благодарности

Автор выражает искреннюю благодарность и признательность своему научному руководителю A.M. Райгородскому за всестороннюю помощь при написании настоящей работы. Автор также сердечно благодарит своих родителей за их терпение и поддержку.

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

[1] Рубанов О.И. Хроматические числа трехмерных графов расстояний, не содержащих тетраэдров // Математические заметки. 2007. Т. 82, № 5. С. 797 - 800. (Журнал входит в список, рекомендованный ВАК Минобр-науки РФ.)

[2] Демёхин Е.Е., Райгородский A.M., Рубанов О.И. Дистанционные графы, имеющие большое хроматическое число и не содержащие клик или циклов заданного размера // Математический сборник. 2013. Т. 204, № 4. С. 49 - 78. (Журнал входит в список, рекомендованный ВАК Ми-нобрнауки РФ. A.M. Райгородский — постановка задачи и параграф 1, Е.Е. Демёхин - параграфы 2 и 3, О.И. Рубанов - параграфы 4, 5 и 6.)

[3] Raigorodskii A., Rubanov О. 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. {A.M. Райгородский поставил задачу и редактировал введение. Доказательство всех основных результатов принадлежит О.И. Рубанову.)

[4] Райгородский A.M., Рубанов О.И. О графах расстояний с большим хроматическим числом и без больших клик // Математические заметки. 2010. Т. 87, № 3. С. 417 - 428. (Журнал входит в список, рекомендованный ВАК Минобрнауки РФ. A.M. Райгородский поставил задачу и редактировал введение. Доказательство всех основных результатов принадлежит О.И. Рубанову.)

[5] Raigorodskii A., Rubanov 0. Small clique and large chromatic number // Electronic Notes in Discrete Mathematics. Elsevier BV, 2009. Vol. 34. P. 441 - 445. (Журнал входит в список, рекомендованный ВАК Минобрнауки РФ. A.M. Райгородский поставил задачу и редактировал введение. Доказательство всех основных результатов принадлежит О. И. Рубанову.)

Напечатано с готового оригинал-макета

Подписано в печать 07.07.2014 г. Формат 60x90 1/16. Усл.печ.л. 1,0. Тираж 100 экз. Заказ 158.

Издательство ООО "МАКС Пресс" Лицензия ИД N 00510 от 01.12.99 г. 119992, ГСП-2, Москва, Ленинские горы, МГУ им. М.В. Ломоносова, 2-й учебный корпус, 527 к. Тел. 8(495)939-3890/91. ТелУФакс 8(495)939-3891.