Введение к работе
Актуальность работы
Комбинаторная геометрия - очень активно развивающаяся область на стыке дискретной математики и геометрии чисел. Изначальный интерес к этой области возник, в частности, благодаря работам Борсукаи Эрдеша. В этих работах были сформулированы задача о разбиении тел на части меньшего диаметра, задача о максимальном числе инциден- ций между точками и прямыми на плоскости, задача о числе различных и одинаковых расстояний между n точками на плоскости. Чуть позже, в 1950 году, Нелсоном была поставлена задача о хроматическом числе плоскости, которая вскоре была обобщена на случай произвольной размерности. Эти проблемы тесно связаны между собой и стали центральными в комбинаторной геометрии. За последние годы было опубликовано множество статей по этой тематике. Одними из наиболее важных являются статья Кана и Калаи, в которой они опровергают гипотезу Борсука о том, что любое тело в Rn диаметра единица можно разбить на n + 1 часть строго меньшего диаметра, и статья Гута и Каца, в которой они доказывают гипотезу Эрдеша о том, что между n точками на плоскости должно быть по крайней мере n1-o(1) различных расстояний.
Значительным прорывом в задаче о хроматическом числе пространства стал результат Франкла и Вилсона, которые с помощью линейно- алгебраического метода показали, что хроматическое число пространства растет экспоненциально с ростом размерности. После этого асимптотическая нижняя оценка хроматического числа пространства была уточнена Райгородским за счет рассмотрения более общей конструкции. С другой стороны, за последние 20 лет было получено очень много нижних оценок хроматических чисел пространств малых размерностей. По видимому, наиболее интересен результат Нечуштана, который с помощью сложной геометрической конструкции доказал, что хроматическое число пространства не меньше шести. Кроме него различные оценки получали Кантвелл, Райгородский, Цибулька. В диссертации за счет сочетания геометрических соображений и линейно-алгебраического метода получается доказать ряд нижних оценок хроматических чисел пространств, уточняющих ранее известные.
Хроматические числа изучались не только для евклидовых пространств. Определение хроматического числа для произвольного метрического пространства было дано в работе Бенды и Перлеса. Много работ посвящено хроматическому числу пространства qn с евклидовой метрикой (работы Бенды и Перлеса, Райгородского, Цибульки, Чилакамари и др.) и хроматическому числу сфер (работы Ловаса, Райгородского, Симмонса). В диссертации мы вводим определение пестроты пространства, которое, с одной стороны, обобщает определение хроматического числа, данное Бендой и Перлесом, а с другой стороны, позволяет поставить в более общий контекст работы Нечуштана, Цибульки и др., в которых получены нижние оценки хроматических чисел пространств малых размерностей. В диссертации автором разработан подход, позволяющий поднимать нижние оценки хроматического числа в большие размерности. При этом ключевую роль здесь играют раскраски сфер.
В последние годы в задаче о хроматическом числе пространства находят применение методы геометрии чисел. Все верхние оценки хроматических чисел пространств в малых размерностях получаются за счет рассмотрения покрасок, основанных на решетках (см. работу Радоичича и Тота). Так, например, известный результат о том, что хроматическое число плоскости не превосходит семи, получается на основе гексагональной решетки. Плоскость замощается шестиугольниками диаметра чуть меньше единицы, после чего каждый шестиугольник красится в один цвет таким образом, чтобы расстояние между соседними шестиугольниками одного цвета было больше единицы.
То, что методы геометрии чисел можно применить к получению асимптотических верхних оценок хроматических чисел, было замечено Ларманом и Роджерсом. В своей работе они доказали асимптотическую верхнюю оценку хроматического числа пространства с евклидовой нормой. Недавно Канг и Фюреди смогли получить асимптотическую верхнюю оценку хроматического числа пространства с произвольной нормой. В диссертации доказаны оценки, существенно уточняющие и обобщающие результат Канг и Фюреди. Для этого используются различные теоремы геометрии чисел и смежных областей: классическая теорема Минковского-Главки и ее уточнения Шмидтом, граница Кабатянского-Левенштейна, результаты Элкеша, Одлыжко и Рашакасательно упаковок суперсфер. Кроме того, доказывается аналог теоремы Эрдеша-Роджерса.
Как уже говорилось выше, одним из важнейших событий в комбинаторной геометрии последних десятилетий стало опровержение гипотезы Борсука. Сам контрпример был получен в размерности 2015 на основе линейно-алгебраического метода. После 1993 года, в котором вышла статья Кана и Калаи, появилось множество статей, в которых авторы понижали размерность контрпримера. Нилли, Грэй и Вайсбах, Райгородский, Вайсбах, Хинрихс, и, наконец, Хинрихс и Рихтер довели минимальную размерность контрпримера до 298. С другой стороны, известно, что гипотеза Борсука верна в размерностях n ^ 3, и естественным образом возникла следующая задача. Пусть мы разбиваем (двумерное или трехмерное) множество диаметра единица на фиксированное число частей меньшего диаметра. Насколько маленького диаметра можно получить части? В этом направлении получали результаты Лассак, Макеев, Хеп- пеш, Филимонов и др. В диссертационной работе мы уточняем результат Лассака для описанной выше задачи о разбиении трехмерных тел на пять частей меньшего диаметра. Наш подход основан на технике универсальных покрывающих систем. Этот подход, в частности, был использован Хеппешем при доказательстве гипотезы Борсука в r3.
Цель работы состоит в решении следующих задач: установить новые нижние и верхние оценки хроматических чисел пространств, ввести и изучить понятие пестроты сфер, разработать общий метод поднятия нижних оценок хроматического числа в большие размерности, получить новую верхнюю оценку диаметра частей в задаче о разбиении трехмерных тел на пять частей как можно меньшего диаметра.
Научная новизна
Все результаты диссертации являются новыми. Перечислим основные из них:
-
Доказаны новые нижние оценки хроматических чисел пространств в размерностях 9-12. Точнее, получены оценки x(r9) ^ 21, x(r10) ^ 23, x(rn) ^ 25, x(r12) ^ 27.
-
Разработан общий метод поднятия нижних оценок хроматического числа пространства в большие размерности.
-
Доказано, что любое трехмерное множество диаметра единица можно разбить на пять частей, диаметр каждой из которых не превосходит величины 0.9425.
-
Доказано, что хроматическое число пространства rn с произвольной нормой не превосходит величины (4 + o(1))n, получены уточнения этого результата в случае пространств с /,-нормой, где p ^ 2.
Основные методы исследования
В работе используются линейно-алгебраический метод, разнообразные методы комбинаторной геометрии, методы геометрии чисел, методы теории графов, вероятностный метод.
Теоретическая и практическая ценность
Диссертация имеет теоретический характер. Полученные в диссертации результаты представляют интерес для специалистов по комбинаторной геометрии, геометрии чисел и дискретной математике.
Апробация работы
Результаты диссертации докладывались на следующих научно- исследовательских семинарах:
-
Московский семинар по теории чисел под руководством член-корр. РАН, профессора Ю.В. Нестеренко и профессора Н.Г. Мощевитина (мех-мат МГУ, 2012 г.).
-
Семинар "Вероятностные и алгебраические методы в комбинаторике" под руководством профессора А.М. Райгородского (мехмат МГУ, 2007-2012 гг., неоднократно).
-
Семинар "Тригонометрические суммы и их приложения" под руководством профессора Н.Г. Мощевитина (мехмат МГУ, 2010г.).
-
Семинар "Узлы и теория представлений" под руководством профессора В.О. Мантурова, ассистента Д.П. Ильютко и ассистента И.М. Никонова (мехмат МГУ, 2011 г.).
-
Семинар "Дискретный анализ" под руководством профессора А.А. Сапоженко (ВМиК МГУ, 2011 г.).
-
Семинар по теории кодирования под руководством д.ф.-м.н. Л.А. Бассалыго (ИППИ РАН, 2011 г.).
-
Научно-исследовательский семинар по математической логике под руководством акад. РАН, профессора С.И. Адяна и член-корр. РАН, профессора Л.Д. Беклемишева (мехмат МГУ, 2012 г.).
-
Кафедральный семинар кафедры дискретной математики под руководством профессора А.М. Райгородского (ФИВТ МФТИ, 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 Сентября 2012 г.).
Работа автора поддержана грантом РФФИ 09-01-00294, грантом РФФИ 12-01-00683 и грантом Президента МД-8390.2010.1.
Публикации
Результаты диссертации опубликованы в 6 работах автора (все они входят в перечень ВАК), список которых приведен в конце автореферата [1-6].
Структура диссертации
Диссертация состоит из введения, трех глав и списка литературы, насчитывающего 70 наименований. Общий объем диссертации составляет 88 страниц.
