close

Вход

Забыли?

вход по аккаунту

?

Упаковки и раскраски сфер в многомерных пространствах.

код для вставкиСкачать
Московский государственный университет имени М.В.Ломоносова
На правах рукописи
Купавский Андрей Борисович
Упаковки и раскраски сфер
в многомерных пространствах
01.01.06 — математическая логика, алгебра и теория чисел,
01.01.09 — дискретная математика и математическая кибернетика
АВТОРЕФЕРАТ
диссертации на соискание ученой степени
кандидата физико-математических наук
Москва — 2013
Работа выполнена на кафедре теории чисел Механико-математического
факультета Московского государственного университета имени
М.В. Ломоносова.
Научные руководители:
доктор физико-математических наук,
профессор Райгородский Андрей Михайлович,
доктор физико-математических наук,
профессор Мощевитин Николай Германович
Официальные оппоненты: Быковский Виктор Алексеевич
член-корреспондент РАН
Хабаровское отделение ФГБУН ИПМ
ДВО РАН, директор института
Кабатянский Григорий Анатольевич
доктор физико-математических наук
ФГБУН Институт проблем передачи
информации имени А.А. Харкевича РАН,
главный научный сотрудник
Ведущая организация:
ФГБОУ “Ярославский государственный
университет имени П.Г. Демидова”
Защита диссертации состоится 26 апреля 2013 года в 16 часов 45
минут на заседании диссертационного совета Д 501.001.84 при МГУ имени М.В. Ломоносова по адресу: РФ, 119991, Москва, ГСП-1, Ленинские
горы, д.1, МГУ, Механико-математический факультет, аудитория 14-08.
С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М.В. Ломоносова (Ломоносовский проспект, 27, сектор А, 8-й этаж).
Автореферат разослан 26 марта 2013 г.
Ученый секретарь диссертационного
совета Д 501.001.84 при МГУ,
доктор физико-математических наук,
профессор
Иванов Александр Олегович
Общая характеристика работы
Актуальность работы
Комбинаторная геометрия – очень активно развивающаяся область
на стыке дискретной математики и геометрии чисел. Изначальный интерес к этой области возник, в частности, благодаря работам Борсука1
и Эрдеша2 . В этих работах были сформулированы задача о разбиении
тел на части меньшего диаметра, задача о максимальном числе инциденций между точками и прямыми на плоскости, задача о числе различных
и одинаковых расстояний между n точками на плоскости. Чуть позже,
в 1950 году, Нелсоном была поставлена задача о хроматическом числе
плоскости, которая вскоре была обобщена на случай произвольной размерности. Эти проблемы тесно связаны между собой и стали центральными в комбинаторной геометрии. За последние годы было опубликовано множество статей по этой тематике. Одними из наиболее важных
являются статья Кана и Калаи3 , в которой они опровергают гипотезу
Борсука о том, что любое тело в Rn диаметра единица можно разбить
на n + 1 часть строго меньшего диаметра, и статья Гута и Каца4 , в которой они доказывают гипотезу Эрдеша о том, что между n точками на
плоскости должно быть по крайней мере n1−ō(1) различных расстояний.
Значительным прорывом в задаче о хроматическом числе пространства стал результат Франкла и Вилсона5 , которые с помощью линейноалгебраического метода показали, что хроматическое число пространства растет экспоненциально с ростом размерности. После этого асимптотическая нижняя оценка хроматического числа пространства была уточнена Райгородским6 за счет рассмотрения более общей конструкции. С
другой стороны, за последние 20 лет было получено очень много нижних
оценок хроматических чисел пространств малых размерностей. По ви1
K. Borsuk, Drei Sätze über die n-dimensionale Euklidische Sphäre, Fund. Math., 20 (1933), 177 - 190.
P. Erdős, On a set of distances of n points, Amer. Math. Monthly, 53 (1946), 248 - 250.
3
J. Kahn, G. Kalai, A counterexample to Borsuk’s conjecture, Bull. Amer. Math. Soc., 29 (1993), N1,
60 - 62.
4
L. Guth, N.H. Katz, On the Erdős distinct distance problem on the plane, 2010, arXiv:1011.4105.
5
P. Frankl, R. Wilson, Intersection theorems with geometric consequences, Combinatorica, 1 (1981),
357 - 368.
6
А.М. Райгородский, О хроматическом числе пространства, Успехи матем. наук, 55 (2000), N2,
147 - 148.
2
1
димому, наиболее интересен результат Нечуштана7 , который с помощью
сложной геометрической конструкции доказал, что хроматическое число
пространства не меньше шести. Кроме него различные оценки получали Кантвелл, Райгородский, Цибулька. В диссертации за счет сочетания
геометрических соображений и линейно-алгебраического метода получается доказать ряд нижних оценок хроматических чисел пространств,
уточняющих ранее известные.
Хроматические числа изучались не только для евклидовых пространств. Определение хроматического числа для произвольного метрического пространства было дано в работе Бенды и Перлеса8 . Много работ
посвящено хроматическому числу пространства Qn с евклидовой метрикой (работы Бенды и Перлеса, Райгородского, Цибульки, Чилакамари
и др.) и хроматическому числу сфер (работы Ловаса, Райгородского,
Симмонса). В диссертации мы вводим определение пестроты пространства, которое, с одной стороны, обобщает определение хроматического
числа, данное Бендой и Перлесом, а с другой стороны, позволяет поставить в более общий контекст работы Нечуштана, Цибульки и др., в которых получены нижние оценки хроматических чисел пространств малых
размерностей. В диссертации автором разработан подход, позволяющий
поднимать нижние оценки хроматического числа в бо́льшие размерности. При этом ключевую роль здесь играют раскраски сфер.
В последние годы в задаче о хроматическом числе пространства находят применение методы геометрии чисел. Все верхние оценки хроматических чисел пространств в малых размерностях получаются за счет
рассмотрения покрасок, основанных на решетках (см. работу Радоичича
и Тота9 ). Так, например, известный результат о том, что хроматическое
число плоскости не превосходит семи, получается на основе гексагональной решетки. Плоскость замощается шестиугольниками диаметра чуть
меньше единицы, после чего каждый шестиугольник красится в один
цвет таким образом, чтобы расстояние между соседними шестиугольниками одного цвета было больше единицы.
7
O. Nechushtan, On the space chromatic number, Discrete Math., 256 (2002), 499 - 507.
M. Benda, M. Perles, Colorings of metric spaces, Geombinatorics, 9 (2000), 113 - 126.
9
R. Radoičić, 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.
8
2
То, что методы геометрии чисел можно применить к получению
асимптотических верхних оценок хроматических чисел, было замечено Ларманом и Роджерсом10 . В своей работе они доказали асимптотическую верхнюю оценку хроматического числа пространства с евклидовой нормой. Недавно Канг и Фюреди11 смогли получить асимптотическую верхнюю оценку хроматического числа пространства с произвольной нормой. В диссертации доказаны оценки, существенно уточняющие и обобщающие результат Канг и Фюреди. Для этого используются различные теоремы геометрии чисел и смежных областей: классическая теорема Минковского–Главки и ее уточнения Шмидтом12 , граница
Кабатянского–Левенштейна13 , результаты Элкеша, Одлыжко и Раша14
касательно упаковок суперсфер. Кроме того, доказывается аналог теоремы Эрдеша–Роджерса15 .
Как уже говорилось выше, одним из важнейших событий в комбинаторной геометрии последних десятилетий стало опровержение гипотезы
Борсука. Сам контрпример был получен в размерности 2015 на основе
линейно-алгебраического метода. После 1993 года, в котором вышла статья Кана и Калаи, появилось множество статей, в которых авторы понижали размерность контрпримера. Нилли, Грэй и Вайсбах, Райгородский,
Вайсбах, Хинрихс, и, наконец, Хинрихс и Рихтер16 довели минимальную
размерность контрпримера до 298. С другой стороны, известно, что гипотеза Борсука верна в размерностях n 6 3, и естественным образом
возникла следующая задача. Пусть мы разбиваем (двумерное или трехмерное) множество диаметра единица на фиксированное число частей
меньшего диаметра. Насколько маленького диаметра можно получить
части? В этом направлении получали результаты Лассак17 , Макеев, Хеп10
D.G. Larman, C.A. Rogers, The realization of distances within sets in Euclidean space, Mathematika,
19 (1972), 1 - 24.
11
Z. Füredi, J.-H. Kang, Covering the n-space by convex bodies and its chromatic number, Discrete
Math., 308 (2008), 4495 - 4500.
12
W.M. Schmidt, On the Minkowski–Hlawka theorem, Illinois J. Math., 7 (1963), 18 - 23.
13
Г.А. Кабатянский, В.И. Левенштейн, О границах для упаковок на сфере и в пространстве,
Пробл. передачи информ., 14 (1978), N1, 3 - 25.
14
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.
15
P. Erdős, C.A. Rogers, Covering space with convex bodies, Acta Arithmetica, 7 (1962), 281 - 285.
16
A. Hinrichs, C. Richter, New sets with large Borsuk numbers, Discrete Math., 270 (2003), 137 - 147.
17
M. Lassak, An estimate concerning Borsuk’s partition problem, Bull. Acad. Polon. Sci. Ser. Math.,
3
пеш, Филимонов и др. В диссертационной работе мы уточняем результат
Лассака для описанной выше задачи о разбиении трехмерных тел на пять
частей меньшего диаметра. Наш подход основан на технике универсальных покрывающих систем. Этот подход, в частности, был использован
Хеппешем при доказательстве гипотезы Борсука в R3 .
Цель работы состоит в решении следующих задач: установить новые нижние и верхние оценки хроматических чисел пространств, ввести
и изучить понятие пестроты сфер, разработать общий метод поднятия
нижних оценок хроматического числа в бо́льшие размерности, получить
новую верхнюю оценку диаметра частей в задаче о разбиении трехмерных тел на пять частей как можно меньшего диаметра.
Научная новизна
Все результаты диссертации являются новыми. Перечислим основные
из них:
1. Доказаны новые нижние оценки хроматических чисел пространств
в размерностях 9–12. Точнее, получены оценки χ(R9 ) > 21, χ(R10 ) >
23, χ(R11 ) > 25, χ(R12 ) > 27.
2. Разработан общий метод поднятия нижних оценок хроматического
числа пространства в бо́льшие размерности.
3. Доказано, что любое трехмерное множество диаметра единица можно разбить на пять частей, диаметр каждой из которых не превосходит величины 0.9425.
4. Доказано, что хроматическое число пространства Rn с произвольной нормой не превосходит величины (4 + ō(1))n , получены уточнения этого результата в случае пространств с lp -нормой, где p > 2.
30 (1982), 449 - 451.
4
Основные методы исследования
В работе используются линейно-алгебраический метод, разнообразные методы комбинаторной геометрии, методы геометрии чисел, методы
теории графов, вероятностный метод.
Теоретическая и практическая ценность
Диссертация имеет теоретический характер. Полученные в диссертации результаты представляют интерес для специалистов по комбинаторной геометрии, геометрии чисел и дискретной математике.
Апробация работы
Результаты диссертации докладывались на следующих научноисследовательских семинарах:
— Московский семинар по теории чисел под руководством член-корр.
РАН, профессора Ю.В. Нестеренко и профессора Н.Г. Мощевитина
(мех-мат МГУ, 2012 г.).
— Семинар “Вероятностные и алгебраические методы в комбинаторике” под руководством профессора А.М. Райгородского (мехмат
МГУ, 2007-2012 гг., неоднократно).
— Семинар “Тригонометрические суммы и их приложения” под руководством профессора Н.Г. Мощевитина (мехмат МГУ, 2010г.).
— Семинар “Узлы и теория представлений” под руководством профессора В.О. Мантурова, ассистента Д.П. Ильютко и ассистента И.М.
Никонова (мехмат МГУ, 2011 г.).
— Семинар “Дискретный анализ” под руководством профессора А.А.
Сапоженко (ВМиК МГУ, 2011 г.).
— Семинар по теории кодирования под руководством д.ф.-м.н. Л.А.
Бассалыго (ИППИ РАН, 2011 г.).
— Научно-исследовательский семинар по математической логике под
руководством акад. РАН, профессора С.И. Адяна и член-корр. РАН,
профессора Л.Д. Беклемишева (мехмат МГУ, 2012 г.).
5
— Кафедральный семинар кафедры дискретной математики под руководством профессора А.М. Райгородского (ФИВТ МФТИ, 2010–
2012 гг.).
— Семинар под руководством проф. П. Тетали (Georgia Tech, 2011г.).
Результаты диссертации докладывались на следующих международных
конференциях:
— “Fete of combinatorics” (г. Кестхей, Венгрия, 11 – 15 Августа 2008г.).
— “EuroComb” (г. Бордо, Франция, 7–11 Сентября 2009г.).
— “Геометрия, топология и приложения” (Москва, 16 – 20 Августа
2010г.).
— “8th French Combinatorial Conference” (г. Париж, Франция, 28 Июня
– 2 Июля 2010 г.).
— “IFS Conference” (г. Будапешт, Венгрия, 13 – 17 Июня 2011 г.).
— “Диофантовы приближения. Современное состояние и приложения”
(Минск, Беларусь, 3 – 9 Июля 2011 г.).
— “7th Slovenian International Conference on Graph Theory” (Блед, Словения, 19 – 25 Июня 2011 г.).
— “SIAM Conference on Discrete Mathematics” (Галифакс, Канада, 18 –
21 Июня 2012 г.).
— “Вероятностные методы в дискретной математике” (Петрозаводск,
2 – 9 Июня 2012 г.).
— “Cycles and Colorings” (Новый Смоковец, Словения, 9 – 14 Сентября
2012 г.).
— “4th Polish Combinatorial Conference” (Познань, Польша, 17 – 21 Сентября 2012 г.).
Работа автора поддержана грантом РФФИ 09-01-00294, грантом РФФИ 12-01-00683 и грантом Президента МД-8390.2010.1.
6
Публикации
Результаты диссертации опубликованы в 6 работах автора (все они
входят в перечень ВАК), список которых приведен в конце автореферата
[1–6].
Структура диссертации
Диссертация состоит из введения, трех глав и списка литературы, насчитывающего 70 наименований. Общий объем диссертации составляет
88 страниц.
Краткое содержание диссертации
Во введении к диссертации излагается история задачи о хроматическом числе, история проблемы Борсука, а также история задачи о поиске
плотнейшей упаковки шаров и других задач геометрии чисел, близких
к теме диссертации. Вводятся определения хроматического числа пространства, числа Борсука, величин dnm , упаковки шаров, верхней плотности множества. Напомним, что хроматическим числом n-мерного пространства называется величина
(
χ(Rn ) = min m : Rn =
m
[
)
Vi , ∀i = 1, . . . , m ∀x, y ∈ Vi |x − y| =
6 1 .
i=1
Величины dnm определяются следующим образом:
(
dnm =
sup
inf
x : ∃Φ1 , . . . , Φm : Φ =
Φ⊂Rn ,diam Φ=1
m
[
)
Φi , ∀i diam Φi 6 x .
i=1
Содержание главы 1
Глава 1 посвящена вопросам, связанным с хроматическими числами
пространств малых размерностей, поднятием оценок в бо́льшую размерность и пестротой. В разделе 1.1 дается определение хроматического числа для произвольного метрического пространства через функции правильной раскраски. Приводится ряд результатов касательно верхних и
нижних оценок хроматического числа в пространствах малых размерностей.
7
В разделе 1.2 излагается доказательство оценки χ(R9 ) > 21. В параграфе 1.2.1 вводится ключевое определение дистанционного графа: назовем H = (V, E) дистанционным графом в Rn , если множество его
вершин V — это подмножество Rn , а множество его ребер состоит из
пар вершин, отстоящих друг от друга на расстояние a > 0, где a — это
некоторое фиксированное число. Дается определение числа α(H) независимости графа H. Выполняются следующие оценки: χ(H) 6 χ(Rn ) для
любого дистанционного графа H, χ(H) > |V |/α(H) для любого графа.
В этом же параграфе определен граф G, на основе которого получена
оценка хроматического числа R9 : G = (V, E),
V = {v = (v1 , . . . , v10 ), vi ∈ {0, 1}, v1 + . . . + v10 = 5},
E = {{u, v} ∈ V × V, (u, v) = u1 v1 + . . . + u10 v10 = 3}.
Сформулирована теорема о числе независимости рассматриваемого графа, которая говорит, что α(G) = 12. Из нее следует нижняя оценка
хроматического числа графа G, а, значит, и хроматического числа R9 .
Кроме того, из оценки χ(R9 ) > 21 выводится оценка χ(R10 ) > 23.
В параграфе 1.2.2 дано доказательство теоремы о числе независимости рассматриваемого графа. Сначала приводится пример независимого множества размера 12 в графе G. Затем с помощью линейноалгебраического метода доказывается лемма 1.
Лемма 1. В любом максимальном независимом множестве W векторов
из G обязательно найдутся два вектора со скалярным произведением
единица.
Далее предлагается удобный способ анализа возможных независимых
множеств графа G, который учитывает симметрии графа. Дальнейшие
рассуждения основаны на переборе случаев. В параграфе 1.2.3 с помощью многократного применения принципа Дирихле доказывается оценка
χ(G) 6 63.
В разделе 1.3 идет речь о поднятии нижних оценок хроматического
числа из размерности n в размерность n + 2. Установлена следующая
теорема.
Теорема 5. Пусть n > 2, а G – дистанционный граф с ребрами единичной длины, вершины которого расположены на сфере Srs ⊂ Rn ,
8
χ(G) > m. Пусть при этом радиус rs сферы удовлетворяет условиям
s
r
√
q
√
1
1+ 3
2
√ =
3 − 1, rs 6=
6 rs 6
.
2
3
2+ 3
Тогда χ(Rn+2 ) > m + 4.
Из этой теоремы получается оценка χ(R11 ) > 25. В параграфе 1.3.1
приводятся три вспомогательных леммы, среди которых можно отметить
лемму 3.
Лемма 3. В любой правильной раскраске пространства для любых r > 0,
n > 2 найдутся точки A, B ∈ Rn , такие, что |AB| = r и цвет точки
A отличен от цвета точки B.
В параграфе 1.3.2 завершается доказательство теоремы 5. Все доказательство основано на геометрических соображениях.
В разделе 1.4 теорема 5 помещена в более общий контекст. Вводится ключевое новое понятие пестроты множества относительно пространства.
Пусть (Γ, ρ) – метрическое пространство, U ⊂ Γ, ρu – метрика, индуцированная на U метрикой ρ. Пестрота π(U |(Γ, ρ)) множества U относительно пространства (Γ, ρ) — это
π(U |(Γ, ρ)) = min max χ0 (O(U )),
F
O
где O – произвольное преобразование пространства, сохраняющее метрику, F – правильная раскраска пространства, а χ0 (O(U )) – это количество
цветов, затраченное на покраску множества O(U ) при данной раскраске.
В дальнейшем изучается пестрота сфер π n (Srm ) = π(Srm |Rn ). В параграфе 1.4.1 изучается пестрота окружностей. Сформулирована и доказана
теорема 6, в которой в зависимости от радиуса и размерности пространства получены нижние оценки пестроты окружностей. Установлно следующее утверждение.
Утверждение 1. Для почти всех радиусов выполнено неравенство
χ(Sr1 ) < π 2 (Sr1 ).
Сформулированы теорема Ловаса о хроматическом числе сфер и некоторые вспомогательные утверждения касательно пестроты симплексов и
9
сфер. Далее приводится доказательство теоремы 6, основанное на геометрических соображениях.
Проведем связь между пестротой сферы и поднятием нижних оценок
хроматических чисел пространств в бо́льшие размерности. Пусть граф
G — дистанционный в Rn , χ(G) > m, и его вершины
лежат на сфере
√
радиуса r < 1. Пусть π n+k (Srk−1
) > x, где r0 = 1 − r2 . Покажем, что
0
χ(Rn+k ) > x + m. Действительно, зафиксируем правильную раскраску
Rm+k . Выберем сферу Srk−1
, покрашенную в > x цветов (такая существу0
ет по определению пестроты). После этого на сферу радиуса r, ортогональную данной, положим граф G. Цвета, в которые покрашен граф G,
должны быть отличны от цветов сферы Srk−1
.
0
В параграфе 1.4.2 изучается пестрота двумерных сфер. Получен
ряд результатов, обобщающих теорему 6. Как следствие, доказано, что
χ(R12 ) > 27 и передоказана оценка χ(R4 ) > 7. В параграфе 1.4.3 результаты теорем 6–9 обобщаются на многомерный случай. Основной результат дан в теореме 10, которая говорит, что при некоторых ограничениях
на радиус и при n 6 7 имеем π 2n (Srn−1 ) > 2n. Еще одним способом
передоказана оценка χ(R4 ) > 7. В пункте “основная конструкция” описана общая схема построения дистанционных графов, на основе которых
получаются оценки, в следующем пункте эта схема анализируется в разных случаях, соответствующих теоремам 10–12. В пункте “возможные
дальнейшие результаты” рассказаны возможные пути обобщения теорем
10–12, а также приводится довольно интересный частный случай таких
обобщений.
Теорема 13. Имеем π 3 (Sr2 ) > 5 при
s
(s
)
3
1
3
1
r∈
− √ ≈ 0.5846;
+ √ ≈ 1.0762 .
4
4
6
6
Содержание главы 2
Глава 2 посвящена разбиениям трехмерных тел на пять частей как
можно меньшего диаметра. Даны определения величин dnk (Φ), dnk . Проведена связь между этими величинами и проблемой Борсука, сформулирована основная теорема о том, что d35 6 0.9425. В разделе 2.1 даются ключевые определения: множество U называется универсальной покрышкой
10
в Rn , если
∀ Φ ⊂ Rn , diam Φ = 1, ∃ O, O(U ) ⊇ Φ,
где O – некоторое движение пространства; система множеств U называется универсальной покрывающей системой (УПС) в Rn , если
∀ Φ ⊂ Rn , diam Φ = 1, ∃ U ∈ U, ∃ O, O(U ) ⊇ Φ,
где O – снова некоторое движение пространства. Верен следующий факт:
пусть дана УПС U, тогда выполнено неравенство
dnk 6 sup dnk (U ).
U ∈U
Кроме того, в этом разделе описана универсальная покрышка, которую
использовал Лассак18 .
В разделе 2.2 производится построение УПС, на которой основано доказательство. Остановимся поподробнее на построении. За основу берется шар радиуса d, не превосходящего радиуса шара Юнга. Далее, описанный шар пересекается с двумя шарами радиуса единица с центрами
в некоторых граничных точках первого шара. Множества в полученной
УПС зависят от двух параметров: от радиуса первого шара и от положения центра третьего шара относительно центра второго. В лемме 6
доказывается, что полученная система действительно является УПС.
В разделе 2.3 строится разбиение множеств из УПС на пять частей
меньшего диаметра. Множества разбиваются плоскостями, параллельными координатным плоскостям. Границы частей, таким образом, состоят из кусков плоскостей и кусков сфер. Разбиения параметризуются
двумя параметрами.
В разделе 2.4 находятся диаметры частей разбиения при условии, что
радиус d был больше 0.592. В параграфе 2.4.1 строится разбиение границ частей множеств из УПС на двумерные, одномерные и нульмерные
составляющие. В последующих параграфах доказывается, что диаметр
каждой из частей разбиения каждого из множеств, лежащих в УПС, достигается на парах точек, принадлежащих нульмерным составляющим
границ, и находится диаметр каждой из частей. В параграфе 2.4.6 выбираются параметры разбиения и доказывается основная теорема в случае
18
M. Lassak, An estimate concerning Borsuk’s partition problem, Bull. Acad. Polon. Sci. Ser. Math.,
30 (1982), 449 - 451.
11
d > 0.592. В разделе 2.5 рассматривается случай d 6 0.592. Здесь нам
достаточно разбиения, аналогичного тому, которое использовал в своей
работе Лассак.
Содержание главы 3
Глава 3 посвящена верхним оценкам хроматических чисел пространств. Основной аппарат, который используется в этой главе, — это
методы геометрии чисел. В разделе 3.1 дается определение хроматического числа пространства с множеством запрещенных расстояний, доказывается простая верхняя оценка хроматического числа Rn с m запрещенными расстояниями, приводятся известные нижние оценки. Формулируется основная теорема.
Теорема 15. Пусть дано нормированное пространство RnK , а A0 = [1, l].
1. Выполнено χ(RnK , A0 ) 6 (2(l + 1) + o(1))n .
2. Пусть p > 2. Тогда χ(Rnp , A0 ) 6 (2cp (l + 1) + o(1))n , cp < 1, cp → 0
при p → ∞.
3. Пусть l > 2. Тогда χ(RnK , A0 ) > (l/2)n .
4. Пусть
n l >o 2. Тогда
p
.
max p, p−1
χ(Rnp , A0 )
n
> (b · l) , где b =
5. Пусть l > 2. Тогда χ(Rn , A0 ) > (b · l)n , где b ≈ 0, 755 ·
√
p0
2
2
√
, а p0 =
2.
В качестве следствий из нее выводится новая верхняя оценка хроматических чисел пространств с произвольной нормой и ее уточнение для
случая пространств с lp -нормой при p > 2.
В разделе 3.2 излагается доказательство теоремы 15. Даются необходимые определения из геометрии чисел. Затем доказывается аналог
теоремы Эрдеша–Роджерса19 .
Теорема 16. Пусть нам дано выпуклое центрально-симметричное тело
K, порождающее норму ||x||K в Rn . Пусть нам также даны решетка
Λ и множество
G
X=
(K + q),
q∈Λ
19
P. Erdős, C.A. Rogers, Covering space with convex bodies, Acta Arithmetica, 7 (1962), 281 - 285.
12
причем копии K, соответствующие разным точкам решетки, не пересекаются. Предположим, что δ(X) = (c + ϕ(n))−n , где c = const > 1,
ϕ(n) → 0 при n → ∞. Пусть
z = n · δ −1 (X) · (ln n + ln ln n + ln c + 1 + ψ(n)).
Тогда найдется такое ψ(n), ψ(n) → 0 при n → ∞, что существует
покрытие пространства z копиями множества X.
Доказательство этой теоремы основано на вероятностном методе. Затем формулируется теорема Минковского–Главки, теорема Элкеша, Одлыжко и Раша об упаковках суперсфер.
Остановимся подробнее на том, как из указанных выше теорем получать верхние оценки хроматического числа n-мерного пространства с
произвольной нормой, задаваемой телом K. Ограничимся случаем одного запрещенного расстояния. Пусть диаметр тела K равен двум. РасF
смотрим решетчатую упаковку X = q∈Λ (K +q) плотности не менее 2−n .
F
Далее, для некоторого > 0 рассмотрим упаковку X 0 = q∈Λ ((1/2 −
)K + q). Среди точек, принадлежащих X 0 , нет пары, отстоящей друг от
друга на расстояние единица. Значит, все точки X 0 мы можем покрасить
в один цвет. Далее, применяя теорему 15, мы покрываем пространство
4
копиями X 0 , при этом нам понадобится не более ( 1−2
+ ō(1))n копий.
Крася каждую копию в свой цвет, мы получаем правильную раскраску
пространства.
Благодарности
Автор очень признателен профессору Андрею Михайловичу Райгородскому и профессору Николаю Германовичу Мощевитину за постановку задач и неоценимую помощь в работе.
Список публикаций по теме диссертации
[1] А.Б. Купавский, О поднятии оценки хроматического числа Rn в
бо́льшую размерность, Доклады Российской Академии Наук, 429
(2009), N3, 305 - 308.
[2] А.Б. Купавский, О раскрасках сфер, вложенных в Rn , Матем. сборник, 202 (2011), N6, 83 - 110.
13
[3] A. Kupavskii, The chromatic number of the space Rn with arbitrary
norm, Discrete Math., 311 (2011), 437 – 440.
[4] А.Б. Купавский, Хроматическое число Rn с множеством запрещенных расстояний, Доклады Российской Академии Наук, 435
(2010), N6, 740 - 743.
[5] А.Б. Купавский, А.М. Райгородский, О разбиении трехмерных
множеств на пять частей меньшего диаметра, Матем. заметки,
87 (2010), N2, 233 - 245. (А.М. Райгородскому принадлежит постановка задачи и редакция текста введения. А.Б. Купавскому принадлежит основной результат (доказательство теоремы 1).)
[6] А.Б. Купавский, А.М. Райгородский, О хроматическом числе R9 ,
Фунд. и прикл. матем., 14 (2008), N5, 139 - 154; Journal of
Mathematical Sciences, 163 (2008), N6, 720 - 731. (А.М. Райгородскому принадлежит постановка задачи и редакция текста введения.
А.Б. Купавскому принадлежит доказательство основных результатов (теорем 1-4).)
14
Документ
Категория
Без категории
Просмотров
6
Размер файла
345 Кб
Теги
сферы, пространство, раскраска, упаковки, многомерная
1/--страниц
Пожаловаться на содержимое документа