Проблемы Борсука, Нелсона-Эрдеша-Хадвигера и Грюнбаума в комбинаторной геометрии

ОГЛАВЛЕНИЕ Введение 8
Общая характеристика работы 12
Список использованных обозначений 23
Глава. Исторический обзор 26
1.1 Постановки задач..............................26
1.2 Проблема Борсука..............................28
1.2.1 Проблема Борсука в "малых” размерностях ......................................28
1.2.2 Проблема Борсука для некоторых специальных классов множеств....................32
1.2.3 Верхние оценки на минимальное число
частей меньшего диаметра...............34
1.2.4 Контрпримеры к гипотезе Борсука и
нижние оценки на минимальное число частей меньшего диаметра...............37
1.3 Хроматические числа некоторых метрических
пространств...................................39
1.3.1 Общая постановка задачи ................39
1.3.2 Некоторые предварительные замечания 40
1.3.3 Оценки хроматических чисел в ”малых”
размерностях...........................42
2
1.3.4 Оценки хроматических чисел с ростом
размерности и реализация всех расстояний при разбиении пространства Л'* на некоторое число частей.................44
1.4 Проблема Грюнбаума..............................47
Глава. Линейно-алгебраический метод.
Нижние оценки в задачах Борсука и
Нелсона - Эрдеша - Хадвигера 50
2.1 Несколько общих замечаний.......................50
2.2 Формулировки результатов........................51
2.2.1 Проблема Борсука и хроматические числа некоторых метрических пространств 51
2.2.2 Одно обобщение задачи Нелсона - Эрдеша - Хадвигера...............................58
2.3 Доказательства результатов......................61
2.3.1 Общее описание подхода....................61
2.3.2 Доказательство теоремы 2.2.1.1.......64
2.3.3 Доказательство теоремы 2.2.1.2.......68
2.3.4 Доказательства теорем 2.2.1.3 и 2.2.1.4 . 71
2.3.5 Доказательство теоремы 2.2.1.5.......74
2.3.6 Доказательство теоремы 2.2.1.6.......76
2.3.7 Доказательство теорем 2.2.2.1 и 2.2.2.2 . 78
2.3.8 Несколько дополнительных наблюдений 85
2.4 Еще несколько результатов.......................88
2.4.1 Системы векторов с запретами на скалярные произведения............................88
2.4.2 О связи между задачами Борсука и Нелсона - Эрдеша - Хадвигера......................89
2.4.3 Доказательство теоремы 2.4.1.1............92
2.4.4 Доказательство теоремы 2.4.2.1............93
2.5 Краткое резюме метода...........................97
3 Глава. Метод альтернирования.
Хроматические числа конечных геометрических графов 99
3.1 Несколько общих замечаний.......................99
3.2 Постановки задач...............................100
3.3 Формулировки результатов.......................105
3.3.1 (-1,0,1) - задача .......................105
3.3.2 (-2,-1,0,1,2) - задача...................110
3.3.3 Общий случай в задаче....................115
3.4 Доказательства результатов.....................119
3.4.1 Небольшое напоминание (общие предпосылки) 119
3.4.2 Доказательство теоремы 3.3.1.2...........119
ф 3.4.3 Доказательство теоремы 3.3.1.3...........124
3.4.4 Доказательство теоремы 3.3.1.4...........125
3.4.5 Доказательства теорем 3.3.2.1 - 3.3.2.4
и 3.3.3.1, 3.3.3.2.......................130
3.5 Соотношения между полученными
результатами....................................137
3.6 Еще несколько результатов......................143
3.6.1 Приложение разработанного метода к
задаче параграфа 2.2.2...................143
3.6.2 О числах Борсука и Нелсона - Эрдеша
- Хадвигера..............................146
3.6.3 Доказательство теоремы 3.6.2.1...........150
3.6.4 Доказательство следствия 3.6.2.1 . . . .156
3.6.5 Дополнение...............................156
•1
3.7 Краткое резюме метода
158
Глава. Метод покрытия с зацеплением.
Верхние оценки в задачах Борсука, Грюнбаума и Нелсона - Эрдеша - Хадвигера для многогранников и
конечных геометрических графов 171
4.1 Несколько общих замечаний....................171
4.2 Постановки задач.............................172
4.3 Формулировки результатов.....................174
4.3.1 Предварительные замечания.............174
4.3.2 Случай (0,1) - многогранников.........175
4.3.3 Случай ( — 1,0,1) - многогранников
(кросс - политопов)....................180
4.3.4 Общий случай..........................186
4.4 Вспомогательные определения: задача о покрытии 192
4.5 Доказательства результатов...................194
4.5.1 Общие предпосылки.....................194
4.5.2 Доказательство теоремы 4.3.4.1........195
4.5.3 Комментарии к доказательству
теоремы 4.3.4.2........................205
4.5.4 Несколько иллюстраций к
параграфу 4.5.2 .......................209
4.5.5 Несколько слов о теореме 4.3.2.3......210
4.6 Соотношения между полученными
результатами.................................211
4.7 Приложение 1: покрытие множеств шарами
в произвольной норме.........................215
4.8 Приложение 2: хроматические числа конечных геометрических графов...........................
4.9 Краткое резюме метода........................
5 Глава. Хроматические числа в малых размер ностях
5.1 Несколько общих замечаний....................
5.2 Формулировки результатов.....................
5.3 Доказательства результатов...................
5.3.1 Доказательство теоремы 5.2.4.........
5.3.2 Доказательство теорем 5.2.1 и 5.2.2 . . .
5.3.3 Доказательство теоремы 5.2.3.........
5.4 Краткое резюме метода........................
6 Глава. Проблема Борсука в малых размерно стях
6.1 Несколько общих замечаний....................
6.2 Об одной модификации трехмерного подхода Грюнбаума.......................................
6.3 Универсальные покрывающие системы и специальные разбиения .............................
6.4 Целочисленные многогранники в малых размерностях ......................................
7 Глава. Вероятностный метод.
Вложение случайного графа в геометрический
7.1 Несколько общих замечаний....................
7.2 ’’Двумерный случай” .........................
7.2.1 Постановка задачи ....................
218
219
225
225
225
226 226 229 235 242
243
243
243
251
255
259
259
260 260
7.2.2 Формулировки некоторых результатов . 261
7.2.3 Доказательства теорем...............262
7.2.4 Обсуждение нижних оценок............264
7.3 Случай произвольной размерности...............266
7.3.1 Постановка задачи .....................266
7.3.2 Верхние оценки ........................266
7.3.3 Обсуждение нижних оценок............267
7.3.4 Обсуждение вопроса существования . . 268
Список использованных источников 271
7
#
Введение
В диссертации рассматривается несколько классических и глубоко связанных между собою задач комбинаторной геометрии. Если стремиться дать достаточно короткое определение самой комбинаторной геометрии как отдельной математической дисциплины, то следует, по-видимому, сказать так: комбинаторная геометрия - это раздел математики, который находится на стыке комбинаторики и дискретной геометрии, т.е. раздел, основные задачи которого связаны с отысканием комбинаторных характеристик, позволяющих так или иначе описывать структуру различных дискретных систем множеств в тех или иных пространствах. На самом деле, невозможно, конечно, вместить в одном определении всю полноту науки, но некоторое общее представление о предмете оно все-таки дает.
Термин "комбинаторная геометрия1’, разумеется, намного моложе самого предмета. Довольно трудно сейчас определить, кто первым ввел его в оборот, и на сей счет существуют различные мнения. Одним из наиболее признанных "авторов" термина является, по-видимому, замечательный геометр Г. Хадвигер, который в 1955 году использовал его в своих работах [121], [122]. Нелепо, однако же, думать, что 1955 год можно считать датой основания комбинаторной геометрии как определенной выше дисциплины и как совокупности соответствующих задач. В то же время понятно, что наука, имя которой было придумано лишь около полувека назад, не может быть слишком старой. По крайней мере, вряд ли она могла сформироваться в единое целое, скажем, более ста лет назад. В сущности, так оно и
есть: хотя дату возникновения науки указать еще труднее, нем момент ее самоидентификации, да и, более того, было бы странно надеяться на отыскание сколь-нибудь осмысленной точки отсчета, но с известной долей уверенности можно утверждать, что фундамент для будущей многогранной и плодотворной деятельности был заложен на рубеже XIX и XX веков.
В действительности, проще объяснять суть предмета, двигаясь не от общего к частному, а в обратном направлении. Иными словами, гораздо естественнее попытаться перечислить хотя бы те классические задачи, которые легли в основу науки и которые в максимальной степени стимулировали дальнейшее ее развитие. Наиболее интересную для нас группу таких задач образуют три проблемы - проблема К. Борсука (см., например, [1], [8], [11], [24], [141]) о разбиении множеств на части меньшего диаметра, проблема Е. Нелсона - П. Эрдеша - Г. Хадвигера (см., например, [2], [66], [141], [152]) о раскраске метрических пространств и проблема Б. Грюнбаума (см., например, [5]) о покрытии множеств шарами того же диаметра. К этой группе следует добавить также задачу Хадвигера - Маркуса - ГЪхберга - Болтянского (см. [8], [24], [123]) об освещении границы выпуклого тела минимальным количеством направлений и задачи, связанные с теоремой Хелли (см., например, [5], [118], [119]). Каждая из этих задач, будучи, безусловно, жемчужиной комбинаторной геометрии, является классической и в самом широком контексте. Популярность этих задач не вызывает никаких сомнений: так, в разные годы ими занимались столь замечательные специалисты в области дискретной геометрии и комбинаторики, как Хелли, Юнг, Борсук, Эрдеш,
Грюнбаум. Кли, Роджерс, Ларман, Болтянский, Ленц, Гэйл, Данцер, Бургейн, Калаи, Алон, Циглер и др. II это тем более удивительно и показательно, если учесть, что проблема Борсука была поставлена в 1933 году, проблема Нелсона -Эрдеша - Хадвигера - в 1950, проблема Грюнбаума - в 1957, проблема Хадвигера - Маркуса - Гохберга - Болтянского -в конце 50-ых и лишь проблема Хелли - в десятые годы XX века.
Непосредственно важные для нашей диссертации задачи Борсука, Нелсона - Эрдеша - Хадвигера и Грюнбаума, вероятно, особенно значимы, красивы и популярны. С одной стороны, само по себе любое продвижение в них представляет огромный интерес и вызывает мощный резонанс. С другой стороны, они как бы выступают в роли катализаторов для создания новых методов и генерации новых идей, которые впоследствии оказываются применимыми далеко не только в комбинаторной геометрии. Наконец, и сочетание их отнюдь не случайно. Мало того, что глубокая связь между ними ясна уже из их формулировок, - эта связь методически прослеживается в последние годы все глубже и глубже, и соискателю принадлежит немало излагаемых ниже результатов, которые ярко об этом свидельствуют.
Таким образом, предварительно суммируя сказанное, можно утверждать, что одним из приоритетнейших направлений в современной комбинаторной геометрии является разработка методов и техники, позволяющих, во-первых, эффективно решать три поставленные задачи, а во-вторых, не менее эффективно использовать знания о каждой из них для получения новой информации об остальных.
Диссертация делится на семь глав. В первой главе да-
ются постановки основных проблем и подробно излагается их история. Во второй главе в деталях разрабатывается линейно-алгебраический метод исследования задач Борсука и Нелсона - Эрдеша - Хадвигера. Этот метод применяется к получению самых сильных нижних оценок на так называемое число Борсука и на хроматические числа различных метрических пространств. При этом в его рамках прослеживается нетривиальная связь между задачами. Третья глава посвящена построению 'метода альтернирования”, который, вбирая в себя значительную часть техники первой главы, является нетривиальной надстройкой над этой техникой, помогающей добиться новых важных продвижений в вопросах получения нижних оценок на хроматические числа конечных геометрических графов и на числа Борсука и Нелсона - Эрдеша - Хадвигера. В четвертой главе разрабатывается еще один новый метод, который мы назвали '’методом покрытия с зацеплением”. В отличие от первых двух, он позволяет установить глубокую связь между результатами относительно проблем Борсука и Грюнбаума. При этом метод применен к весьма обширному классу задач, касающихся разбиения многогранников на части меньшего диаметра и покрытия их шарами того же диаметра. Верхние оценки на минимальное число подобных частей и шаров оказываются существенно сильнее всех известных прежде. Более того, в конце главы дается приложение метода и к отысканию наилучших верхних оценок на хроматические числа конечных геометрических графов. В пятой главе доказываются новые нижние оценки на хроматические числа некоторых "маломерных” пространств. В шестой главе разрабатывается тонкая геометрическая техника, позволяющая уточнять все
прежние результаты относительно оптимального разбиения множеств в размерности 3. Наконец, в седьмой главе осуществляется исследование задачи Нелсона - Эрдеша - Хадви-гера с теоретико-вероятностной точки зрения. А именно, предлагается техника вложения случайного графа в геометрический, и на ее основе изучается поведение хроматического числа пространства ’'почти наверное’'.
Благодарности. Соискатель считает своим приятным долгом в первую очередь поблагодарить д.ф.-м.н. Н.Г. Мо-щевитина за постоянный интерес и внимание к его работе. Соискатель также благодарит д.ф.-м.н. Н.П. Долбилина и проф. С.В. Конягиназа неоднократную помощь и поддержку.
Общая характеристика работы
Актуальность темы диссертации. В работе подробно исследуются три глубоко связанные между собой классические проблемы современной комбинаторной геометрии. Первая из них - проблема Борсука - была сформулирована ровно 70 лет назад (см. [1]), и за прошедшие годы она, безусловно, сделалась ключевой в области дискретной геометрии и комбинаторики: с одной стороны, любое продвижение в ней вызывает мощный международный резонанс, а с другой стороны, она служит естественным катализатором возникновения новых идей и направлений в рамках соответствующего раздела науки. Говоря кратко, она состоит в определении минимального числа частей меньшего диаметра, на которые может быть разбито произвольное ограниченное множество в пространстве. Уже из такой постановки
понятно, что должна существовать нетривиальная взаимосвязь проблемы с известными и весьма приоритетными задачами разбиений и упаковок в пространствах - задачами, несомненно, важными как с фундаментальной, так и с прикладной точек зрения. И действительно, эта взаимосвязь отслеживается в многочисленных работах таких специалистов в дискретной геометрии, геометрии чисел и комбинаторике, как К.А. Роджерс (см. [79]), Р. Ранкин (см. [80]), Ж. Бургейн и И. Линденштраусс. (см. [30]) и др. Более того, деятельность, относящаяся к отысканию верхних оценок на упомянутое минимальное число в проблеме, имеет выход и на задачи нахождения столь значимых аналитических характеристик, как, например, Колмогоровская энтропия. Здесь следует сразу же сослаться и на третью проблему из числа рассматриваемых в диссертации. Это так называемая проблема Грюнбаума (см. [5]), возникшая в середине пятидесятых годов XX столетия и состоящая в изучении минимального количества равных шаров, которыми покрывается произвольное множество в пространстве. Связь между проблемами Борсука и Грюнбаума очевидна, а соотношение последней и перечисленных выше классических вопросов геометрии чисел и анализа еще более прозрачно, чем это было в случае проблемы Борсука. Возвращаясь к последней, стоит дополнительно сказать, что она также имеет тонкие связи с задачами топологии и теории размерности: по-видимому, для самого Борсука возможность отыскания приложений в этих областях и послужила основной мотивировкой вопроса.
Вторая проблема, изучаемая нами в работе, принадлежит нескольким авторам, из которых наибольшую роль в ее становлении сыграли Э. Нелсон, П. Эрдеш и Г. Хадвигер (см.
[2], [4], [141]). Проблема сводится к нахождению наименьшего количества цветов, необходимых для такой раскраски метрического пространства, при которой между точками одного цвета не может быть некоторого фиксированного заранее расстояния. Ей также больше 50-и лет, и ее популярность огромна. Во-первых, ясно, что практически все связи, приведенные нами при обсуждении проблем Борсука и Грюнбаума, актуальны и для нее: более того, с точки зрения разбиений и упаковок пространств она даже интереснее, так как в ней разрабатывается техника, относящаяся к так называемым разбиениям Вороного и имеющая непосредственный выход на замечательные статьи [70], [71], [63] и др. Во-вторых, она в значительной мере связана с различными важными задачами теории графов, в том числе и случайных.
На самом деле, особенно тонкие и нетривиальные связи между тремя упомянутыми проблемами были найдены лишь в недавнее время, и теперь (как в отношении приложений, так и в отношении лучшего понимания внутренней структуры проблем) приоритетом пользуется дальнейшее установление подобных связей.
Стоит отметить, далее, что разнообразие методов, применяемых для решения наших задач весьма велико, и это, конечно, также служит свидетельством актуальности темы. Среди таких методов и общие методы теории графов, и замечательный вероятностный метод в комбинаторике, и линейно-алгебраический метод в комбинаторике, и методы теории случайных графов, и топологические методы в геометрии, и аналитические методы, и пр., и пр.
Наконец, важно подчеркнуть, что в разное время близ-
кими задачами занимались В.Г. Болтянский, Л. Данцер, Н. Алон, Г.М. Циглер, В. Кли, Г. Калаи, X. Фюрстенберги многие другие известные математики. Ежегодно в мире проводятся конференции и семинары по этим задачам, им посвящены специализированные журналы. Публикуются обзоры и монографии.
В заключение разумно выделить наиболее актуальные и приоритетные направления в задачах. Итак, во-первых, несомненный интерес представляет усиление нижних и верхних оценок на перечисленные выше экстремальные характеристики в проблемах Борсука, Нелсона - Эрдеша - Хадви-гера и Грюнбаума. Во-вторых, огромную значимость имеет получение результатов для дискретных аналогов этих характеристик, определяемых на многогранниках и конечных геометрических графах (эта область деятельности особенно популярна в последние годы). В-третьих, продолжают быть важными и любые продвижения в вопросах, связанных с " малыми’' размерностями.
Цель и задачи исследования. Основной целью исследования является получение многочисленных результатов относительно проблем Борсука, Нелсона - Эрдеша - Ха-двигера и Грюнбаума. Кроме того, мы преследуем цель единого описания этих задач в терминах общих методов их решения и отыскания новых взаимосвязей между проблемами. Основными задачами являются следующие: разработка линейно-алгебраического метода и его применение к получению различных новых нижних оценок для числа Борсука и хроматических чисел метрических пространств, введенных Нелсоном, Эрдешом и Хадвигером; построение мс-
то да альтернирования, его применение к доказательству нетривиальных нижних оценок на хроматические числа конечных геометрических графов, а также приложение метода к усилению неравенств, которым удовлетворяют числа Бор-сука и Нелсона - Эрдеша - Хадвигера; разработка метода покрытия с зацеплением и применение этого метода для получения новых верхних оценок на минимальное число частей меньшего диаметра в оптимальном разбиении многогранника с заданной координатной структурой вершин (скажем, (0,1) - многогранника, кросс-политопа и пр.) и на минимальное число шаров того же диаметра в оптимальном покрытии аналогичного множества; обосновние новых нижних оценок на хроматические числа метрических пространств в малых размерностях; построение метода, позволяющего максимально эффективно работать с проблемой Борсука в малых размерностях - как при оптимальном разбиении произвольных множеств на меньшие части, так и в случае, когда множества суть кросс-политопы; отыскание теоретиковероятностных асимптотических характеристик поведения хроматических чисел конечных геометрических графов путем вложения в них случайного графа и исследования предельных распределений тех или иных соответствующих величин.
Научная новизна полученных результатов. Все результаты диссертации являются новыми. Более того, новыми являются не только сами результаты, но и методы их обоснования. Таковы методы альтернирования и покрытия с зацеплением; линсйно-алгебраичсский метод нетривиально доработан и существенно видоизменен.
Практическая значимость полученных результатов. Диссертация носит теоретический характер. Методы, разработанные в ней, могут быть полезными как при дальнейшем исследовании задач Борсука, Нелсона - Эрдеша -Хадвигера и Грюнбаума, так и при работе с хроматическими числами различных графов общего вида, и при изучении комбинаторных свойств многогранников, имеющих заданную координатную структуру множества вершин, и, вообще, при работе с многими вопросами комбинаторной и дискретной геометрии. В то же время наглядность результатов позволяет весьма эффективно внедрять их в учебный процесс - в рамках специальных курсов и специальных семинаров.
Основные положения диссертации, выносимые на защиту.
1. Для хроматического числа вещественного евклидова пространства получена оценка х(^) > (1-239... 4- 0(1))** (теорема 2.2.1.2 из параграфа 2.2.1).
2. Для хроматического числа рационального евклидова пространства получена оценка х(С}^) > (1.173...+ 0(1))** (теорема 2.2.1.3 и замечание 2.2.1.1 из параграфа 2.2.1).
3. Найдена оценка х((^Д1)>&) > (1.365... + 0(1)) , верная для хроматических чисел пространств (^,/1) и (С^^,/1), коль скоро запрещенное расстояние Ь Е И и Ь € С}, соответственно (теорема 2.2.1.5 из параграфа 2.2.1).
4. Имеет место неравенство > (1 +£ + о(1))</,
£ = е(д) > 0 (теорема 2.2.1.6 из параграфа 2.2.1).
17
5. Для максимального значения хроматического числа вещественного евклидова пространства с двумя запрещенными расстояниями выполнена оценка ^((НЛЬ),2) > (1.439... + о(1))^ (теорема 2.2.2.1 из параграфа 2.2.2).
6. Для максимального значения хроматического числа вещественного пространства с метрикой 1Ч и с & запрещенными расстояниями выполнена оценка х((КЛ/9),£) > (слк)ы, С1,С2 > 0 (теорема 2.2.2.2 из параграфа 2.2.2).
7. Для хроматических чисел геометрических графов с вершинами в точках, имеющих координаты -1, О, 1, получены серии нетривиальных нижних оценок (теоремы
3.3.1.1 - 3.3.1.4 из параграфа 3.3.1).
8. Для хроматических чисел геометрических графов с вершинами в точках, имеющих координаты -2,-1, О, 1, 2, получены серии нетривиальных нижних оценок (теоремы
3.3.2.1 - 3.3.2.4 из параграфа 3.3.2).
9. Для хроматических чисел геометрических графов с вершинами в точках, имеющих произвольные целочисленные координаты, получены серии нетривиальных нижних оценок (теоремы 3.3.3.1, 3.3.3.2 из параграфа 3.3.3).
10. Результаты пунктов 7, 8, 9 обобщены на случай геометрических графов с к запрещенными расстояниями (теорема 3.6.1 из параграфа 3.6).
11. Для суммы чисел Борсука и Нелсона - Эрдеша - Хадви-гера получена оценка/4-х > 1.2255... +1.239...+£, 8 > О (теорема 3.6.2.1 из параграфа 3.6.2).
18
12. В проблеме Борсука найдены новые верхние оценки для минимального количества частей меньшего диаметра, на которые разбивается произвольный многогранник с заданной арифметической структурой координат вершин. Отдельно исследованы случаи (0,1) - многогранников и кросс-политопов (теоремы 4.3.2.1 - 4.3.2.3 из параграфа 4.3.2, теоремы 4.3.3.1 - 4.3.3.3 из параграфа
4.3.3 и теорема 4.3.4.1 из параграфа 4.3.4).
13. В проблеме Грюнбаума найдены новые верхние оценки для минимального количества шаров того же диаметра, которыми покрывается произвольный многогранник с заданной арифметической структурой координат вершин. Отдельно исследованы случаи (0,1) - многогранников и кросс-политопов (теоремы 4.3.2.4, 4.3.2.5 из параграфа 4.3.2, теоремы 4.3.3.4 - 4.3.3.6 из параграфа 4.3.3 и теорема 4.3.4.2 из параграфа 4.3.4).
14. Результаты предыдущего пункта обобщены на случай покрытия многогранников шарами в произвольной норме (теорема 4.7.1 из параграфа 4.7).
15. В размерностях (I. = 6,7,9 и с1 = 11 найдены новые нижние оценки на хроматические числа пространств Л** и С(теоремы 5.2.1 - 5.2.4 из параграфа 5.2).
16. В проблеме Борсука предложены новые оптимальные разбиения трехмерных множеств на части меньшего диаметра (параграф 6.2 и предложение 6.3.1 из параграфа 6.3).
19
17. Изучены разбиения кросс-политопов в малых размерностях (предложение 6.4.1).
18. Исследованы вероятностные характеристики, связанные с вложением случайных графов в геометрические (теоремы 7.2.2.1 - 7.2.2.3 из параграфа 7.2.2 и теорема 7.3.2.1 из параграфа 7.3.2).
Личный вклад соискателя. Все результаты диссертации получены соискателем самостоятельно.
Апробация результатов. Результаты диссертации неоднократно докладывались на многочисленных международных конференциях и семинарах.
Перечислим сперва конференции: международная конференция “Современные проблемы теории чисел и ее приложения" (г. Тула, 1996 г.); вторая международная конференция “Алгебра, геометрия и комбинаторика” в Порту (Португалия, 1998 г.); международная конференция ’’Алгебраическая теория чисел и диофантовы приближения” в Граце (Австрия, 1998 г.); третья международная конференция "Алгебра, геометрия и комбинаторика" в Порту (Португалия, 1999 г.); международная конференция, посвященная памяти П. Эрдеша, в Будапеште (Венгрия, 1999 г.); международная конференция "XXI Арифметические дни" в Риме (Италия, 1999 г.); международная конференция "Решетки, многогранники и разбиения" в Обервольфахе (Германия, 2000 г.); международная конференция, посвященная Кли и Грюнбауму, в Эйн - Геве (Израиль, 2000 г.); международная конференция "Конференция по теории чисел, посвященная смене тысячелетий" в Эрбане (США, 2000 г.);
международная конференция "Теория графов, комбинаторика, алгоритмы и приложения" в Каламазу (США, 2000 г.); международная конференция "Дискретная и вычислительная геометрия” в Анойе (Греция, 2000 г.); международная конференция "Современные проблемы теории чисел и ее приложения” (г. Тула, 2001 г.); международная конференция по дискретной геометрии, посвященная семидесятилетию С.С. Рышкова (г. Москва, 2001 г.); международная конференция "Дискретная, комбинаторная и вычислительная геометрия” в Пекине (Китай, 2002 г.); международная конференция "Современные проблемы теории чисел и ее приложения" (г. Тула, 2003 г.); международная конференция "Диофантовы приближения и равномерное распределение" в Минске (Беларусь, 2003 г.); международный семинар по дискретной математике (г. Москва, 2004 г.); Ломоносовские чтения в Московском государственном университете в 1999, 2002, 2003 гг.
Перечислим теперь семинары: кафедральный семинар кафедры теории чисел механико - математического факультета МГУ под руководством проф. А.Б. Шидловского, чл. - корр. РАН Ю.В. Нестеренко и д.ф.-м.н. Н.Г. Мощеви-тина; кафедральный семинар кафедры математической статистики и случайных процессов механико - математического факультета МГУ под руководством акад. РАН В.В. Козлова; семинар под руководством акад. РАН О.Б. Лупанова в МГУ; семинары д.ф.-м.н. Н.Г. Мощевитина и д.ф.-м.н. Н.П. Долбилина в МГУ; семинар проф. С.В. Конягина в МГУ; семинар проф. С.С. Рышкова в МГУ; семинар проф. И.Х. Сабитова в МГУ; семинар к.ф.-м.н. С.П. Тарасова и чл. - корр. РАН A.A. Разборова в Вычислительном Центре при России-
ской Академии Наук; семинар д.ф.-м.н. Н.М. Добровольского в Тульском Государственном Педагогическом Университете; семинар проф. А. Шницеля в Варшаве (Польша, 1999 г.); семинар проф. Р. Тихого в Граце (Австрия, 1999 г.); семинар проф. Г.М. Циглера в Берлине (Германия, 1999 г.); семинар проф. И. Барани в Будапеште (Венгрия, 2000 г.); семинар проф. Л. Сскей в Коламбии (США, 2001 г.); семинар проф. Д. Лармана в Лондоне (Великобритания, 2001 г.); семинар проф. И. Лидера в Кембридже (Великобритания, 2001 г.); коолоквиум факультета математики университета Корнелл в Итаке (США, 2001 г.); семинар проф. Р. Эрдала в Кингстоне (Канада, 2001 г.); коллоквиум факультета математики Лондонской Школы Экономики (Великобритания, 2001 г.); семинар факультета математики Университета Бордо (Франция, 2001 г.); семинар проф. В. Кли в Сиэтле (США, 2003 г.); семинар проф. М. Сенешаль в • Нортхэмптоне (США, 2003 г.); семинар проф. Р. Поллака в
Нью Йорке (США, 2004 г.).
Опубликованность результатов диссертации. Результаты диссертации опубликованы соискателем в работах [138] - [168] списка использованных источников. Всего по теме диссертации опубликована 31 работа, среди которых одна научно - популярная брошюра.
Структура и объем диссертации. В диссертации имеется введение, общая характеристика работы, список использованных обозначений и сокращений, 7 глав, список использованных источников. Полный объем 289 с., из них 19 с. занимает список использованных источников (168 наименований).
22
#
Список использованных обозначений
• d,n - размерность пространства;
• R<y - d - мерное вещественное (как правило, евклидово) пространство;
• Q'*' - d - мерное рациональное (как правило, евклидово) пространство;
• х = (#1,... ,Xd) - вектор;
• е/(х.у) = |х—у| = h{x,y) - евклидово расстояние между векторами х,у;
• (х.у) =< х,у > - скатярное произведение в евклидовом пространстве;
• 1Ч, q > 1, - гёльдерова метрика;
• (Х,г) - произвольное метрическое пространство с метрикой г(х,у), где х.гу Є X; например, (Я-, г) = (Rrf,/2), (ЛГ, г) = (QЛл^д) и т.д.;
• f(d),f - числа Борсука;
• y(d) - число Грюнбаума;
• G = (V,E) или G = (V,£) и пр. - графы с множествами вершин V, V и ребер £,£;
• x{G) - хроматическое число графа G;
• c*{G) - число независимости графа G;
23
• u>(G) - количество вершин в максимальной клике графа
О;
• x(RJ) = х{№1 J2), а) - хроматическое число вещественного евклидова пространства с запрещенным (критическим) расстоянием а;
• X(Q<f) = X'UQ^М>а) " хроматическое число рационального евклидова пространства с запрещенным (критическим) расстоянием a G Q;
• \((Х, г),а.)) - хроматическое число метрического пространства (X, г) с запрещенным (критическим) расстоянием а;
• X((-Y, г), йь • • •»Ok) - хроматическое число метрического пространства (X, г) с запрещенным (критическим) набором расстояний а 1,.... а*;
• X((-Y, г), к) = maxtx((X,r),ai,
• X - число Хадвигера;
• 'Rrf - произвольное множество из d элементов;
• с.о.п. - система общих представителей;
• т(Л4) - мощность минимальной с.о.п. для совокупности множеств М С 2**;
• card М - мощность множества М\
• diam М - диаметр множества М;
• conv М - выпуклая оболочка множества М;
Сьа — (і) - биномиальный коэффициент; а^> Ь ~ существует константа с > 0: а > сЬ; а Ь - существует константа с> 0: а < сЬ; а X 6 - значит, а > 6 и а < 6;
[я], {#} - как правило, целая часть и дробная доля числа
С(п,р) - случайный граф (пространство);
- А* - ый момент случайной величины £;
М/£*’ - А: - ый факториальный момент случайной величины
- дисперсия случайной величины
1 Глава. Исторический обзор
1.1 Постановки задач
В 1933 году К. Борсук (см. [1]) высказал гипотезу о том, что всякое ограниченное d - мерное точечное множество Q С Rrf, имеющее ненулевой диаметр, может быть разбито на d -h 1 часть меньшего диаметра:
Q = |_1* • ‘U^rf+b diamllj < diam Q V i = 1,... yd + 1.
(Здесь под диаметром множества 11 понимается величина
diam О = sup d(x, у),
х.убО
где, в свою очередь, d(x,y) - стандартная евклидова метрика.)
Немного позднее, в 1944 году, Г. Хадвигер (см. [2]) показал, что если все евклидово пространство Kd произвольным образом покрыто замкнутыми множествами, число которых в точности равно d 4-1, то хотя бы в одном из этих множеств все неотрицательные вещественные числа реализуются как расстояния между парами точек этого множества. Иными словами, если
R‘' = n,U..-U<Wi
и все множества 17, замкнутые, то найдется такое г, что
R+U{°} = Мх>у) : х-у е й»}-
Дааее, усилиями Е. Нелсона, Дж.Р. Исбела, П. Эрдеша и Г. Хадвигера была сформулирована следующая проблема