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

• Автор: Филимонов, Владислав Павлович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2013
• Место защиты: Москва
• Количество страниц: 115 с. : ил.

Оглавление
Введение
1 Оценки в К2
1.1 Формулировки результатов
1.2 Доказательства
1.3 Комментарии
1.4 Таблица результатов
2 Оценки в Кт
2.1 Оценки снизу в К
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 Асимптотические оценки сверху в Шт
2.4.1 Получение оценок
2.4.2 Асимптотика при т —> оо
2.4.3 Гипотеза об асимптотике й при 1 ^ т ^
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 лет, и ее популярность огромна. При решении данной задачи была разработана техника, относящаяся к так называемым разбиениям Вороного и имеющая непосредственную

некоторого п £ N). При этом в сумме, определяющей д(х), слагаемое, соответствующее этой окружности, в точке х уменьшается на 1 либо на 2. Обозначим число сторон многоугольника через т. В этом случае диаметр его описанной окружности равен х (sin^J . Если эта окружность — то
справедливо равенство х (sin 1 = 1 — 2кх, откуда х = (2к + (sin ^
Все числа такого вида (при к ^ 0, т ^ 3) вместе с числами вида ддд (при п ^ 0), упорядоченные по убыванию, и образуют последовательность хп.
В таблице 1.3 представлены все “неулучшаемые” оценки, более сильные, чем соответствующие оценки (1), а также следствия из них, основанные на невозрастании dn. Следствий всего четыре — при п = 11,19,27 и 38, и они возникли из-за того, что в соответствующих точках хп левый и правый пределы функции д(х) отличаются на 2.
В первом столбце указан номер элемента последовательности п, во втором и третьем — оценки снизу для dn. основанные на (1) и (14) соответственно, в последнем — точное значение оценки. Все константы приведены с четырьмя верными знаками после запятой. Прочерк означает, что оценка (14) для данного п оказалась не лучше, чем оценка (1).
Таблица 1.3: Сравнение оценок
п (1) Теорема
8 0.3535 0.4338 sin f
9 0.3333 0.3826 sinf
10 0.3333 0.3420 sinf
И 0.3333 - 1
12 0.3333 - 1
13 0.3333 - 1
14 0.2672 0.3090 sini
15 0.2581 0.2928 (2 + (sinf)-')-
16 0.2500 0.2817 sin jY
17 0.2425 0.2701 (2 +(sinf)-1)-
18 0.2357 0.2588 sin Y^
19 0.2294 0.2500 l
20 0.2236 0.2500 1
21 0.2182 0.2393 Sinfk
22 0.2132 0.2323 (2 +(sinf)“1)’
23 0.2085 0.2225 smff
24 0.2041 0.2167 (2 + (smf)-1)’