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

Московский государственный университет имени М.В.Ломоносова

005051345

На правах рукописи

ИР

Купавский Андрей Борисович

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

01.01.06 — математическая логика, алгебра и теория чисел, 01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

4 АПР 2013

Москва - 2013

005051345

Работа выполнена на кафедре теории чисел Механико-математического факультета Московского государственного университета имени М.В. Ломоносова.

Научные руководители: доктор физико-математических наук,

профессор Райгородский Андрей Михайлович, доктор физико-математических наук, профессор Мощевитин Николай Германович

Официальные оппоненты: Быковский Виктор Алексеевич

член-корреспондент РАН Хабаровское отделение ФГБУН ИПМ ДВО РАН, директор института

Кабатянский Григорий Анатольевич доктор физико-математических наук ФГБУН Институт проблем передачи информации имени A.A. Харкевича РАН, главный научный сотрудник

Ведущая организация: ФГБОУ "Ярославский государственный

университет имени П.Г. Демидова"

Защита диссертации состоится 26 апреля 2013 года в 16 часов 45 минут на заседании диссертационного совета Д 501.001.84 при МГУ имени М.В. Ломоносова по адресу: РФ, 119991, Москва, ГСП-1, Ленинские горы, д.1, МГУ, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М.В. Ломоносова (Ломоносовский проспект, 27, сектор А, 8-й этаж).

Автореферат разослан 26 марта 2013 г.

Ученый секретарь диссертационного совета Д 501.001.84 при МГУ, доктор физико-математических наук,

профессор Иванов Александр Олегович

Общая характеристика работы

Актуальность работы

Комбинаторная геометрия - очень активно развивающаяся область на стыке дискретной математики и геометрии чисел. Изначальный интерес к этой области возник, в частности, благодаря работам Борсука1 и Эрдеша2. В этих работах были сформулированы задача о разбиении тел на части меньшего диаметра, задача о максимальном числе инциден-ций между точками и прямыми на плоскости, задача о числе различных и одинаковых расстояний между п точками на плоскости. Чуть позже, в 1950 году, Нелсоном была поставлена задача о хроматическом числе плоскости, которая вскоре была обобщена на случай произвольной размерности. Эти проблемы тесно связаны между собой и стали центральными в комбинаторной геометрии. За последние годы было опубликовано множество статей по этой тематике. Одними из наиболее важных являются статья Кана и Калаи3, в которой они опровергают гипотезу Борсука о том, что любое тело в R" диаметра единица можно разбить на п + 1 часть строго меньшего диаметра, и статья Гута и Каца4, в которой они доказывают гипотезу Эрдеша о том, что между п точками на плоскости должно быть по крайней мере п1-0'1) различных расстояний.

Значительным прорывом в задаче о хроматическом числе пространства стал результат Франкла и Вилсона5, которые с помощью линейно-алгебраического метода показали, что хроматическое число пространства растет экспоненциально с ростом размерности. После этого асимптотическая нижняя оценка хроматического числа пространства была уточнена Райгородским6 за счет рассмотрения более общей конструкции. С другой стороны, за последние 20 лет было получено очень много нижних оценок хроматических чисел пространств малых размерностей. По ви-

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

2P. Erd6s, On a set of distances of n points, Amer. Math. Monthly, 53 (1946), 248 - 250.

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

4L. Guth, N.H. Katz, On the Erdâs distinct distance problem on the plane, 2010, arXiv:1011.4105.

5P. Firankl, R. Wilson, Intersection theorems with geometric consequences, Combinatorica, 1 (1981), 357 - 368.

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

димому, наиболее интересен результат Нечуштана7, который с помощью сложной геометрической конструкции доказал, что хроматическое число пространства не меньше шести. Кроме него различные оценки получали Кантвелл, Райгородский, Цибулька. В диссертации за счет сочетания геометрических соображений и линейно-алгебраического метода получается доказать ряд нижних оценок хроматических чисел пространств, уточняющих ранее известные.

Хроматические числа изучались не только для евклидовых пространств. Определение хроматического числа для произвольного метрического пространства было дано в работе Бенды и Перлеса8. Много работ посвящено хроматическому числу пространства Q" с евклидовой метрикой (работы Бенды и Перлеса, Райгородского, Цибульки, Чилакамари и др.) и хроматическому числу сфер (работы Ловаса, Райгородского, Симмонса). В диссертации мы вводим определение пестроты пространства, которое, с одной стороны, обобщает определение хроматического числа, данное Бендой и Перлесом, а с другой стороны, позволяет поставить в более общий контекст работы Нечуштана, Цибульки и др., в которых получены нижние оценки хроматических чисел пространств малых размерностей. В диссертации автором разработан подход, позволяющий поднимать нижние оценки хроматического числа в ббльшие размерности. При этом ключевую роль здесь играют раскраски сфер.

В последние годы в задаче о хроматическом числе пространства находят применение методы геометрии чисел. Все верхние оценки хроматических чисел пространств в малых размерностях получаются за счет рассмотрения покрасок, основанных на решетках (см. работу Радоичича и Тота9). Так, например, известный результат о том, что хроматическое число плоскости не превосходит семи, получается на основе гексагональной решетки. Плоскость замощается шестиугольниками диаметра чуть меньше единицы, после чего каждый шестиугольник красится в один цвет таким образом, чтобы расстояние между соседними шестиугольниками одного цвета было больше единицы.

70. Nechushtan, On the space chromatic number, Discrete Math., 256 (2002), 499 - 507.

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

&R. RadoiÊié, G. T<5th, 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.

То, что методы геометрии чисел можно применить к получению асимптотических верхних оценок хроматических чисел, было замечено Ларманом и Роджерсом10. В своей работе они доказали асимптотическую верхнюю оценку хроматического числа пространства с евклидовой нормой. Недавно Канг и Фюреди11 смогли получить асимптотическую верхнюю оценку хроматического числа пространства с произвольной нормой. В диссертации доказаны оценки, существенно уточняющие и обобщающие результат Канг и Фюреди. Для этого используются различные теоремы геометрии чисел и смежных областей: классическая теорема Минковского-Главки и ее уточнения Шмидтом12, граница Кабатянского-Левенштейна13, результаты Элкеша, Одлыжко и Раша14 касательно упаковок суперсфер. Кроме того, доказывается аналог теоремы Эрдеша-Роджерса15.

Как уже говорилось выше, одним из важнейших событий в комбинаторной геометрии последних десятилетий стало опровержение гипотезы Борсука. Сам контрпример был получен в размерности 2015 на основе линейно-алгебраического метода. После 1993 года, в котором вышла статья Кана и Калаи, появилось множество статей, в которых авторы понижали размерность контрпримера. Нилли, Грэй и Вайсбах, Райгородский, Вайсбах, Хинрихс, и, наконец, Хинрихс и Рихтер16 довели минимальную размерность контрпримера до 298. С другой стороны, известно, что гипотеза Борсука верна в размерностях п ^ 3, и естественным образом возникла следующая задача. Пусть мы разбиваем (двумерное или трехмерное) множество диаметра единица на фиксированное число частей меньшего диаметра. Насколько маленького диаметра можно получить части? В этом направлении получали результаты Лассак17, Макеев, Хеп-

WD.G. barman, С.А. Rogers, The realization of distances within sets in Euclidean space, Mathematik», 19 (1972), 1 - 24.

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

12W.M. Schmidt, On Ihe Minkowski-Hlawka theorem, Illinois J. Math., 7 (1963), 18 - 23.

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

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

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

I6A. Hinrichs, C. Richter, New sets with large Borsvk numbers, Discrete Math., 270 (2003), 137 - 147.

17M. Lassak, An estimate concerning Borsuk's partition problem, Bull. Acad. Polon. Sei. Ser. Math.,

пеш, Филимонов и др. В диссертационной работе мы уточняем результат Лассака для описанной выше задачи о разбиении трехмерных тел на пять частей меньшего диаметра. Наш подход основан на технике универсальных покрывающих систем. Этот подход, в частности, был использован Хеппешем при доказательстве гипотезы Борсука в К3.

Цель работы состоит в решении следующих задач: установить новые нижние и верхние оценки хроматических чисел пространств, ввести и изучить понятие пестроты сфер, разработать общий метод поднятия нижних оценок хроматического числа в ббльшие размерности, получить новую верхнюю оценку диаметра частей в задаче о разбиении трехмерных тел на пять частей как можно меньшего диаметра.

Научная новизна

Все результаты диссертации являются новыми. Перечислим основные из них:

1. Доказаны новые нижние оценки хроматических чисел пространств в размерностях 9-12. Точнее, получены оценки х0&9) ^ 21, х0&10) ^ 23, Х(КИ) > 25, Х(К12) > 27.

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

3. Доказано, что любое трехмерное множество диаметра единица можно разбить на пять частей, диаметр каждой из которых не превосходит величины 0.9425.

4. Доказано, что хроматическое число пространства К" с произвольной нормой не превосходит величины (4 4- о(1))п, получены уточнения этого результата в случае пространств с ^-нормой, где р ^ 2.

30 (1982), 449 - 451.

Основные методы исследования

В работе используются линейно-алгебраический метод, разнообразные методы комбинаторной геометрии, методы геометрии чисел, методы теории графов, вероятностный метод.

Теоретическая и практическая ценность

Диссертация имеет теоретический характер. Полученные в диссертации результаты представляют интерес для специалистов по комбинаторной геометрии, геометрии чисел и дискретной математике. Апробация работы

Результаты диссертации докладывались на следующих научно-исследовательских семинарах:

— Московский семинар по теории чисел под руководством член-корр. РАН, профессора Ю.В. Нестеренко и профессора Н.Г. Мощевитина (мех-мат МГУ, 2012 г.).

— Семинар "Вероятностные и алгебраические методы в комбинаторике" под руководством профессора A.M. Райгородского (мехмат МГУ, 2007-2012 гг., неоднократно).

— Семинар "Тригонометрические суммы и их приложения" под руководством профессора Н.Г. Мощевитина (мехмат МГУ, 2010г.).

— Семинар "Узлы и теория представлений" под руководством профессора В.О. Мантурова, ассистента Д.П. Ильютко и ассистента И.М. Никонова (мехмат МГУ, 2011 г.).

-- Семинар "Дискретный анализ" под руководством профессора A.A. Сапоженко (ВМиК МГУ, 2011 г.).

— Семинар по теории кодирования под руководством д.ф.-м.н. JI.A. Бассалыго (ИППИ РАН, 2011 г.).

— Научно-исследовательский семинар по математической логике под руководством акад. РАН, профессора С.И. Адяна и член-корр. РАН, профессора Л.Д. Беклемишева (мехмат МГУ, 2012 г.).

— Кафедральный семинар кафедры дискретной математики под руководством профессора A.M. Райгородского (ФИВТ МФТИ, 20102012 гг.).

— Семинар под руководством проф. П. Тетали (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 Сентября 001.2 г.).

Работа автора поддержана грантом РФФИ 09-01-00294, грантом РФФИ 12-01-00683 и грантом Президента МД-8390.2010.1.

Публикации

Результаты диссертации опубликованы в 6 работах автора (все они входят в перечень ВАК), список которых приведен в конце автореферата [1-6].

Структура диссертации

Диссертация состоит из введения, трех глав и списка литературы, насчитывающего 70 наименований. Общий объем диссертации составляет 88 страниц.

Краткое содержание диссертации

Во введении к диссертации излагается история задачи о хроматическом числе, история проблемы Борсука, а также история задачи о поиске плотнейшей упаковки шаров и других задач геометрии чисел, близких к теме диссертации. Вводятся определения хроматического числа пространства, числа Борсука, величин с^, упаковки шаров, верхней плотности множества. Напомним, что хроматическим числом п-мерного пространства называется величина

X(R") = min jm : К" = [J Vu Vi = 1,..., m V®, у € Vt

Величины определяются следующим образом:

d^ = sup inf { x : ЗФЬ.. . ,Фт : Ф = I 1ф„ Vi diam1^ ^ x I .

ФсШп,<ЦатФ=1 [ J

Содержание главы 1

Глава 1 посвящена вопросам, связанным с хроматическими числами пространств малых размерностей, поднятием оценок в бблыпую размерность и пестротой. В разделе 1.1 дается определение хроматического числа для произвольного метрического пространства через функции правильной раскраски. Приводится ряд результатов касательно верхних и нижних оценок хроматического числа в пространствах малых размерностей.

В разделе 1.2 излагается доказательство оценки х(®-9) ^ 21. В параграфе 1.2.1 вводится ключевое определение дистанционного графа: наг зовем Н = (У,Е) дистанционным графом в М", если множество его вершин V — это подмножество К", а множество его ребер состоит из пар вершин, отстоящих друг от друга на расстояние а > 0, где а — это некоторое фиксированное число. Дается определение числа а(Н) независимости графа Н. Выполняются следующие оценки: х(Н) ^ для любого дистанционного графа Я, х{Н) ^ \У\/а{Н) для любого графа. В этом же параграфе определен граф Є, на основе которого получена оценка хроматического числа М9: Є = (V, Е),

V = {и = (иь..., ую),уі Є {0,1}, V! + ... + у10 = 5},

Е = {{и, и} Є V х V, (и, у) = щуі + ... + гію^іо = 3}.

Сформулирована теорема о числе независимости рассматриваемого графа, которая говорит, что а (С) = 12. Из нее следует нижняя оценка хроматического числа графа <3, а, значит, и хроматического числа К9. Кроме того, из оценки х(К9) ^ 21 выводится оценка х(®10) ^ 23.

В параграфе 1.2.2 дано доказательство теоремы о числе независимости рассматриваемого графа. Сначала приводится пример независимого множества размера 12 в графе Затем с помощью линейно-алгебраического метода доказывается лемма 1.

Лемма 1. В любом максимальном независимом множестве \¥ векторов из Є обязательно найдутся два вектора со скалярным произведением единица.

Далее предлагается удобный способ анализа возможных независимых множеств графа (3, который учитывает симметрии графа. Дальнейшие рассуждения основаны на переборе случаев. В параграфе 1.2.3 с помощью многократного применения принципа Дирихле доказывается оценка х(С) ^ 63.

В разделе 1.3 идет речь о поднятии нижних оценок хроматического числа из размерности п в размерность п + 2. Установлена следующая теорема.

Теорема 5. Пусть тг ^ 2, а Є - дистанционный граф с ребрами единичной длины, вершины которого расположена на сфере 5Га С К",

^ т. Пусть при этом радиус г„ сферы удовлетворяет условиям

'."Л-

Тогда х(Кп+2) >т + 4.

Из этой теоремы получается оценка ^ 25. В параграфе 1.3.1

приводятся три вспомогательных леммы, среди которых можно отметить лемму 3.

Лемма 3. В любой правильной раскраске пространства для любых г > О, п > 2 найдутся точки А, В £ Е", такие, что \АВ\ = г и цвет точки А отличен от цвета точки В.

В параграфе 1.3.2 завершается доказательство теоремы 5. Все доказательство основано на геометрических соображениях.

В разделе 1.4 теорема 5 помещена в более общий контекст. Вводится ключевое новое понятие пестроты множества относительно пространства.

Пусть (Г, р) - метрическое пространство, {/ С Г, ри - метрика, индуцированная на и метрикой р. Пестрота 7г(С/|(Г, р)) множества V относительно пространства (Г, р) — это

7г(Г/|(Г,р)) = тттахде(£/)),

г и

где О - произвольное преобразование пространства, сохраняющее метрику, ^ - правильная раскраска пространства, а х'{0(и)) - это количество цветов, затраченное на покраску множества О(11) при данной раскраске. В дальнейшем изучается пестрота сфер 7г"(5™) = 7г(^г*|К"). В параграфе 1.4.1 изучается пестрота окружностей. Сформулирована и доказана теорема 6, в которой в зависимости от радиуса и размерности пространства получены нижние оценки пестроты окружностей. Установлно следующее утверждение.

Утверждение 1. Для почти всех радиусов выполнено неравенство

Х(5г1)<тг2(5г1).

Сформулированы теорема Ловаса о хроматическом числе сфер и некоторые вспомогательные утверждения касательно пестроты симплексов и

сфер. Далее приводится доказательство теоремы б, основанное на геометрических соображениях.

Проведем связь между пестротой сферы и поднятием нижних оценок хроматических чисел пространств в большие размерности. Пусть граф Є — дистанционный в К", х(С) ^ т, и его вершины лежат на сфере радиуса г < 1. Пусть ттп+к{Б^Г1) ^ х, где г' = \/1 - г2. Покажем, что ^ х 4- то. Действительно, зафиксируем правильную раскраску Выберем сферу 5*-1, покрашенную в ^ х цветов (такая существует по определению пестроты). После этого на сферу радиуса г, ортогональную данной, положим граф Цвета, в которые покрашен граф б, должны быть отличны от цветов сферы

В параграфе 1.4.2 изучается пестрота двумерных сфер. Получен ряд результатов, обобщающих теорему 6. Как следствие, доказано, что Х(М12) ^ 27 и передоказана оценка х(®4) > 7. В параграфе 1.4.3 результаты теорем 6-9 обобщаются на многомерный случай. Основной результат дан в теореме 10, которая говорит, что при некоторых ограничениях на радиус и при п ^ 7 имеем 7г2"(5"-1) > 2п. Еще одним способом передоказана оценка х(®4) ^ 7. В пункте "основная конструкция" описана общая схема построения дистанционных графов, на основе которых получаются оценки, в следующем пункте эта схема анализируется в разных случаях, соответствующих теоремам 10-12. В пункте "возможные дальнейшие результаты" рассказаны возможные пути обобщения теорем 10-12, а также приводится довольно интересный частный случай таких обобщений.

Теорема 13. Имеем 7Г3(£2) ^ 5 при Содержание главы 2

Глава 2 посвящена разбиениям трехмерных тел на пять частей как можно меньшего диаметра. Даны определения величин с%(Ф), <Щ. Проведена связь между этими величинами и проблемой Борсука, сформулирована основная теорема о том, что й3 ^ 0.9425. В разделе 2.1 даются ключевые определения: множество II называется универсальной покрышкой

в R", если

V Ф С М", diain Ф = 1, 3 О, 0(U) 2 Ф, где О - некоторое движение пространства; система множеств Ы называется универсальной покрывающей системой (УПС) в Rn, если

УФсГ, diam Ф = 1, 3 U еЫ, 3 О, 0(U) 2 Ф,

где О - снова некоторое движение пространства. Верен следующий факт: пусть дана УПС U, тогда выполнено неравенство

djJ<BUPd¡5(U).

UeU

Кроме того, в этом разделе описана универсальная покрышка, которую использовал Лассак18.

В разделе 2.2 производится построение УПС, на которой основано доказательство. Остановимся поподробнее на построении. За основу берется шар радиуса d, не превосходящего радиуса шара Юнга. Далее, описанный шар пересекается с двумя шарами радиуса единица с центрами в некоторых граничных точках первого шара. Множества в полученной УПС зависят от двух параметров: от радиуса первого шара и от положения центра третьего шара относительно центра второго. В лемме 6 доказывается, что полученная система действительно является УПС.

В разделе 2.3 строится разбиение множеств из УПС на пять частей меньшего диаметра. Множества разбиваются плоскостями, параллельными координатным плоскостям. Границы частей, таким образом, состоят из кусков плоскостей и кусков сфер. Разбиения параметризуются двумя параметрами.

В разделе 2.4 находятся диаметры частей разбиения при условии, что радиус d был больше 0.592. В параграфе 2.4.1 строится разбиение границ частей множеств из УПС на двумерные, одномерные и нульмерные составляющие. В последующих параграфах доказывается, что диаметр каждой из частей разбиения каждого из множеств, лежащих в УПС, достигается на парах точек, принадлежащих нульмерным составляющим границ, и находится диаметр каждой из частей. В параграфе 2.4.6 выбираются параметры разбиения и доказывается основная теорема в случае

18М. Lassak, An estímate concerning Borsúk's partition problem, Bull. Acad. Polon. Sei, Set. Math., 30 (1982), 449 - 451.

d ^ 0.592. В разделе 2.5 рассматривается случай d < 0.592. Здесь нам достаточно разбиения, аналогичного тому, которое использовал в своей работе Лассак.

Содержание главы 3

Глава 3 посвящена верхним оценкам хроматических чисел пространств. Основной аппарат, который используется в этой главе, — это методы геометрии чисел. В разделе 3.1 дается определение хроматического числа пространства с множеством запрещенных расстояний, доказывается простая верхняя оценка хроматического числа Мп с т запрещенными расстояниями, приводятся известные нижние оценки. Формулируется основная теорема.

Теорема 15. Пусть дано нормированное пространство Ж^-, а А' — [1,/].

1. Выполнено Л') < (2(1 + 1) + о(1))п.

2. Пусть р > 2. Тогда А') < (2^(1 + 1) + о(1))п,с„ < 1,Ср 0 при р —» оо.

3. Пусть I > 2. Тогда х(Щ,А') > (Ч2)"-

4. Пусть I > 2. Тогда х(К£,Л') ^ (Ь ■ 1)п, где Ь = а р' = max

5. Пусть I ^ 2. Тогда x(R", А!) ^ (Ъ ■ 1)п, где Ъ w 0,755 • у/2.

В качестве следствий из нее выводится новая верхняя оценка хроматических чисел пространств с произвольной нормой и ее уточнение для случая пространств с /^-нормой при р > 2.

В разделе 3.2 излагается доказательство теоремы 15. Даются необходимые определения из геометрии чисел. Затем доказывается аналог теоремы Эрдеша-Роджерса19.

Теорема 16. Пусть нам дано выпуклое центрально-симм-ртр-анное тело К, порождающее норму ||х||к- в Rn. Пусть нам также даны решетка А и множество

Х=\_\(K + q),

деЛ

1SP. Erd6s, С.A. Rogers, Covering space with convex bodies, Acta Arithmetics, 7 (1962), 281 - 285.

причем копии К, соответствующие разным точкам решетки, не пересекаются. Предположим, что б(Х) = (с + <р(п))~п, где с = const > 1, tp(n) —)• 0 при п -¥ оо. Пусть

z = n-S~1(X) ■ (lnn + lnlnn + lnc+ 1 + ф(п)).

Тогда найдется такое ij){n), i>{n) —>■ 0 при п —> оо, что существует покрытие пространства z копиями множества X.

Доказательство этой теоремы основано на вероятностном методе. Затем формулируется теорема Минковского-Главки, теорема Элкеша, Од-лыжко и Раша об упаковках суперсфер.

Остановимся подробнее на том, как из указанных выше теорем получать верхние оценки хроматического числа n-мерного пространства с произвольной нормой, задаваемой телом К. Ограничимся случаем одного запрещенного расстояния. Пусть диаметр тела К равен двум. Рассмотрим решетчатую упаковку X = плотности не менее 2~". Далее, для некоторого е > 0 рассмотрим упаковку X' — |_|9еЛ((1/2 — е)К + q). Среди точек, принадлежащих X', нет пары, отстоящей друг от друга на расстояние единица. Значит, все точки X' мы можем покрасить в один цвет. Далее, применяя теорему 15, мы покрываем пространство копиями X', при этом нам понадобится не более (jz^ + 5(1))" копий. Крася каждую копию в свой цвет, мы получаем правильную раскраску пространства.

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

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

Список публикаций по теме диссертации

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

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

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

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

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

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

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж (С О экз. Заказ № IЯ

Московский государственный университет им. М.В.Ломоносова механико-математический факультет

04201357130 пРавах рукописи

Купавский Андрей Борисович УПАКОВКИ И РАСКРАСКИ СФЕР В МНОГОМЕРНЫХ ПРОСТРАНСТВАХ

01.01.06 — математическая логика, алгебра и теория чисел, 01.01.09 — дискретная математика и математическая кибернетика

Диссертация на соискание ученой степени кандидата физико-математических наук

Научные руководители — д.ф.-м.н. Н.Г. Мощевитин, д.ф.-м.н. A.M. Райгородский

Москва, 2013

Оглавление

Введение 4

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

размерности 8

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Введение

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

Задача о хроматическом числе пространства — это одна из классических задач комбинаторной геометрии (см. [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]) получены новые верхние оценки хроматического числа пространства Еп с некоторой нормой, а также новые верхние и нижние оценки хроматического числа пространства с отрезком запрещенных расстояний. Основной аппарат, который используется в доказательствах, — это теория упаковок.

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

Глава 1

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

В этой главе мы получаем различные результаты касательно раскрасок сфер и пространств малой размерности. Мы доказываем новые оценки хроматического числа в пространствах размерностей 9-12, устанавливаем общие результаты о поднятии оценок хроматического числа в большую размерность. Мы вводим новое понятие пестроты пространства, которое используем для получения некоторых из вышеперечисленных результатов. Основными теоремами главы являются теоремы 1, 5, 6, 8 - 12.

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

В 1950 году Хадвигер и Нелсон поставили вопрос о нахождении хроматического числа плоскости: в какое минимальное количество цветов можно так покрасить плоскость, чтобы любые две точки на расстоянии единица друг от друга были покрашены в разные цвета?

Поставим задачу более общо. Пусть (Г, р) - это метрическое пространство (пара пространство - метрика). Определим функции правильной раскраски метрического пространства

F = Fm{x): Г Л {1,..., т}, (F(x0) = F(x)) р(х, х0) ф 1

и хроматическое число пространства

х((Г,р)) = min{m £ N : 3Fm}.

Для хроматического числа пространства Rn с евклидовой метрикой введем более короткое обозначение Вообще, если Г с М"' и метрика на Г евклидова, то мы будем писать х(Г) вместо х((Г,р)). Заметим, что вышеописанное определение отличается от того определения, которое мы давали

во введении, однако, в этой главе нам удобно использовать именно его.

Даже задача о нахождении хроматического числа плоскости, возникшая первой, не решена до сих пор. Имеются простые оценки 4 < х(1&2) < 7, и все попытки улучшить их оказывались тщетными. С другой стороны, за почти 60 лет с момента постановки задачи было получено множество результатов (см. [16], [18], [19], [26], [34], [62]). Имеется большое число работ, посвященных хроматическому числу с дополнительным ограничением на каждый цвет (в частности, когда множество точек каждого цвета является измеримым множеством, или является объединением многогранников (см. [26], [62])). Хроматическое число изучалось для пространств с неевклидовой метрикой (см. [19]).

Известны оценки хроматического числа пространства <0)п с евклидовой метрикой при п < 7 (см. [16], [36]). В частности,

Х(02) = 2 ([64]), = 2 ([48]), Х(04) - 4 ([31]).

Известны оценки хроматического числа сферы 5"2 с евклидовой метрикой в зависимости от радиуса (см. [60], [61]).

Известны следующие асимптотические оценки хроматического числа (нижняя оценка была получена в работе [21], верхняя — в работе [50]):

(1,239 +о(1))п <Х(Кя)<(3 + о(1))п.

Из этих оценок видно, что с ростом п величина х(^п) растет экспоненциально. Показан экспоненциальный рост для хроматического числа Мп с любой 1р-метрикой (см. [15], а также главу 3).

При п — 3,4 имеют место оценки

6<х(М3)<15([56],[57]), 7<х(М4)<54([35],[57]).

Известные верхние оценки хроматического числа Мп при п > 4 носят тривиальный характер. Что касается оценок снизу, долгое время лучшие оценки в большинстве малых размерностей давали конструкции из работы [50], и лишь в последнее время многие из них были уточнены. Приведем таблицу оценок снизу для х(^п) ПРИ п < \2 со ссылками на работы, в которых они были получены:

п = 1 2 3 4 5 6

х(мп) > 2 4[55] 6, [56] 7, [35], [6] 9, [35] П, [36]

п - 7 8 9 10 11 12

х(1Г) > 15, [16] 16, [50] 16, [50] 19, [50] 20, [16] 24, [50]

Заметим, что составить данную таблицу, несмотря на изобилие книг и обзоров, оказалось отнюдь не просто. Подобные таблицы есть и в [34], и в [62]. Однако они содержат неточности и даже грубые ошибки. Именно поэтому мы по каждой оценке, кроме тривиальной одномерной, даем ссылку на ту работу, в которой она получена.

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

Основной результат этого раздела — это новая оценка снизу величины х(^9) (см. также [70]). Как следствие, мы получим оценку снизу величины х(^10)-Итак, справедлива

Теорема 1. Выполнена оценка х(^9) >21.

Заметим, что появлению этого результата во многом поспособствовали компьютерные расчеты из работы [4]. В следующем параграфе мы несколько разъясним суть доказательства теоремы 1 и перенесем результат этой теоремы в размерность 10.

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

Пусть дан граф С = (V, Е). Мы будем говорить, что С — дистанционный граф в если множество вершин V — это подмножество Мп, а множество ребер состоит из пар вершин, отстоящих друг от друга на расстояние а > 0, где а — это некоторое фиксированное число. Из определения дистанционного графа вытекает, что, если С — дистанционный в Мп, то х(^) < где х(С) — хроматическое число графа С, т.е. минимальное количество цветов, в которые можно так покрасить вершины чтобы любые две смежные вершины были разных цветов. Все известные оценки снизу хроматического числа получаются именно таким образом. Для получения оценки, заявленной в теореме 1, мы рассмотрим следующий граф: С = (У^Е),

V = {у = (уи ..., vw),vi е {0,1}, «1 + ... + Ую = 5},

Е = {{и, у} еУ XV, (и, г») = ■и1г>1 + ... + щ0у 10 = 3}.

Иными словами, элементы V - это векторы с координатами из {0,1}, у которых пять единиц, ребрами соединены пары векторов со скалярным произведением 3 (далее, допуская вольность речи, часто будем называть вершины этого графа векторами). Подобные графы встречаются при применении линейно-алгебраического метода, а также в теории кодирования (см. [11], [19], [29]). Как несложно понять, у этого графа будет С]>0 = 252 вершин.

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

Теорема 2. Для описанного выше графа а(6?) = 12.

Эту теорему мы докажем в параграфе 1.2.2, а сейчас заметим, что, в действительности, теорема 1 сразу же следует из теоремы 2. Поясним этот момент. Во-первых, х(С) > |К|/а(С) = 252/12 = 21. Во-вторых, граф С является дистанционным в гиперплоскости Н = {х1 + ... + хю = 5} С М10, Н ~ К , и, следовательно, х(М9) > х(С?) > 21. Теорема 2 доказана.

Более того, граф С лежит на сфере в гиперплоскости Н, поэтому у нас есть некоторый запас прочности. Это позволит нам доказать следующий результат.

Теорема 3. Выполнена оценка х(®^10) > 23.

Доказательство. Векторы из V лежат на гиперплоскости Н = {х\ + ... + — 5} и на сфере 5 = {х\ + ... + = 5}, значит, и на 9-мерной сфере 5" = Б Г) Н. Вычислим радиус г' этой сферы. Радиус г сферы $ равен л/б. Расстояние р от центра до Н достигается на точке а = (1/2,..., 1/2), откуда р — \а\ = \/5/2. Получаем г' = \]г1 — р2 = \Jbj2. Таким образом, г' < 2, значит, в М10 есть две точки Р\,Р2, находящиеся на расстоянии 2 от каждой из точек 5'. Повернем 5' и точку р2 относительно точки р\ так, чтобы |р3 — = 2, где - образ точки при повороте. При этом сфера 5" перейдет в в". Рассмотрим граф С\ = (У\. Е\), вершинами которого являются вершины (?, их образы при повороте и точки р\. р2, Рз, а ребрами соединены вершины, лежащие на расстоянии 2 друг от друга. Покажем, что ^ 23.

Обозначим образ графа (9 при повороте за С. Допустим, х(^т) < 22. Занумеруем цвета раскраски числами 1,... ,22. Пусть р\ покрашена в цвет 1. Тогда и (7, и С покрашены в цвета 2,... ,22, т.к. р\ соединена со всеми вершинами из С

и С, причем все цвета присутствуют в силу того, что — 21, > 21.

Значит, ир2, и р3 должны быть покрашены в цвет 1. Но р2 и рз соединены ребром. Противоречие. Следовательно, х^х) > 23. При этом граф Сх реализован в М10 как дистанционный, таким образом, х0&10) > х(Ст) > 23. □

Отметим, что конструкция, использованная нами при доказательстве теоремы, известна как "обобщенное мозеровское веретено" (см. [55]). Разделы 1.3, 1.4 будут посвящены дальнейшему обобщению конструкции Мозера.

1.2.2 Доказательство теоремы 2 Оценка а(<7) > 12

Несложно показать, что а(С) > 12. Приведем пример двенадцати векторов из V, попарные скалярные произведения которых не равны 3 (векторам отвечают строки таблицы):

1 1 1 1 1 0 0 0 0 0 0 0 0 0 1 1 1 1 1 0 11110

С}

С}

0 111