О покрытиях множеств в евклидовых пространствах тема диссертации и автореферата по ВАК РФ 01.01.09, кандидат физико-математических наук Филимонов, Владислав Павлович

• Филимонов, Владислав Павлович
• кандидат физико-математических наук
• 2013

Оглавление диссертации кандидат физико-математических наук Филимонов, Владислав Павлович

Оглавление

Введение

1 Оценки в М2

1.1 Формулировки результатов

1.2 Доказательства

1.3 Комментарии

1.4 Таблица результатов

2 Оценки в Мт

2.1 Оценки снизу в М3

2.1.1 Метод расслоения

2.1.2 Получение оценок

2.1.3 Таблица результатов

2.2 Оценки снизу вГ

2.2.1 Оценки Хеппеша

2.2.2 Обобщение оценок Хеппеша

2.2.3 Применение метода расслоения

2.3 Точные оценки сверху в Мт

2.3.1 Перестановочный многогранник

2.3.2 Получение оценок

2.4 Асимптотические оценки сверху в К771

2.4.1 Получение оценок

2.4.2 Асимптотика при ш —> оо

2.4.3 Гипотеза об асимптотике (I™ при 1 ^ т ^ 5

2.4.4 Связь с теорией решетчатых покрытий

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

3 Асимптотические свойства кодов деления

3.1 Теорема о площадях

3.2 Теорема о малых отклонениях

3.3 Теорема о рациональной периодичности

3.4 Теорема о вещественной периодичности

Теорема о пределе

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

Введение

Вступление

В данной работе будут изложены результаты, связанные с классической проблемой Борсука (см. [1], [2], [3], [4], [5], [6]) о разбиении множеств в Ет на части меньшего диаметра, с известной задачей Нелсона-Хадвигера (см. [2], [7], [8], [9], [10]) о хроматическом числе евклидова пространства, а также с задачей об оптимальных решётчатых покрытиях евклидовых пространств (см., например, [11] и [12]).

Проблема Борсука была сформулирована почти 80 лет назад, и в последние годы она стала одной из ключевых проблем в области комбинаторной геометрии и явилась источником возникновения множества новых идей и задач в рамках данного раздела науки. Она заключается в отыскании минимального числа частей меньшего диаметра, на которое может быть разбито произвольное ограниченное множество в пространстве. Из данной формулировки ясно, что проблема Борсука связана с известными задачами оптимальных разбиений, упаковок и покрытий множеств в различных пространствах. Данная взаимосвязь проясняется в работах таких ученых, как К.А. Рождерс (см. [13]), Р. Ранкин (см. [14]), Ж. Бургейн и Й. Линденштраусс (см. [15]) и многих других. Настоящая диссертация также посвящена исследованию задачи об оптимальных покрытиях множеств в евклидовых пространствах множествами меньшего диаметра, являющейся непосредственным обобщением проблемы Борсука,

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

взаимосвязь со знаменитыми статьями Г. Батлера (см. [16]), П. Эрдеша и К.А. Рождерса (см. [17]), Д. Лармана и К.А. Рождерса (см. [18]) и многими другими.

Наконец, задача об оптимальных решетчатых покрытиях также имеет более чем 70-летнюю историю и тесно связана с таким разделом алгебры, как теория Диофантовых приближений и неравенств (см. [12], [19]).

Основные определения

Пусть Ф — произвольное ограниченное множество в Мт, п — натуральное число. Обозначим через точную нижнюю грань положительных вещественных чисел х, обладающих тем свойством, что Ф может быть полностью покрыто п множествами ФЬФ2,...,ФП, диаметры которых не превосходят х\

¿С(ф) =^{2;е1+:ФСФ1и...и Фп, Уг сНатФ; ^ х} .

Можно показать (см. [1]), что эта точная нижняя грань достижима, то есть что Ф может быть полностью покрыто п множествами, диаметры которых не превосходят а^(Ф).

Последовательности ¿/™(Ф) и е™(Ф) = ^/п • (элементы последова-

тельностей всюду будут нумероваться индексом п) называются соответственно кодом деления и нормированным кодом деления множества Ф.

Заметим, что для произвольного Ф С Кта последовательность с1™(Ф) является невозрастающей, поскольку в классе всех покрытий п+ 1 множеством существует подкласс, для которого Фп+1 = 0, совпадающий с классом всех покрытий п множествами.

Кроме того, легко убедиться, что для произвольного Ф С Мт существуют такие неотрицательные (а в случае, когда Ф содержит подмножество ненулевой жордановой меры, — положительные) константы С\ = С^Ф) и Сг = СгСФ), что для всех натуральных п справедливо неравенство С\ ^ е™(Ф) ^ С2, которое равносильно оценке ^ ^(Ф) ^ (см., например, [20]).

Цикл работ [60]—[63], а также третья глава диссертации посвящены доказательству теоремы о существовании предела нормированного кода деления произвольного ограниченного множества, замыкание которого измеримо по Жордану. Иными словами, для произвольного такого множества Ф С К771 в действительности существует единственая константа С = С(Ф), с которой

ип •

При этом, в силу теоремы о площадях, доказанной в работе [60], для произвольных ограниченных множеств Фх и Ф2 в Мт, замыкания которых из-

меримы по Жордану и имеют меры дх и /12 соответственно, причём ¡12 ф О, справедливо соотношение

С(ф2) V №'

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

С = 8Щ>С(Ф)>

где супремум берётся по всем множествам Ф диаметра 1 в Мто. Заметим, что из невозрастания последовательности Ф) для произвольного Ф С Ет следует, что последовательности (1™ также не возрастают для всех т.

Получению точных значений и оценок сверху и снизу величин (I™ для различных пит посвящены первые две главы диссертации.

Очевидно, что для каждого п £ N произвольное множество единичного диаметра в Мт может быть покрыто п множествами, диаметры которых не превосходят с1™.

Значения с1™ не изменятся, если взять супремумы только по всем выпуклым и замкнутым множествам Ф диаметра 1. Действительно, если обозначить через [Ф] замыкание, а через сопу Ф выпуклую оболочку множества Ф, то сИат [сопуФ] = сНатФ и Ф С [сопуФ], поэтому с1™(Ф) ^ «¿™([сопуФ]).

Заметим также, что чуть более тонкие рассуждения показывают, что всякое множество диаметра 1 содержится в некотором множестве постоянной ширины I1 (см. [21]), и поэтому достаточно взять супремум лишь по выпуклым замкнутым множествам постоянной ширины 1 без изменения значений

Напомним, что универсальным покрывающим множеством (или универсальной покрышкой) называется такое множество Пто С Кт, что любое множество Ф С диаметра 1 может быть полностью накрыто 0,т (то есть в Мт существует такое множество О™, конгруэнтное что Ф С Од1). Аналогично, универсальной покрывающей системой называется такая система множеств Г2т = что произвольное множество Ф С Мто диаметра 1

может быть полностью накрыто одним из множеств П™. Здесь I — некоторый (возможно, бесконечный) набор индексов. Универсальное покрывающее множество является частным случаем универсальной покрывающей системы, когда I состоит из одного элемента. Подробнее об универсальных покрывающих множествах и системах см. в [22], [23].

Легко видеть, что, если Г2ТО = } 7 — универсальная покрывающая система, то для произвольного п £ N справедливо неравенство с1™ ^ эир

ае1

1 Напомним, что выпуклое множество называется множеством постоянной ширины 1, если его ширина по каждому направлению (то есть расстояние между двумя опорными гиперплоскостями к множеству, перпендикулярными данному направлению) равна 1.

В частности, если — универсальное покрывающее множество, то сЩ ^ с/™(ГГг) для всех натуральных п.

Простейшим примером универсальной покрышки в Мт является т-мер-ный гиперкуб с единичной длиной стороны.

Кроме того, в 1901 году Юнг показал (см. [24]), что в Ш™ универсальной покрышкой является шар радиуса у/2т+2-

На плоскости и в трёхмерном пространстве известны также и другие универсальные покрышки.

В 1920 году Пал в своей работе [25] (см. также [5]) доказал, что правильный шестиугольник с длиной стороны является универсальной покрышкой на плоскости. Более того, можно убедиться, что от такого шестиугольника можно "отрезать" два треугольника с тем, чтобы полученный усеченный шестиугольник по-прежнему оставался универсальной покрышкой (см., например,

И).

Для трёхмерного пространства Хеппеш и Грюнбаум в 1957 году показали (см. [26], [27]), что правильный октаэдр с единичным расстоянием между противоположными гранями является универсальной покрышкой. Кроме того, усечённый окраэдр, от которого плоскостями, отстоящими от трёх плоскостей симметрии октаэдра на расстояние "отрезаны" три четырёхугольные пирамиды, также является универсальной покрышкой.

Наконец, в 1997 году Макеев (см. [23], [28]) построил ещё две универсальные покрышки — ромбододекаэдр, у которого расстояние между параллельными гранями равно 1, а также усечённый ромбододекаэдр, от которого отсечены три четырёхугольных пирамиды по такому же принципу, как и от октаэдра. Изображения и более подробные описания универсальных покрышек в трёхмерном пространстве можно найти в [3].

Универсальные покрышки и покрывающие системы являются весьма эффективным инструментом для получения верхних оценок величин (I™. Для получения нижних оценок автором в статье [64] был разработан также показавший себя эффективным метод расслоения, который мы более подробно опишем во второй главе диссертации.

Обзор известных результатов

Заметим, прежде всего, что на одномерной прямой задача об отыскании величин (¿п является тривиальной, поскольку универсальное покрывающее множество — единичный отрезок имеет единичных диаметр, откуда очевидным образом следует, что для произвольного натурального п справедливо

равенство

п

Получением асимптотических и точных оценок на двумерной плоскости занимался Ленд, отыскавший в работах [20], [29] точные значения

(]2 _ 1 И2 _ , 12 _ И2 _ ,2 _ 1 а1 — 1) "2 — 15 аз — 2 ' 4 ~~ ' 2 '

а также получивший оценки

2 7Г О 1

^ эт — , ^

5 ' ь " л/3 '

1 . ,о . 1 /2 /4 2тг

и асимптотические оценки

/ ' * +0(1)

12

Также в книге [30] упоминается оценка 4 ^ Наконец, в работе [31] доказаны оценки

п

2С05§

,2 1 ,2 у/2657 - 896л/3

-—-— « 0.3324.

Кроме того, что в работе [32] также были получены точные значения и оценки величин 4(Ф) при небольших значениях п для трёх различных множеств Ф — круга, квадрата и правильного треугольника.

Для случая трехмерного пространства в книге [5] и статье [33] получены оценки

4 > 4 ^ 0.9425.

Кроме того, в работе [34] найдены точные значения и получены оценки величин ^(б1) для малых п для единичной сферы 5, из которых очевидным образом получаются следующие оценки:

4 > уЦ-

Заметим, что в доказательстве теоремы ¿д в статье [34] мы обнаружили существенную ошибку, исправление которой как автору настоящей работы,

так и автору [34] не представляется возможным; таким образом, утверждение

теоремы <?9, а также следующее из него неравенство (і\ ^ нельзя считать справедливыми.

Для случая пространств большей размерности, в статье [35] показано, что для произвольного натурального т справедливо неравенство

^ < /4т2 + У8ш2 + 1-1

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

С > (2)

В работе [20] данное утверждение доказано для случая т = 2 следующим образом. Среди всех измеримых множеств диаметра 1 на плоскости максимальную площадь имеет круг (см. [36]). Поэтому для произвольного натурального п суммарная площадь п множеств диаметра с^(-О) на плоскости (где В — круг единичного диаметра), с одной стороны, не меньше его площади а с другой — не превосходит ^ • (о^)2, откуда имеем с/2 ^ ^п(^) ^ Заметим, что при т > 1 неравенство (2) является строгим, поскольку очевидно, что единичный шар не может быть замощен непересекающимися шарами меньшего диаметра.

Приведенное выше рассуждение может быть проведено в пространстве произвольной размерности, поскольку, как показано, например, в [37], среди всех множеств диаметра 1 в 1КТО максимальный объём имеет т-мерный шар.

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

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

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

Список литературы диссертационного исследования кандидат физико-математических наук Филимонов, Владислав Павлович, 2013 год

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

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

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

[3] A.M. Райгородский, Вокруг гипотезы Борсука, Итоги науки и техники, Сер. "Современная математика", 23 (2007), 147 - 164.

[4] A.M. Raigorodskii, Three lectures on the Borsuk partition problem, London Mathematical Society Lecture Note Series, 347 (2007), 202 - 248.

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

[6] V.G. Boltyanski, Н. Martini, P.S. Soltan, Excursions into combinatorial geometry, Universitext, Springer, Berlin, 1997.

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

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

[9] L.A. Székely, Erdös on unit distances and the Szemerédi-Trotter theorems, Paul Erdos and his Mathematics, Bolyai Series Budapest, J. Bolyai Math. Soc., Springer, 11 (2002), 649 - 666.

[10] P. Brass, W. Moser, J. Pach, Research problems m discrete geometry, Springer, 2005.

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

[12] А. Schuermann, F. Vallentin, Methods in the Local Theory of Packing and Covering Lattices, 2008, http://arxiv.org/abs/math/0412320v2.

C.A. Rogers, Covering a sphere with spheres, Mathematika, 10 (1963), 157 -164.

R. Rankin, On the closest packing of spheres in n dimensions, Ann. Math., 48 (1947), 1062 - 1081.

J. Bourgain, J. Lindenstrauss, On covering a set in WLd 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.

G.J. Butler, Simultaneous packing and covering in Euclidean space, Proc. Lon. Math. Soc., Ser. 3, 25 (1972), N4, 721 - 735.

P. Erdos, C.A. Rogers, Covering space with convex bodies, Acta Arithmetica, 7 (1962), 281 - 285.

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

R.P. Bambah, On lattice coverings by spheres, Proc. Nat. Inst. Sei. India, 20 (1954), 25 - 52.

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

H.G. Eggleston, Convexity, Cambridge Univ. Press, 1958.

B. Weissbach, Polyhedral covers, Coll. Math. Soc. J. Bolyai, North-Holland, 48 (1987), 639 - 646.

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

H.W.E. Jung, Uber■ die kleinste Kugel, die eine raumliche Figur einschliesst, J. reine und angew. Math., 123 (1901), 241 - 257.

J. Pal, Uber ein elementares Variationsproblem, Danske Videnskab. Selskab., Math.-Fys. Meddel 3 (1920), N2.

A. Heppes, Terbeli ponthalmazok felosztäsa kisebb ätmeröjü reszhalmazok összegere, A magyar tudomänyos akademia, 7 (1957), 413 - 416.

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

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

Н. Lenz, Zerlegung ebener Bereiche in konvexe Zellen von möglichst kleinem Durchmesser, Jahresbericht d. DMV Bd., 58 (1956), 87 - 97.

Г. Хадвигер, Г. Дебруннер, Комбинаторная геометрия плоскости, Москва, "Наука", 1965.

М. Dembinski, М. Lassak, Covering plane sets with sets of three times less diameter, Demonstratio Math., XVIII (1985), 517 - 525.

A. Heppes, Covering a planar dom,ain with sets of small diameter, Periodica Mathematica Hungarica, 53 (2006), 157 - 168.

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

A. Heppes, Decomposing the 2-sphere into domains of smallest possible diameter, Periodica Mathematica Hungarica, 36 (1988), 171 - 180.

M. Lassak, An estimate concerning Borsuk partition problem, Bull. Acad. Polon. Sei. Ser. Math., 30 (9-10), 449 - 451 (1982).

T. Bonnesen, W. Fenchel, Theorie der konvexen Korper, Erg. d. Math., III/1 (1934), P. 34.

Ю.Д. Бураго, В.А. Залгаллер, Геометрические неравенства, Ленинград: Наука, 1980, С. 93.

Д. Шклярский, О разбиениях двумерной сферы. Математический Сборник, 16 (58), 1945, N2, 125 - 128.

J. Matousek, Using the Borsuk-Ulam Theorem: Lectures on Topological Methods m Combinatorics and Geometry, Springer, 2003.

P. Leopardi, Distributing points on the sphere: Partitions, separation, quadrature and energy, Ph.D. dissertation, School of Mathematics and Statistics, Departement of Applied Mathematics, University of New South Wales, November 2006.

[41] A. Postnikov, Permutohedra, Associahedra, and Beyond, Int Math Res Notices, 6 (2009), 1026 - 1106.

A. Гарбер, А. Поярков, О перестановочных многогранниках, Вестник Московского университета. Серия 1: Математика, механика, N2 (2006), 3 - 7.

Р. Gaiha, S.K. Gupta, Adjacent vertices on a permutohedron, SIAM Journal on Applied Mathematics, 32 (1977), N2, 323 - 327.

J. Santmyer, For All Possible Distances Look to the Permutohedron, Mathematics Magazine, 80 (2007), N2, 120 - 125.

B.A. Венков, О некотором классе эвклидовых многогранников, Вестник Ленинградского университета, Серия математика, физика, химия, N9 (1954), 11 - 31.

И.Г. Араманович, P.C. Гутер, Л.А. Люстерник, Математический анализ. Дифференцирование и интегрирование., Москва: ГИФМЛ, 1961, С. 309.

Г.И. Архипов, В.А. Садовничий, В.Н. Чубариков, Лекции поматемати-ческому анализу., Москва, 2003, С. 430 - 434.

L. Fejes-Töth, Lagerungen in der Ebene, auf der Kugel und im Raum, BerlinGottingen-Heidelberg, 1953, P. 67.

M.N. Bleicher, Lattice coverings ofn-space by spheres, Canad. J. Math, 1962, 632 - 650.

E. Hlawka, Ausfullung und Uberdeckung konvexer Korper durch konvexe Korper, Monatshefte fur Mathematik, 53, N2, 81 - 131.

R. Kershner, The Number of Circles Covering a Set, American Journal of Mathematics, 61 (1939), N3, 665 - 671.

Б.Н. Делоне, С.С. Рышков, Решение задачи о наименее плотном решетчатом покрытии 4-мерного пространства равными сферами, Доклады Академии Наук СССР, 4 (1963), 1333 - 1334.

Е.П. Барановский, С.С. Рышков, Примитивные пятимерные паралле-лоэдры, Доклады Академии Наук СССР, 14 (1973), 1391 - 1395.

Н. Davenport, The covering of space by spheres, Rendiconti del Circolo Matematico di Palermo, Springer, 1 (1952), N1, 92 - 107.

G.L. Watson, The covering of space by spheres, Rendiconti del Circolo Matematico di Palermo, 5 (1956), N1, 93 - 100.

[56] С.A. Rogers, Lattice coverings of space, Mathematika, 6 (1959), 33 - 39.

[57] W. Blaschke, Kreis und Kugel, Veit, Leipzig, 1916.

[58] F. Hausdorff, Grundzuge der Mengenlehre, Veit, Leipzig, 1914.

[59] B. Bollobas, An extension of the isoperimetric inequality on the sphere, Elemente der Mathematik, 44 (1989), 121 - 124.

[60] В.П. Филимонов, Коды деления и теорема о площадях, Доклады Академии Наук, 426 (2009), N2, 173 - 176.

[61] В.П. Филимонов, Теорема о малых отклонениях для кодов деления, Доклады Академии Наук, 431 (2010), N5, 593 - 597.

[62] В.П. Филимонов, Теорема о рациональной периодичности для кодов деления, Доклады Академии Наук, 434 (2010), N2, 168 - 172.

[63] В.П. Филимонов, Теорема о вещественной периодичости для кодов деления, Доклады Академии Наук, 436 (2011), N4, 452 - 457.

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

г\

115 4