Проблемы Борсука и Нелсона-Хадвигера в рациональных пространствах тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Московский физико-технический институт факультет инноваций и высоких технологий

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

Пономаренко Екатерина Игоревна

ПРОБЛЕМЫ БОРСУКА И НЕЛСОНА-ХАДВИГЕРА В РАЦИОНАЛЬНЫХ ПРОСТРАНСТВАХ

01.01.09 — дискретная математика и математическая кибернетика

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

17 АПР 2314

■ Москва — 2014

005547355

005547355

Работа выполнена на кафедре дискретной математики

факультета инноваций и высоких технологий Московского физико-

технического института.

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

профессор Райгородский Андрей Михайлович.

Официальные оппоненты: Доктор физико-математических наук, профессор Ярославского государственного университета им. Г.П. Демидова Дольников Владимир Леонидович;

кандидат физико-математических наук, ведущий научный сотрудник ИППИ РАН Мусин Олег Рустумович.

Ведущая организация: Хабаровское отделение Института

прикладной математики ДВО РАН.

Защита диссертации состоится ЫЛуСи$ 2014 г. в 11 часов на заседании диссертационного совета Д 501.001.44 при Московском государственном университете имени М.В. Ломоносова по адресу: 119991, Москва, ГСП-1, Ленинские горы, 2-й учебный корпус, факультет ВМК, аудитория 685. Желающие присутствовать на заседании диссертационного совета должны сообщить об этом за два дня по тел. 939-30-10 (для оформления заявки на пропуск).

С диссертацией можно ознакомиться в Фундаментальной библиотеке МГУ имени М. В. Ломоносова. С текстом автореферата можно ознакомиться на официальном сайте факультета ВМК МГУ http://cs.msu.ru/. Автореферат разослан « ^ »г.

Председатель /

диссертационного совета / А. А. Васин

Актуальность

Диссертация посвящена изучению вопросов, лежащих на стыке нескольких областей. Впервые задачи, рассматриваемые в данной работе, возникли в рамках комбинаторной геометрии. Хотя это достаточно молодая область дискретной математики и даже сам термин "комбинаторная геометрия" появился только в середине прошлого века, сейчас это бурно развивающаяся дисциплина, которая своим развитием во многом обязана именно этим задачам.

Центральными задачами диссертации являются задача Борсука о разрезании тел в пространстве на части меньшего диаметра и задача Нелсона-Хадвигера о разбиении пространства на части без запрещенного расстояния1,2'3'4,5,6. Для комбинаторной геометрии эти проблемы действительно являются основополагающими. Задача Борсука состоит в отыскании числа f(d) — минимального количества частей меньшего диаметра, на которые можно разбить произвольное множество диаметра 1 в пространстве Rd. В 1933 году К. Борсук высказал гипотезу7, что f(d) = d+ 1. Попытки доказать либо опровергнуть эту гипотезу на протяжении шестидесяти лет оказывали сильное влияние на развитие комбинаторной геометрии, пока в 1993 году Дж. Кан и Г. Калаи не опровергли8 гипотезу Борсука при помощи линейно-алгебраического метода, разработанного П. Франклом и Р. Уилсоном.

Задача о хроматическом числе пространства была сформулирована в 1950 году Э. Нелсоном, который поставил вопрос о том, каково минимальное число цветов, в которые необходимо так раскрасить все евклидово пространство Md, чтобы точки, расстояние между которыми в точности равно единице, оказались раскрашенными в разные цвета.

1В.Г. Болтянский, И.Ц. Гохбсрг, Теоремы и задачи комбинаторной геометрии, Москва, "Наука", 1965.

2А. Soifcr, The Mathematical Coloring Book, Springer, 2009.

3P. Brass, W. Moser, J. Pach, Research problems in discrete geometry, Springer, 2005.

4P.K. Agarwal, J. Pach, Combinatorial geometry, John Wiley and Sons Inc., New York, 1995.

5A.M. Райгородский, Проблема Борсука и хроматические числа метрических пространств, Успехи матем. паук, 56 (2001), вып. 1, 107- 146.

6А.М. Райгородский, Вокруг гипотезы Борсука, Итоги пауки и техники, 23 (2007), 147 - 164.

7К. Borsuk, Drei Sätze über die n-dimensionale euklidische Sphäre, Fundamenta Math., 20 (1933), 177 - 190.

8J. Kahn, G. Kalai, A counterexample to Borsuk's conjecture, Bulletin (new series) of the AMS, 29 (1993), N1, 60 - 62.

Незадолго до того Г. Хадвигер рассматривал похожую задачу: он доказал, что если евклидово пространство Md покрыто d + 1 замкнутым множеством, то хотя бы в одном из этих множеств все неотрицательные вещественные числа реализуются как расстояния между парами точек этого множества. При решении именно этой задачи П. Франкл и Р. Уилсон получили один из наиболее ярких результатов9 за всю историю комбинаторной геометрии. При помощи теоремы Франкла -Уилсона удалось не только совершить прорыв в изучении хроматического числа пространства, а именно доказать гипотезу П. Эрдеша об экспоненциаль-ности роста величины x(Rd), но и, как говорилось выше, опровергнуть гипотезу Борсука, вопрос об истинности которой оставался открытым на протяжении более чем полувека. Улучшению этой теоремы посвящена первая глава диссертационной работы.

Кроме влияния на развитие комбинаторно-геометрических методов, эти проблемы играют важную роль и при изучении других задач. Так, проблема Борсука тесно связана с задачей об освещении тел10'11, с классической проблемой дискретной геометрии об упаковке шаров и других тел в пространстве12'13, с проблематикой геометрии чисел, с задачей Грюнбаума о покрытии тел шарами14'15.

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

9Р. FYankl, R. Wilson, Intersection theorems with geometric consequences , Combinatorica, 1 (1981), 357 - 368.

10H. Martini, P.S. Soltan, Combinatorial problems on the illumination of convex bodies, Aequationes Mathematicae, Springer-Verlag, 57 (1999), 121 - 152

nV.G. Boltyanski, H. Martini, P.S. Soltan, Excursions into combinatorial geometry, Springer, 1997.

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

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

14В. Grünbaum, A simple proof of Borsuk's conjecture in three dimensions, Proc. Cambridge Philos. Soc, 53 (1957), 776 - 778.

15 J. Bourgain, J. Lindenstrauss, On covering a set in Rd by balls of the same diameter, Lecture Notes in Math., Springer-Verlag,Berlin, 1469 (1991), 138 - 144.

тральными в диссертационной работе.

Со временем методы, связанные с изучением проблем Борсука и Нелсона-Хадвигера, изначально сформулированные в комбинаторно-геометрических терминах, оказались исключительно полезными при решении проблем из других областей математики. Так один из наиболее результативных методов в решении указанных задач заключается в рассмотрении систем (ОД)-векторов. Тем самым, возникают естественные приложения в теории кодирования — например, в задачах о равновесных кодах с запрещенными Хэмминговыми расстояниями16'17. В то же время (0,1)-векторы можно интерпретировать как ребра гиперграфов, что дает результаты при изучении их экстремальных свойств.

Наконец вышеупомянутые задачи тесно связаны и с обычными графами: с проблемой Борсука связано понятие графа диаметров, а с задачей Нелсона-Хадвигера — понятие дистанционного графа. С одной стороны, идеи и термины теории графов помогают решать эти задачи, с другой — получаемые результаты имеют значение для самой теории графов.

Цель работы

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

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

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

1. Усилена теорема Франкла-Уилсона.

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

16L. Bassalygo, G. Cohen, G. Zcmor, Codes with forbidden distances, Discrete Mathematics, 213 (2000), 3- 11.

17Ф.Дж. Мак-Вильямс, Н.Дж.А. Слоэп, Теория кодов, исправляющих ошибки, Москва, Радио и связь, 1979.

3. Сформулированы определения корректных аналогов задачи Борсу-ка для рационального пространства.

4. Опровергнут аналог гипотезы Борсука для рационального пространства и исследованы размерности контрпримеров.

5. Изучены верхние и нижние оценки для аналогов числа Борсука.

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

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

При доказательстве результатов нами использовалась разнообразная техника. Так основным методом работы является линейно-алгебраический метод18. Кроме того, в работе используется теорема Алсведе-Хачатряна19, в которой найден максимум числа ребер в гиперграфе с данной нижней границей для мощностей пересечения ребер. В диссертационной работе введено понятие аффинной размерности. Данное понятие сыграло принципиальную роль в обобщении задачи Борсука на случай рационального пространства.

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

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

Апробация работы

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

— Международная конференция "Четвертая польская конференция по комбинаторике" (Бедлево, Польша, 17-21 сентября 2012 г.).

— Всероссийская конференция "55-я научная конференция МФТИ" (Долгопрудный, Россия, 19-25 ноября 2012 г.).

18А.М. Райгородский, Линейно-алгебраический метод в комбинаторике, Москва, МЦНМО, 2007.

19R. Ahlswede, L.H. Khachatrian, The complete nontrivial-intersection theorem for systems of finite sets, J. Combin. Theory A, 76 (1996), 121 - 138.

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

— Семинар под руководством профессора A.M. Райгородского (мехмат МГУ, 2010 г.).

Работа автора поддержана грантом РФФИ N 12-01-00683, грантом НШ-2519.2012.1 и грантом Президента МД-6277.2013.1.

Публикации

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

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

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

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

Первая глава посвящена вопросам верхней оценки числа независимости графов. В ней рассматривается теорема Франкла-Уилсона, формулируются и доказываются уточнения этой теоремы, а также приводятся приложения этих уточнений к задаче о хроматическом числе.

В разделе 1.1 приводится классический вариант теоремы Франкла-Уилсона.

Теорема 1.1.1. Пусть Н = (У,Е) — к-однородный гиперграф (т.е. в каждом его ребре ровно к вершин) на п вершинах, причем для любых е Е выполнено П ф I и к — I — степень простого числа, которую мы обозначим Тогда имеют место два случая:

1. если 21 < к, то

IЯКЕ^;

¿=о

2. если 21 ^ к, то при ¿ = к — 2д + 1 = 2/ — & + 1

В разделе 1.2 формулируется новая теорема 1.2.1, в которой получено усиление для второго пункта теоремы 1.1.1.

Теорема 1.2.1. Пусть Н = (У,Е) — к-однородный гиперграф на п вершинах, причем к ^ для любых е Е выполнено П ^ I, 21 ^ к и <7 = к — I — степень простого числа. Положим <1= 21 — к + 1. Пусть, далее, 2 С N таковы, что (1\ + да = д. Положим щ = п — Л\, к\ = к — д 1. Определим натуральное число г из соотношения

(кг - д2 + 1) + < щ < (к! - ¿2 + 1) (2 + .

Тогда

(~«12+2Г/~<С11 ^п

Доказательство этого утверждения разбито на три этапа. Приведем краткую схему доказательства. Пусть дан гиперграф Н = (У,Е), удовлетворяющий условию теоремы, и п,к, /,7, с?, (¿1,с?2, щ, к\,г — те же самые числа, что и в формулировке. На первом этапе доказывается, что в Н есть такой подгиперграф Н\ = (К Е\) (множество вершин не изменится), что каждые два его ребра пересекаются не менее, чем по <1\, вершинам и число его ребер "не сильно" меньше числа ребер исходного гиперграфа Н. На втором этапе мы увеличиваем мощности попарных пересечений, т.е. выделим, в свою очередь, из Н\ такой подгиперграф Н2 = (V, Е2) (множество вершин снова не изменится), что каждые два его ребра пересекаются не менее, чем по д, = + ¿2, вершинам и число его ребер "не сильно" меньше числа ребер гиперграфа Н\. На третьем этапе за счет условия теоремы, в котором говорится об отсутствии пар ребер в £ (а стало быть, и пар ребер в Е2 С Е\ С Е), пересекающихся по / вершинам, получается верхняя оценка мощности множества Е2. Но, поскольку Е\ не сильно больше Е2, а Е не сильно больше то в итоге и возникнет верхняя оценка мощности Е.

Это доказательство объединяет в себе идеи линейно-алгебраического метода П. Франкла и Р. Уилсона и идеи Алсведе и Хачатряна.

В разделе 1.3 формулируются две теоремы для случая (-1,0,1)-векторов. Это аналог теоремы Франкла-Уилсона и новая теорема 1.3.2, являющаяся его усилением.

Теорема 1.3.1. Пусть п, к-\, ко, таковы, что к\ + к-\ < <

к\, разность кх+к-^—Ь является степенью простого числа (обозначим ее q = ра) ик\ + к-\ — 2д < —2к-\. Тогда

т(п, к-и к0, киг) < ^ СгпС3п

п—г'

где

Л = {(¿,7) : i + j ^n,i + 2j 1}.

Теорема 1.3.2 Пусть п, к-\, ко, к\, £ таковы, что к\+к-\ ^ к-1 ^ к\, разность к\ + к-\ — £ является степенью простого числа (обозначим ее <7 = ра) и к\ + к-1 — 2д ^ — 2к-\. Положим д—к\ + А;_1 — 2д + 1. Пусть ш = (тп1,т2,тз),

причем все элементы вектора и матрицы — натуральные числа,

т1 + тп2 + тз = п, т_1д+тод + Ш1д = тг, т_1,2 + т0,2 + 7771,2 = т2, 771-1,3 + 7770,3 + 7771,3 = 7773, 777-1 д + 777_1,2 + 777_1,3 = к-1,

777-0,1 + 7770,2 + 7П0,3 = к0, ТПхд + 7711,2 + 7771,3 =

м выполнено еще одно условие, для формулировки которого нам потребуются дополнительные обозначения и термины. А именно, пусть множество {1,...,п} представлено в виде объединения трех непересекающихся частей М\, М2, Мз, мощности которых равны т\,т,2,тг соответственно. Скажем, что вектор х = (х-[,..хп) € Уп(к-1, ко, к{) удовлетворяет разбиению Т{М\, М2, Мз), если

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

|{г еМх: Хг = -1}| = ш_1,ь |{г € Мх : = 0}| = т0д,

|{г € Мх : Хг = 1}| = Ш1Д, |{г ем2: Хг = -1}| = 777-1,2, |{г е М2 : х, = 0}| = то,2,

|{г 6 М2 : Х( = 1}| = 7771,2, |{г е Мз : Хг = -1}| = 777-1,3, |{г € М3 : х{ = 0}| = т0,з, |{г € М3 : а^ = 1}| = 7771,3.

777(77, к-х, ко, кг, ^

7771!7772!тз!

ш_1д!т-1|2!т-1,з! га0д!то|2!то,з! т^.т^т^. где

Л={Ц,з)\ г+j^n,i + 2j^q-l}.

Доказательство новой теоремы основано на линейно-алгебраическом методе.

Новые теоремы приводят к неожиданным следствиям в проблеме Нелсона-Хадвигера. Раздел 1.4 содержит в себе результаты приложения усиленных теорем к задаче о хроматическом числе. В частности удается доказать, что оценка Франкла-Уилсона может быть получена не только при к ~ но и при всех к, к ~ к'п, где к' — любое число из отрезка

^ • ^ тому же удается получить усиление оценок для некоторых конфигураций дистанционных графов. Содержание главы 2

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

Определение. Пусть X, У е {К, <0>}, к е N. Положим ххО^п',к) = тах„ь...лехх(^'1;аЬ"-1ак)1 где «ъ • • •, а к) ~ хроматическое

число пространства У" с запрещенными расстояниями а\, ..., а^ .

Для хроматического числа рационального пространства с одним и двумя запрещенными расстояниями приводятся лучшие известные на сегодняшний день результаты и доказываются новые нижние оценки. Теорема 2.2.1 Имеет место оценка

хтхс3+о(1)г,

где Сз = 1-199 ...

Теорема 2.3.1. Имеет место оценка

Нт вир Хк(К"; 2) + Нт вир хоС'О!™; 2) ^ С4 + Сз + й> = 2.693..., 52 я 0.029.

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

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

Определение. Вещественным дистанционным графом (или вещественным графом расстояний) называется любой граф С = (У,Е), у которого

У С К", ЗаеК: £С{{х,у}: х,уеУ, |х-у|=а}, .

Определение. Вполне рациональным дистанционным графом (или вполне рациональным графом расстояний) назовем любой граф С? = (V, Е), у которого

У С <0>п, а£<[}: Е С {{х, у} : х,у€У, |х-у|=о}.

Определение. Назовем аффинной размерностью множества А минимальную размерность пространства, которое его содержит, и обозначим ее айШтА.

Введем новое понятие хроматического числа, а именно ХаЯ^™) = тах{%((9) : С — конечный вполне рациональный дистанционный граф с айШт С7 ^ п}.

Теорема 2.4.1. Имеет место оценка

Х*я(ОГ) > ХеШ > (Сх + 0(1))" (2.2)

А именно, существует такая последовательность конечных вполне рациональных графов расстояний Сп С (О!4" с аЯкНт ^ п и такая последовательность чисел 6п —» 0, п —»• оо, что х(@п) ^ ^

(Сх + ^Г-

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

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

Утверждение. Выполнена оценка fq(n) ^ f(n) для любого п 6 N.

То, что неравенство верно и в другую сторону представляется очевидным. Таким образом, этот аналог не является новой величиной. В разделе 3.2 приводятся два правильных аналога задачи Борсука.

Первый аналог:

XQ,i(") = . max Xq04).

•ACQ", diamA=l

Второй предложенный к рассмотрению аналог использует введенное ранее понятие аффинной размерности:

Ход(") = , л,- Р8*.- д

A: affdimA=n, diamA=l

Для построенных чисел изучаются те же вопросы, что и для классического числа Борсука. А именно формулируются (и опровергается) аналоги гипотезы Борсука, доказываются нижние оценки при растущей размерности п, исследуются минимальные размерности контрпримера к аналогам гипотезы Борсука.

Основные результаты отражены в следующих теоремах Теорема 3.2.1. Имеет место неравенство

+<ВД) = (1.225...+ ii(n))^, ¿i = o(l)

при п —> оо.

Теорема 3.2.2. Имеет место неравенство

т/п

а ff

f,i(n) >

+ = (1.225... + ö2(n))^, S2 = o( 1)

при п —> оо.

Теорема 3.3.1. Для величины х«2д(п) гипотеза неверна при всех п ^ 946.

Теорема 3.3.2. Для величины х«эд(п) гипотеза неверна при п Е [561,757] и при всех п ^ 903.

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

В последнем разделе третьей главы приводится еще одно обобщение понятия рационального числа Борсука, а именно предлагается рассмотреть его для других вариантов метрики. Для метрики 1Р число Борсука обозначим xq,i(п,р), а в аффинном случае — Ход(п>Р)-

Для случая, когда р 6 N, в диссертации приводится доказательство следующих асимптотических оценок:

ХОД(п,р) >Щ= (1-203... + ii(n))^, ¿2 = о(1). 4д(п,Р) >Щ = (L203- + ¿2 = о(1).

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

Работы автора по теме диссертации

[1] Е.И. Пономаренко, A.M. Райгородский, Улучшение теоремы Франкла-Уилсона о числе ребер гиперграфа с запретами на пересечения, Доклады РАН, 2013. (A.M. Райгородскому принадлежит постановка задачи и редакция введения, Е.И. Пономаренко принадлежит доказательство всех основных результатов.)

[2] Е.И. Пономаренко, A.M. Райгородский, Новые оценки в задаче о числе ребер в гиперграфе с запретами на пересечение, Проблемы передачи информации, 2013. (A.M. Райгородскому принадлежит постановка задачи и редакция введения, Е.И. Пономаренко принадлежит доказательство всех основных результатов.)

[3] Е.И. Пономаренко, A.M. Райгородский, Новая нижняя оценка хроматического числа рационального пространтсва, УМН, 2013. (A.M. Райгородскому принадлежит постановка задачи и редакция введения, Е.И. Пономаренко принадлежит доказательство всех основных результатов.)

[4] Е.И. Пономаренко, A.M. Райгородский, О хроматическом числе пространства Q", Труды МФТИ, 4(2012), N1, 127-130. (A.M. Райгородскому принадлежит постановка задачи и редакция введения, Е.И. Пономаренко принадлежит доказательство всех основных результатов.)

[5] Е.И. Пономаренко, A.M. Райгородский, О некоторых аналогах проблемы Борсука в пространстве Q", Доклады РАН, 436 (2011), N3, 306-310. (A.M. Райгородскому принадлежит постановка задачи и редакция введения, Е.И. Пономаренко принадлежит доказательство всех основных результатов.)

[6] A.B. Купавский, Е.И. Пономаренко, A.M. Райгородский, О некоторых аналогах проблемы Борсука в пространстве Q™, Труды МФТИ, 4(2012), N1, 81-90. (A.M. Райгородскому принадлежит постановка задачи и редакция введения, A.B. Купавскому принадлежит редакция доказательства основной теоремы, Е.И. Пономаренко принадлежит доказательство всех основных результатов.)

Заказ № 43-Р/03/2014 Подписано в печать 13.03.14 Тираж 100 экз. Усл. п.л. 0,8

ООО "Цифровичок", тел. (495) 797-75-76 www.cfr.ru ; е-таИ:info@cfr.ru

Московский физико-технический институт факультет инноваций и высоких технологий

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

04201457730

Пономаренко Екатерина Игоревна

ПРОБЛЕМЫ БОРСУКА И НЕЛСОНА-ХАДВИГЕРА В РАЦИОНАЛЬНЫХ ПРОСТРАНСТВАХ

01.01.09 — дискретная математика и математическая кибернетика

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

Научный руководитель — д.ф.-м.н. А.М. Райгородский

Москва, 2014

Оглавление

Список основных обозначений....................................................................4

Введение................................................................................................................6

Глава 1 Верхняя оценка числа независимости графов

1.1 Теорема Франкла-Уилсона....................................................................14

1.2 Улучшение теоремы Франкла-Уилсона..............................................15

1.2.1 Формальное доказательство......................................................16

Схема доказательства................................................................16

Первый этап................................................................................17

Второй этап..................................................................................17

Третий этап..................................................................................18

1.2.2 Комментарии к доказательству ..............................................20

1.3 Обобщение теоремы Франкла-Уилсона на случай (—1, 0,1)-векторов и ее улучшение........................................................................................20

1.4 Приложения в задаче Нелсона-Эрдеша-Хадвигера........................25

Глава 2 Хроматическое число рационального пространства

2.1 Определение хроматического числа рационального пространства 30

2.2 Новая нижняя оценка хроматического числа рационального пространства с одним запрещенным расстоянием..................................31

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

2.4 Хроматическое число аффинно-рационального пространства ... 36

Глава 3 Некоторые аналоги задачи Борсука

3.1 Задача Борсука для вещественного и рационального пространства ............................................................................................................40

3.2 Правильный аналог задачи Борсука для рационального пространства ..................................................................................................41

3.3 Размерности контрпримеров ................................................................45

3.3.1 Случай та ^ 903 (та ^ 946) ........................................................46

3.3.2 Случай та е [561,757]..................................................................48

3.4 Обобщение на случай метрики 1Р ........................................................49

Заключение Список литературы

Список основных обозначений

N — множество натуральных чисел;

Q — множество рациональных чисел;

Q[a?i,..., хп] — пространство многочленов от п переменных с рациональными коэффициентами;

Ш — множество действительных чисел;

\А\ — мощность конечного множества А;

[а] — целая часть числа а;

а\Ь — свойство "а делит 6", т.е. число а является делителем числа 6;

(х, у) — евклидово скалярное произведение векторов хиу;

|х| — норма вектора х в евклидовом пространстве;

V(G) — множество вершин графа G]

E(G) — множество ребер графа G;

f(N) = o(g(N)) — для любого числа с > 0 существует такое число Nq, что для любого N > Nq выполнено неравенство |/(iV)| ^ c\g(N)\;

fix) ~ д{х) — функции асимптотически равны при х —У оо, то есть fix) — 9{х) ' (1 + °(1))>

г(х,у) — расстояние между точками х, у в метрике г;

— индикатор события X. То есть 1(^0 = 1 в случае, если X выполняется, и 0 — иначе;

а = b( mod к) — а сравнимо с 6 по модулю к, то есть а и b дают одинаковые остатки при делении на к;

а^Ь — а приближенно равно Ь с точностью до последнего разряда; С* — число сочетаний из п элементов по к.

Введение

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

Актуальность

Диссертация посвящена изучению вопросов, лежащих на стыке нескольких областей. Впервые задачи, рассматриваемые в данной работе, возникли в рамках комбинаторной геометрии. Хотя это достаточно молодая область математики и даже сам термин "комбинаторная геометрия" появился только в середине прошлого века, сейчас это бурно развивающаяся дисциплина, которая своим развитием во многом обязана именно этим задачам. Разумеется, первые задачи комбинаторной геометрии были известны задолго до того, как появилась эта дисциплина: одним из первых задачами комбинаторной геометрии занимался еще И. Кеплер в начале XVII века.

Основными задачами данной работы являются задача Борсука о разрезании тел в пространстве на части меньшего диаметра и задача Нелсона-Хадвигера о разбиении пространства на части без запрещенного расстояния (см. [1] — [16]). Для комбинаторной геометрии эти задачи действительно являются центральными. Так, гипотеза Борсука тесно связана с задачей об освещении тел (см. [1], [17] — [19]), с классической проблемой дискретной геометрии об упаковке шаров и других тел (см. [20] — [22]), с проблематикой геометрии чисел, с задачей Грюнбаума о покрытии тел шарами (см. [23] — [27]).

Со временем, методы связанные с изучением задач Борсука и Нелсона-Хадвигера, изначально сформулированные в комбинаторно-геометрических терминах, оказались исключительно полезными при решении проблем из других областей математики. Так один из наиболее результативных методов в решении указанных задач заключается в рассмотрении систем (ОД)-векторов. Тем самым, возникают естественные приложения в теории кодирования — например, в задачах о равновесных кодах с запрещенными Хэмминговыми расстояниями (см. [28], [29]). В то же время (0,1)-векторы можно интерпретировать как ребра гиперграфов, что дает результаты при изучении их экстремальных свойств. Наконец вышеупомянутые задачи тесно связаны и с обыч-

ными графами: с проблемой Борсука связано понятие графа диаметров, а с задачей Нелсона-Хадвигера — понятие дистанционного графа. С одной стороны, идеи и термины теории графов помогают решать эти задачи, с другой стороны, получаемые результаты имеют значение для самой теории графов. В следующих параграфах мы подробно остановимся на истории проблемы Борсука и Нелсона-Хадвигера.

Проблема Борсука

В 1933 году К. Борсук (см. [30]) сформулировал следующий вопрос: верно ли, что всякое ограниченное неодноточечное множество в может быть представлено в виде объединения своих частей меньшего диаметра, причем так, чтобы количество этих частей не превышало с1 + 1? Предположение о справедливости положительного ответа на этот вопрос получило впоследствии название "гипотеза Борсука".

К решению этой задачи подходили с разных сторон. В первую очередь справедливость этой гипотезы проверяли в "малых" размерностях. Конечно, для с1=1 утверждение сразу следует из того, что отрезок длины 1 разбивается на два отрезка длины В случае размерности 4 = 2 сам К. Борсук показал, что любое множество диаметра 1 разбивается на три части меньшего диаметра, и именно этот результат привел его к формулировке общей гипотезы. В доказательстве Борсука использовалась следующая лемма: каждое множество диаметра И может быть покрыто правильным шестиугольником, у которого расстояния между противоположными сторонами также равны Б (см. [1], [30] и [31]).

В размерности с£ = 3 ситуация усложняется. Впервые о доказательстве гипотезы Борсука в этой размерности было заявлено в кратком сообщении Перкала (см. [33]), но полное доказательство так и не было опубликовано. Чуть позже Эгглстон (см. [32]) предложил неэлементарное доказательство гипотезы. В последствии было предложено несколько элементарных доказательств. В 1957 году Б. Грюнбаум (см. [23]) доказал, что любое трехмерное множество диаметра И можно покрыть некоторым усеченным октаэдром, который допускает разбиение на 4 части диаметра меньше И. В том же году А. Хеппеш (см. [34]) нашел другое элементарное решение трехмерной проблемы.

Начиная с размерности 4 проблема Борсука до сих пор полностью не решена. Однако, хочется отметить, что свой вклад в изучение проблемы Борсука в "малых" размерностях, помимо упомянутых авторов, внесли В.В. Макеев (см. [35] и [36]), А.Л. Евдокимов, Р. Ревес (совместно с А. Хеппешем — [37]), П. Кацарова-Каранова (см. [38]) и др.

Поскольку окончательного результата в проблеме Борсука получить не удавалось, были предприняты попытки решить проблему в каких-нибудь специальных случаях. В 1946 году Г. Хадвигер доказал, что всякое ¿-мерное множество с гладкой границей может быть разбито на с1 + 1 часть меньшего диаметра (см. [39]). Доказательство теоремы Хадвигера и её небольшое усиление содержится в [39] и в книге [1]. В 1971 году К.А. Роджерс (см. [40]) предложил принципиально другой класс множеств, для каждого их которых верна гипотеза Борсука. А именно гипотеза Борсука справедлива для множеств, которые инвариантны под действием группы симметрий правильного (¿-мерного симплекса.

С гипотезой Борсука связано понятие числа Борсука. Пусть / — произвольное натуральное число такое, что всякое ограниченное точечное множество ненулевого диаметра О С ^ может быть разбито на / частей меньшего диаметра. Определим /(¿) как число, минимальное среди всех таких /. В этих терминах гипотеза Борсука равносильна равенству /(¿) = с1 + 1. Нетрудно видеть, что величина f{d) всегда конечна. В самом деле, произвольное множество диаметра И содержится в ¿-мерном кубе с ребром I), и нужно лишь разбить этот куб на столь мелкие кубики, что диаметр каждого из них будет меньше И. Этот факт был впервые замечен X. Ленцем в 1955 году (см. [26]). Из него вытекает оценка /(¿) < Развитие идей отно-

сительно числа Борсука вылилось в борьбу за усиление оценок с точки зрения уже не конкретных размерностей, а с точки зрения растущей размерности. Так, первым эту верхнюю оценку слегка улучшил К. Борсук (см. [41]) в 1978 году. А в 1982 году М. Лассак (см. [42]) показал, что /(¿) ^ 2Л~1 + 1. В малых размерностях эта оценка является наилучшей из известных. Например, при с1 = 4 оценка /(4) ^ 9 по-прежнему является рекордной. При больших б? наилучшую известную оценку в 1988 году сформулировал О. Шрамм (см.

Аналогичный результат установили в работе [27] Ж. Бургейн и Й. Линден-штраусс. Таким образом, для величины /(¿) есть только экспоненциальные верхние оценки.

Итак, мы видим, что подходов к решению проблемы Борсука имеется достаточно много, и тем не менее ни один из них не дает желаемого результата. Еще К.А. Роджерс в своей статье 1971 года о разбиении симметричных множеств (см. [40]) писал, что получил основной результат этой статьи в попытках опровергнуть гипотезу Борсука. А 10 лет спустя П. Эрдеш предположил, что можно построить контрпример к гипотезе Борсука с помощью некоторых

[43]):

конечных точечных конфигураций в Md (см. [44]). Аналогичное предположение высказал и Д. Ларман (см. [45] и [46]).

Наконец, в 1993 году гипотеза Борсука была опровергнута. Дж. Кан и Г. Калаи с помощью результатов работы П. Франкла и Р. Уилсона 1981 года (см. [47]) построили контрпримеры к гипотезе во всех размерностях d > 2015 (см. [48]). Из их конструкции вытекала оценка f(d) > (1.203... + о(1))^. Ввиду этой оценки результаты Шрамма и Бургейна-Линденштраусса перестают казаться далекими от истины. В дальнейшем были предприняты достаточно многочисленные попытки понижения размерности контрпримера и, одновременно, усиления нижней оценки величины f(d). Так, в 1994 году А. Нилли предложил некоторую модификацию метода Кана и Калаи и в результате нашел отрицательное решение проблемы К. Борсука при d > 946 (см. [49]). Кроме того, работа Нилли была краткой и, в отличие от работы Дж. Кана и Г. Калаи, полностью замкнутой в себе. Далее, в 1997 году Й. Грэй и Б. Вайс-бах построили, за счет небольшого уточнения метода А. Нилли, контрпримеры для всех d > 903 (см. [50]). В том же году A.M. Райгородский (см. [51]) обнаружил иную модификацию подхода Нилли, которая позволила ему опровергнуть гипотезу Борсука уже при d = 561. В 2000 году Б. Вайсбах слегка видоизменил конструкцию из [51], сумев тем самым уменьшить размерность контрпримера еще на единицу (см. [52]). После этого А. Хинрихс предложил новую конструкцию, с помощью которой удалось еще сильнее уменьшить размерность контрпримера — до d = 323. В 2002 году Пихурко уменьшил эту размерность на 1 (см [54]). В 2003 году Хинрихс вернулся к задаче и доказал результат для d ^ 298 (см [55]). Этот результат держался 10 лет и в 2013 году A.B. Бондаренко сумел опровергнуть гипотезу при всех d ^ 65 (см [56]). В том же году Т. Йенрих понизил эту размерность до 64. В таблице ниже приведен список улучшений размерности контрпримера.

Таблица 1:

Авторы публикации Год Ссылка Размерность контрпримера к гипотезе п ^

Дж. Кан, Г. Калаи 1993 [48] 2015

А. Нилли 1994 [49] 946

Б. Вайссбах, И. Грей 1997 [50] 903

A.M. Райгородский 1997 [51] 561

Б. Вайссбах 2000 [52] 560

А. Хинрихс 2001 [53] 324

О. Пихурко 2002 [54] 323

А. Хинрихс, X. Рихтер 2003 [55] 298

A.B. Бондаренко 2013 [56] 65

Т. Йенрих 2013 [57] 64

Помимо попыток понизить размерность контрпримера, предпринимались

попытки улучшить асимптотические оценки величины f(d). Однако, известен только один результат, улучшающий оценку Дж. Кана и Г. Калаи, а именно A.M. Райгородский с помощью одного обобщения метода А. Нилли сумел доказать что f(d) > (2/у/3 + о{ 1))^ = (1.225... + о( 1))^ (см. [58]).

Как говорилось выше, задачи комбинаторной геометрии часто связаны с теорией графов. Это касается, в частности, проблемы Борсука. В теории графов большое внимание уделяется хроматическому числу x{G) — минимальному числу цветов, в которые можно так покрасить некоторый граф G, чтобы концы любого ребра имели разные цвета. Связь проблемы Борсука с хроматическими числами графов реализуется через граф диаметров. Граф диаметров для некоторого тела А — это такой граф G(A), вершинами которого являются все точки, принадлежащие А, а ребрами соединены те из них, которые отстоят друг от друга на расстояние, равное диаметру тела А. Очевидно, что для того, чтобы разбить А на части меньшего диаметра, понадобится число частей, не меньшее, чем x(G(A)) — хроматическое число графа G(A). Таким образом, графы диаметров позволяют строить нижние оценки числа Борсука. Важно отметить, что именно эта идея позволила в свое время Дж. Кану и Г. Калаи опровергнуть гипотезу Борсука.

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

Другой классической задачей комбинаторной геометрии является задача о хроматическом числе пространства. В 1944 году Г. Хадвигер опубликовал работу [59], в которой доказал, что если евклидово пространство M.d покрыто d+ 1 замкнутым множеством, то хотя бы в одном из этих множеств все неотрицательные вещественные числа реализуются как расстояния между парами точек этого множества. В 1950 году Э. Нелсон поставил очень близкую задачу о том, каково минимальное число цветов, в которые необходимо так раскрасить все евклидово пространство чтобы точки, расстояние между которыми в точности равно единице, оказались раскрашенными в разные цвета. Это число получило название хроматического числа пространства M.d. Его принято обозначать

Изучение величины в некотором смысле созвучно изучению числа

Борсука, которое мы обсуждали выше. Так, для хроматического числа тоже рассматривались малые размерности, верхние и нижние оценки. К сожалению, в отличие от числа Борсука, значения хроматического числа не удалось найти даже для размерности d = 2 (для размерности d = 1 ответ очевиден: хС®1) = 2). Известно лишь, что

4 ^ х(К2) < 7.

Обе эти оценки были доказаны в 1961 году — нижняя J1. Мозером и В. Мо-зером, а верхняя Г. Хадвигером (см. [60] и [61]), и никаких принципиальных улучшений с тех пор найдено не было. При d = 3 известно, что

6 < x№d) < 15.

Оценки были доказаны в 2002 году — нижняя О. Нечуштаном (см. [62]), а верхняя Д. Кулсоном (см. [63]).

По-видимому, первым, кто получил нетривиальную нижнюю оценку для хроматического числа вещественного пространства в произвольной размерности d, был Д.Е. Райский, доказавший, что ^ d+2 (см. [64]). Результат этот Райский получил путем прямого обобщения идей J1. Мозера и В. Мозера (см. [60]). Далее, в 1972 году Д. Ларман и К.А. Роджерс (см. [65]) установили оценку ^ Cl(iogгДе ci > 0 — абсолютная константа. П. Эрдеш и В. Шош заметили, что если сочетать идеи Лармана и Роджерса с техникой из работ Ж. Надя, то получится еще лучшая оценка x(Kd) ^ (1 + о(1))у.

В дальнейшем результаты Д. Лармана, К.А. Роджерса, В. Шош и П. Эр-деша неоднократно улучшались. Сперва, в 1978 году сам Д. Ларман показал, чтохОИ ^ (d — 1)(d—2)(rf — 3)/178200 (см. [66]). Затем, в 1980 году П. Франки получил неравенство х(^) > ^ гДе t любое, a d ^ d(t) (см. [67]). Прорыв был совершен в 1981 году в замечательной работе П. Франкла и Р. Уилсона, в той самой работе, которая цитировалась в связи с проблемой Борсука и контрпримером Дж. Кана и Г. Калаи (см. [47]). В этой работе авторы доказали гипотезу П. Эрдеша о том, что величина растет экспоненциально. А именно, они установили неравенство x(®d) ^ (1.207 ... + o(l))d. При этом еще в 1972 году Д. Ларман и К.А. Роджерс с помощью Г.Л. Батлера и метода П. Эрдеша и К.А. Роджерса доказали, что x(^d) ^ (3 + o(l))d (см. [65], [68] и [69]).

Наконец, в 2000 году A.M. Райгородский доказал теорему, которая приводит к оценке x(Md) ^ (1.239 ... + o(l))d (см. [70]).

Как и проблема Борсука, задача об отыскании хроматическо