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

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

диссертации.

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

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

Впервые задача о хроматическом числе была поставлена на рубеже 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 Uberdeckungssatz fur den Euklidischen Raum, Portugaliae Math., 4 (1944), 140 — 144.

2. H. Hadwiger, Ungeloste 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 SzemerediTrotter 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 Satze uber die n-dimensionale euklidische Sphare, 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 GoodmanPollack 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. Furedi, 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.