Упаковки и раскраски сфер в многомерных пространствах тема диссертации и автореферата по ВАК РФ 01.01.06, кандидат физико-математических наук Купавский, Андрей Борисович

• Купавский, Андрей Борисович
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Купавский, Андрей Борисович

Оглавление

Введение

1 Раскраски сфер и хроматические числа пространств малой

размерности

1.1 Хроматическое число

1.2 Оценка величины х(к9)

1.2.1 Вывод теоремы 1 из теоремы 2 и новая оценка х(М10)

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

Оценка а(С) >12

Оценка а(С) < 12: вспомогательная лемма

Доказательство оценки а (С) <12

1.2.3 О верхней оценке хроматического числа графа С

1.3 Поднятие оценок в большую размерность

1.3.1 Доказательство теоремы 5: вспомогательные леммы

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

1.4 Пестрота сфер

1.4.1 Одномерный случай

Вводное замечание и вспомогательные утверждения

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

1.4.2 Двумерный случай

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

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

1.4.3 Многомерный случай

Основная конструкция

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

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

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

Возможные дальнейшие результаты

2 Разбиения трехмерных множеств на части меньшего диаметра

2.1 Универсальные покрывающие системы

2.2 Построение УПС

2.3 Построение разбиения

2.4 Отыскание диаметров частей при с! > 0.592

2.4.1 Простейшие наблюдения

2.4.2 Редукция к одномерным составляющим границ

2.4.3 Редукция к нульмерным составляющим границ

2.4.4 Окончательная локализация диаметров

2.4.5 Сводка вычислений

2.4.6 Выбор параметров и завершение вычислений

2.5 Отыскание диаметров частей при с1<0.592

3 Асимптотические оценки хроматического числа пространства

и упаковки выпуклых центрально-симметричных тел

3.1 Хроматическое число

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

Список литературы

Введение диссертации (часть автореферата) на тему «Упаковки и раскраски сфер в многомерных пространствах»

Введение

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

Задача о хроматическом числе пространства — это одна из классических задач комбинаторной геометрии (см. [18], [34]). В 1950 году Нелсон поставил следующий вопрос: Какое минимальное число цветов требуется для покраски точек плоскости, чтобы не было пары одноцветных точек на единичном расстоянии? Величина х(^2) называется хроматическим числом плоскости. Аналогичный вопрос можно задать и в больших размерностях. Формально говоря, хроматическое число пространства — это величина

За прошедшие 60 лет было получено множество результатов касательно хроматического числа пространства. Франклом и Уилсоном [40] и Ларманом и Роджерсом [50] было доказано, что хроматическое число пространства растет экспоненциально с ростом размерности. Были найдены многочисленные оценки хроматического числа в малых размерностях (см. работы [16], [35], [50], [56] и др.). Кроме того, изучались различные обобщения задачи об отыскании хроматического числа пространства (см. [16], [26], [31], [62]). Например, в работе [31] была в общем виде сформулирована задача о нахождении хроматического числа произвольного метрического пространства. Также изучалось измеримое хроматическое число, которое определяется аналогично обычному хроматическому числу, но при этом требуется, чтобы множества точек одного цвета были измеримыми (см. [30], [39]). Наконец, изучались хроматические числа пространств с множествами запрещенных расстояний (см. [2]. [19], [26]). Однако, до сих пор непонятно, чему равняется хроматическое число плоскости: известны лишь оценки 4 < х(К2) < 7.

Х(ШП) = пип < 7п : М" = У К- Уг = 1,..., 77г\/х.у еЦ \х - у\ ф 1

т

В первой главе (см. также [65], [66], [70]) установлен ряд результатов о хроматическом числе. А именно, введено новое понятие пестроты сфер, и за счет этого уточнены оценки хроматического числа пространства во многих размерностях. В частности, доказано, что х(М9) > 21, х(^10) > 23, х(^И) > 25, х(К12) > 27, передоказана оценка > Предложен общий метод

поднятия оценок хроматического числа в большие размерности.

В 1933 году Борсук [33] поставил следующий вопрос: Верно ли, что любое множество диаметра один в п-мерном Евклидовом пространстве можно разбить на п + 1 часть строго меньшего диаметра? Положительный ответ на этот вопрос стал известен как гипотеза Борсука, а сама задача стала одной из основополагающих в комбинаторной геометрии (см. [1], [17], [22], [32]). Сам Борсук доказал гипотезу для п = 2. Более того, он показал, что любое тело единичного диаметра можно разбить на три части, диаметр каждой из которых не превосходит \/3/2 = 0.8660 .... Следуя статье Борсука, мы определим следующие величины:

/(п) = тт|ш : УФ С Мп, сНатФ = 1,

ЗФ1;...,Фт : Ф

т

^ Фг, сНат Фг <11,

г=1 ^

б^ = вир т£ < х : ЗФ1;..., Фт : Ф = М Фг, Уг сНат Фг < х > .

Фскп,а;ашФ=1 I ' I

Таким образом, вопрос Борсука звучит так: верно ли, что /(п) = п + 1? Борсук же доказал, что /(2) = 3, и, более того, с/§ < л/З/2.

Гипотеза Борсука для п = 3 была доказана Перкалом и Эгглстоном (см. [16]) с помощью неэлементарных средств. Позднее Хеппеш и Грюнбаум независимо друг от друга получили элементарное решение проблемы, при этом установив нетривиальную оценку величины

Было получено множество результатов, говорящих в пользу гипотезы Борсука. В 1946 году Хадвигер доказал, что всякое ¿-мерное тело с гладкой границей можно разбить на с1 + 1 часть меньшего диаметра (см. [1]). В 1971 году Роджерс [58] доказал, что всякое тело в М^, инвариантное относительно действия группы конгруэнций, оставляющих на месте правильный симплекс, можно разбить на с1 + 1 часть меньшего диаметра.

Однако, в 1993 году Кан и Калаи [49] опровергли гипотезу в достаточно большой размерности, в качестве контрпримера используя конечное множество точек. После этого минимальная размерность контрпримера неоднократно уменьшалась, и сейчас лучший результат принадлежит Хинрихсу и Рихтеру [47], которые построили контрпример в размерности 298.

Величины с^ интенсивно изучались Лассаком [51], Макеевым ([12], [13]) Филимоновым [28], Хеппешем [45] и другими.

Во второй главе (см. также [69]) мы уточняем верхнюю оценку величины

полученную в работе [51].

Задача о плотных упаковках шаров в пространстве — это центральная задача дискретной геометрии и геометрии чисел (см. [3], [8], [9]). Гильберт [46] в 1900 году на международном математическом конгрессе отметил ее как одну из открытых проблем (нерешенная часть проблемы 18). Дадим формальную постановку задачи. Под Уо1(Х) будем понимать объем множества X, за В"(0) обозначим п-мерный шар радиуса г с центром в начале координат. Сначала определим верхнюю плотность множества X С М" :

Уо1{Х пвт;(о)) Уо1{В?{ 0)) '

6{Х) = Ит

г ->оо

Пусть множество X С Кп — это объединение непересекающихся открытых п-мерных шаров единичного радиуса. В этом случае X называется упаковкой шаров. Гильберт интересовался, насколько большим может быть Обо-

значим максимум верхней плотности множеств X описанного вида за Л(п). Вокруг задачи о плотных упаковках шаров написано множество книг и обзоров (см., например, [9]). Однако, на поставленный вопрос дан ответ только при п < 3. Известно, что асимптотически

-(1 + о(1 ))п < 1с^2 Д(п) < -(0.599 + о(1))п,

где оценка сверху — это известная граница Кабатянского-Левенштейна [7], а оценка снизу следует, например, из теоремы Минковского-Главки или из ее уточнения Шмидтом [59].

Огромный интерес представляет изучение решетчатых упаковок, то есть таких упаковок X С Мп, что центры шаров из X образуют решетку в Мп. Для решетчатых упаковок известно больше. Например, известны плотнейшие решетчатые упаковки в 1™, п < 8 (см. [9]).

Задача о нахождении плотных упаковок представляет не только самостоятельный интерес. Она также имеет приложения к решению диофантовых

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

В третьей главе (см. также [67], [68]) получены новые верхние оценки хроматического числа пространства Еп с некоторой нормой, а также новые верхние и нижние оценки хроматического числа пространства с отрезком запрещенных расстояний. Основной аппарат, который используется в доказательствах, — это теория упаковок.

Благодарности. Автор признателен профессору Андрею Михайловичу Райгородскому и профессору Николаю Германовичу Мощевитину за постановку задач и неоценимую помощь в работе.

Список литературы диссертационного исследования кандидат физико-математических наук Купавский, Андрей Борисович, 2013 год

Список литературы

[1] В.Г. Болтянский, И.Ц. Гохберг, Теоремы и задачи комбинаторной геометрии, Москва, Наука, 1965.

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

[3] П.М. Грубер, К.Г. Леккеркеркер, Геометрия чисел, Москва, Наука, 2008.

[4] А.Э. Гутерман, В.К. Любимов, A.M. Райгородский, С.А. Усачев, О числах независимости графов расстояний с вершинами в { — 1,0,1}", Матем. заметки, 86 (2009), N5, 794-796.

[5] Л. Данцер, Б. Грюнбаум, В. Кли, Теорема Хелли, Москва, Мир, 1968.

[6] Л.Л. Иванов, Оценка хроматического числа пространства IR4, Успехи матем. наук, 61 (2006), N5, 371 - 372.

[7] Г.А. Кабатянский, В.И. Левенштейн, О границах для упаковок на сфере и в пространстве, Пробл. передачи информ., 14 (1978), N1,3- 25.

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

[9] Дж. Конвей, Н. Слоэн, Упаковки шаров, решетки и группы, Москва, Мир, 1990.

[10] H.H. Кузюрин, Асимптотическое исследование задачи о покрытии, Проблемы кибернетики, 1980, N37, 19 - 56.

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

[12] В.В. Макеев, Об аффинных образах ромбододекаэдра, описанных вокруг трехмерного выпуклого тела, Зап. научн. семин. ПОМИ, 246 (1997), 191 - 195.

13] В.В. Макеев, Универсальные покрышки и проекции тел постоянной ширины, Укр. геом. сборник, 32 (1989), 84 - 88.

14] С.А. Пичугов, Константа Юнга пространства Ьр, Матем. заметки, 43 (1988), N5, 604 - 614.

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

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

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

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

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

20] A.M. Райгородский, Системы общих представителей, Фунд. и прикл. матем., 5 (1999), N3, 851 - 860.

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

22] A.M. Райгородский, Проблема Борсука, Москва, МЦНМО, 2006.

23] A.M. Райгородский, Системы общих представителей в комбинаторике и их приложения в геометрии, Москва, МЦНМО, 2009.

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

25] A.M. Райгородский, Ю.А. Калнишкан, О проблеме Борсука в R3, Матем. заметки, 74 (2003), N1, 149 - 151.

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

27] В.Е. Тараканов, Комбинаторные задачи и (0,1)-матрицы, Москва, Наука, 1985.

28] В.П. Филимонов, О покрытии плоских множеств, Матем. сборник, 201 (2010), N8, 127 - 160.

29] L. Babai, P. Frankl, Linear Algebra Methods in Combinatorics, Part 1, Preliminary version 2, Chicago, Department of Computer Science, The University of Chicago, 1992.

30] C. Bachoc, G. Nebe, F.M. de Ol. Filho, F. Vallentin, Lower bounds for measurable chromatic number, Geom. Funct. Anal., 19 (2009), N3, 645 - 661.

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

32] V.G. Boltyanski, H. Martini, P.S. Soltan, Excursions into combinatorial geometry, Universitext, Springer, Berlin, 1997.

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

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

35] K. Cantwell, Finite Euclidean Ramsey theory, J. Comb. Theory, Ser. A, 73 (1996), N2, 273 - 285.

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

37] N.D. Elkies, A.M. Odlyzko, J.A. Rush, On the packing densities of superballs and other bodies, Inventiones Mathematicae, 105 (1991), N1, 613 - 639.

38] P. Erdös, C.A. Rogers, Covering space with convex bodies, Acta Arithmetica, 7 (1962), 281 - 285.

39] F.M. de Ol. Filho, F. Vallentin, Fourier analysis, linear programming, and densities of distance avoiding sets in Rn, Eur. Math. Soc., 12 (2010), 1417 -1428.

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

41] Z. Füredi, J.-H. Kang, Covering the n-space by convex bodies and its chromatic number, Discrete Math., 308 (2008), 4495 - 4500.

42] D. Gale, On inscribing n-dimensional sets in a regular n-simplex, Proc. Amer. Math. Soc., 4 (1953), 222 - 225.

43] B. Grünbaum, A simple proof of Borsuk's conjecture in three dimensions, Proc. Cambridge Philos. Soc., 53 (1957), 776 - 778.

[44] A. Heppes, Terbeh ponthalmazok felosztasa hsebb atmeröjü reszhalmazok összegere, A magyar tudomänyos akademia, 7 (1957), 413 - 416

[45] A. Heppes, Covering a planar domain with sets of small diameter, Periodica Mathematica Hungarica, 53 (2006), 157 - 168.

[46] D. Hilbert, Mathematische Probleme, Archiv. Math. Phys., 1 (1901), 44 - 63

[47] A. Hinrichs, C. Richter, New sets with large Borsuk numbers, Discrete Math., 270 (2003), 137 - 147.

[48] P.D. Johnson, Coloring abehan groups, Discrete Math., 256 (1982), 219 - 223.

[49] J. Kahn, G. Kalai, A counterexample to Borsuk''s conjecture, Bull. Amer. Math. Soc., 29 (1993), N1, 60 - 62.

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

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

[52] H. Lenz, Zerlegung ebener Bereiche in konvexe Zellen von möglichst kleinem Burchmesser, Jahresbericht d. DMV Bd., 58 (1956), 87 - 97.

[53] H. Lenz, Uber die Bedeckung ebener Punktmengen durch solche kleineren Durchmessers, Arch. Math., VII (1956), 34 - 40.

[54] L. Loväsz, Self-dual polytopes and the chromatic number of distance graphs on the sphere, Acta Sei. Math., 45 (1983), 317 - 323.

[55] L. Moser, W. Moser, Solution to problem 10, Canad. Math. Bull., 4 (1961), 187 - 189.

[56] O. Nechushtan, On the space chromatic number, Discrete Math., 256 (2002), 499 - 507.

[57] R. Radoicic, G. Töth, Note on the chromatic number of the space, B. Aronov (ed.) et al., Discrete and computational geometry, The Goodman-Pollack Festschrift, Berlin: Springer, Algorithms Comb., 25 (2003), 696 - 698.

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

[59] W.M. Schmidt, On the Mmkowski-Hlawka theorem, Illinois J. Math., 7 (1963), 18 - 23.

[60] G.J. Simmons, On a problem of Erdos consermng 3-colounng of the unit sphere, Discrete Math., 8 (1974), 81 - 84.

[61] G.J. Simmons, The chromatic number of the sphere, J. Austral. Math. Soc., Ser. A, 21 (1976), 473 - 480.

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

[63] B. Weissbach, Polyhedral covers, Coll. Math. Soc. J. Bolyai, 48 (1987), 639 -646.

[64] D.R. Woodall, Distances realized by sets covering the plane, J. Comb. Theory, Ser. A, 14 (1973), 187 - 200.

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

[66] А.Б. Купавский, О раскрасках сфер, вложенных в Rn, Матем. сборник, 202 (2011), N6, 83 - 110.

[67] A. Kupavskii, The chromatic number of the space Ш" with arbitrary norm, Discrete Math., 311 (2011), 437 - 440.

[68] А.Б. Купавский, Хроматическое число Rn с множеством запрещенных расстояний, Доклады Российской Академии Наук, 435 (2010), N6, 740 -743.

[69] А.Б. Купавский, A.M. Райгородский, О разбиении трехмерных множеств на пять частей меньшего диаметра, Матем. заметки, 87 (2010), N2, 233 - 245.

[70] А.Б. Купавский, A.M. Райгородский, О хроматическом числе 1R9, Фунд. и прикл. матем., 14 (2008), N5, 139 - 154; Journal of Mathematical Sciences, 163 (2008), N6, 720 - 731.