О покрытиях множеств в евклидовых пространствах

Вступление.

В данной работе будут изложены результаты, связанные с классической проблемой Борсука (см. [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]), что эта точная нижняя грань достижима, то есть что Ф может быть полностью покрыто п множествами, диаметры которых не превосходят а^(Ф).

Последовательности ¿-/&trade-(Ф) и е™(Ф) = ^/п • (элементы последовательностей всюду будут нумероваться индексом п) называются соответственно кодом деления и нормированным кодом деления множества Ф.

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

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

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

При этом, в силу теоремы о площадях, доказанной в работе [60], для произвольных ограниченных множеств Фх и Ф2 в Мт, замыкания которых измеримы по Жордану и имеют меры дх и /12 соответственно, причём ?12 ф О, справедливо соотношение.

С (ф2) V №'.

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

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

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

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

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

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

Напомним, что универсальным покрывающим множеством (или универсальной покрышкой) называется такое множество Пто С Кт, что любое множество Ф С диаметра 1 может быть полностью накрыто 0, т (то есть в Мт существует такое множество О&trade-, конгруэнтное что Ф С Од1). Аналогично, универсальной покрывающей системой называется такая система множеств Г2т = что произвольное множество Ф С Мто диаметра 1 может быть полностью накрыто одним из множеств П&trade-. Здесь I — некоторый (возможно, бесконечный) набор индексов. Универсальное покрывающее множество является частным случаем универсальной покрывающей системы, когда I состоит из одного элемента. Подробнее об универсальных покрывающих множествах и системах см. в [22], [23].

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

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

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

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

Кроме того, в 1901 году Юнг показал (см. [24]), что в Ш&tradeуниверсальной покрышкой является шар радиуса у/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).

Также в книге [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] не представляется возможнымтаким образом, утверждение теоремы .

Для случая пространств большей размерности, в статье [35] показано, что для произвольного натурального т справедливо неравенство < /4т2 + У8ш2 + 1−1.

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

С > (2).

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

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

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

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

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

1. К. Borsuk, Drei Satze uber die n-dimensionale euklidische Sphare, 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. 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.

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

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

12. С.A. Rogers, Lattice coverings of space, Mathematika, 6 (1959), 33 39.

13. W. Blaschke, Kreis und Kugel, Veit, Leipzig, 1916.

14. F. Hausdorff, Grundzuge der Mengenlehre, Veit, Leipzig, 1914.

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

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

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

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

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

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