Проблемы Борсука, Нелсона-Эрдеша-Хадвигера и Грюнбаума в комбинаторной геометрии тема диссертации и автореферата по ВАК РФ 01.01.09, доктор физико-математических наук Райгородский, Андрей Михайлович

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

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

Введение

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

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

1 Глава. Исторический обзор

1.1 Постановки задач.

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

1.2.1 Проблема Борсука в "малых" размерностях

1.2.2 Проблема Борсука для некоторых специальных классов множеств.

1.2.3 Верхние оценки на минимальное число частей меньшего диаметра.

1.2.4 Контрпримеры к гипотезе Борсука и нижние оценки на минимальное число частей меньшего диаметра.

1.3 Хроматические числа некоторых метрических пространств.

1.3.1 Общая постановка задачи

1.3.2 Некоторые предварительные замечания

1.3.3 Оценки хроматических чисел в " малых" размерностях.

1.3.4 Оценки хроматических чисел с ростом размерности и реализация всех расстояний при разбиении пространства И/* на некоторое число частей.

1.4 Проблема Грюнбаума.

2 Глава. Линейно-алгебраический метод.

Нижние оценки в задачах Борсука и

Нелсона - Эрдеша - Хадвигера

2.1 Несколько общих замечаний.

2.2 Формулировки результатов.

2.2.1 Проблема Борсука и хроматические числа некоторых метрических пространств

2.2.2 Одно обобщение задачи Нелсона - Эрдеша - Хадвигера.

2.3 Доказательства результатов.

2.3.1 Общее описание подхода.

2.3.2 Доказательство теоремы 2.2.1.1.

2.3.3 Доказательство теоремы 2.2.1.2.

2.3.4 Доказательства теорем 2.2.1.3 и 2.2.1.

2.3.5 Доказательство теоремы 2.2.1.5.

2.3.6 Доказательство теоремы 2.2.1.6.

2.3.7 Доказательство теорем 2.2.2.1 и 2.2.2.

2.3.8 Несколько дополнительных наблюдений

2.4 Еще несколько результатов.

2.4.1 Системы векторов с запретами на скалярные произведения.

2.4.2 О связи между задачами Борсука и Нелсона - Эрдеша - Хадвигера.

2.4.3 Доказательство теоремы 2.4.1.1.

2.4.4 Доказательство теоремы 2.4.2.1.

2.5 Краткое резюме метода.

3 Глава. Метод альтернирования. Хроматические числа конечных геометрических графов

3.1 Несколько общих замечаний.

3.2 Постановки задач.

3.3 Формулировки результатов.

3.3.1 (-1,0,1) - задача

3.3.2 (-2,-1,0,1,2) - задача.

3.3.3 Общий случай в задаче.

3.4 Доказательства результатов.

3.4.1 Небольшое напоминание (общие предпосылки)

3.4.2 Доказательство теоремы 3.3.1.2.

3.4.3 Доказательство теоремы 3.3.1.3.

3.4.4 Доказательство теоремы 3.3.1.4.

3.4.5 Доказательства теорем 3.3.2.1 - 3.3.2. и 3.3.3.1, 3.3.3.2.

3.5 Соотношения между полученными результатами.

3.6 Еще несколько результатов.

Введение диссертации (часть автореферата) на тему «Проблемы Борсука, Нелсона-Эрдеша-Хадвигера и Грюнбаума в комбинаторной геометрии»

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

Термин "комбинаторная геометрия", разумеется, намного моложе самого предмета. Довольно трудно сейчас определить, кто первым ввел его в оборот, и на сей счет существуют различные мнения. Одним из наиболее признанных "авторов" термина является, по-видимому, замечательный геометр Г. Хадвигер, который в 1955 году использовал его в своих работах [121], [122]. Нелепо, однако же, думать, что 1955 год можно считать датой основания комбинаторной геометрии как определенной выше дисциплины и как совокупности соответствующих задач. В то же время понятно, что наука, имя которой было придумано лишь около полувека назад, не может быть слишком старой. По крайней мере, вряд ли она могла сформироваться в единое целое, скажем, более ста лет назад. В сущности, так оно и есть: хотя дату возникновения науки указать еще труднее, чем момент ее самоидентификации, да и, более того, было бы странно надеяться на отыскание сколь-нибудь осмысленной точки отсчета, но с известной долей уверенности можно утверждать, что фундамент для будущей многогранной и плодотворной деятельности был заложен на рубеже XIX и XX веков.

В действительности, проще объяснять суть предмета, двигаясь не от общего к частному, а в обратном направлении. Иными словами, гораздо естественнее попытаться перечислить хотя бы те классические задачи, которые легли в основу науки и которые в максимальной степени стимулировали дальнейшее ее развитие. Наиболее интересную для нас группу таких задач образуют три проблемы - проблема К. Бор-сука (см., например, [1], [8], [11], [24], [141]) о разбиении множеств на части меньшего диаметра, проблема Е. Нелсона - П. Эрдеша - Г. Хадвигера (см., например, [2], [66], [141], [152]) о раскраске метрических пространств и проблема Б. Грюнбаума (см., например, [5]) о покрытии множеств шарами того же диаметра. К этой группе следует добавить также задачу Хадвигера - Маркуса - Гохберга - Болтянского (см. [8], [24], [123]) об освещении границы выпуклого тела минимальным количеством направлений и задачи, связанные с теоремой Хелли (см., например, [5], [118], [119]). Каждая из этих задач, будучи, безусловно, жемчужиной комбинаторной геометрии, является классической и в самом широком контексте. Популярность этих задач не вызывает никаких сомнений: так, в разные годы ими занимались столь замечательные специалисты в области дискретной геометрии и комбинаторики, как Хелли, Юнг, Борсук, Эрдеш,

Грюнбаум, Кли, Роджерс, Ларман, Болтянский, Ленц, Гэйл, Данцер, Бургейн, Калаи, Алон, Циглер и др. И это тем более удивительно и показательно, если учесть, что проблема Борсука была поставлена в 1933 году, проблема Нелсона -Эрдеша - Хадвигера - в 1950, проблема Грюнбаума - в 1957, проблема Хадвигера - Маркуса - Гохберга - Болтянского -в конце 50-ых и лишь проблема Хелли - в десятые годы XX века.

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

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

Диссертация делится на семь глав. В первой главе даются постановки основных проблем и подробно излагается их история. Во второй главе в деталях разрабатывается линейно-алгебраический метод исследования задач Борсука и Нелсона - Эрдеша - Хадвигера. Этот метод применяется к получению самых сильных нижних оценок на так называемое число Борсука и на хроматические числа различных метрических пространств. При этом в его рамках прослеживается нетривиальная связь между задачами. Третья глава посвящена построению "метода альтернирования", который, вбирая в себя значительную часть техники первой главы, является нетривиальной надстройкой над этой техникой, помогающей добиться новых важных продвижений в вопросах получения нижних оценок на хроматические числа конечных геометрических графов и на числа Борсука и Нелсона - Эрдеша - Хадвигера. В четвертой главе разрабатывается еще один новый метод, который мы назвали "методом покрытия с зацеплением". В отличие от первых двух, он позволяет установить глубокую связь между результатами относительно проблем Борсука и Грюнбаума. При этом метод применен к весьма обширному классу задач, касающихся разбиения многогранников на части меньшего диаметра и покрытия их шарами того же диаметра. Верхние оценки на минимальное число подобных частей и шаров оказываются существенно сильнее всех известных прежде. Более того, в конце главы дается приложение метода и к отысканию наилучших верхних оценок на хроматические числа конечных геометрических графов. В пятой главе доказываются новые нижние оценки на хроматические числа некоторых "маломерных" пространств. В шестой главе разрабатывается тонкая геометрическая техника, позволяющая уточнять все прежние результаты относительно оптимального разбиения множеств в размерности 3. Наконец, в седьмой главе осуществляется исследование задачи Нелсона - Эрдеша - Хадви-гера с теоретико-вероятностной точки зрения. А именно, предлагается техника вложения случайного графа в геометрический, и на ее основе изучается поведение хроматического числа пространства "почти наверное".

Благодарности. Соискатель считает своим приятным долгом в первую очередь поблагодарить д.ф.-м.н. Н.Г. Мо-щевитина за постоянный интерес и внимание к его работе. Соискатель также благодарит д.ф.-м.н. Н.П. Долбилина и проф. C.B. Конягина за неоднократную помощь и поддержку

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

Актуальность темы диссертации. В работе подробно исследуются три глубоко связанные между собой классические проблемы современной комбинаторной геометрии. Первая из них - проблема Борсука - была сформулирована ровно 70 лет назад (см. [1]), и за прошедшие годы она, безусловно, сделалась ключевой в области дискретной геометрии и комбинаторики: с одной стороны, любое продвижение в ней вызывает мощный международный резонанс, а с другой стороны, она служит естественным катализатором возникновения новых идей и направлений в рамках соответствующего раздела науки. Говоря кратко, она состоит в определении минимального числа частей меньшего диаметра, на которые может быть разбито произвольное ограниченное множество в пространстве. Уже из такой постановки понятно, что должна существовать нетривиальная взаимосвязь проблемы с известными и весьма приоритетными задачами разбиений и упаковок в пространствах - задачами, несомненно, важными как с фундаментальной, так и с прикладной точек зрения. И действительно, эта взаимосвязь отслеживается в многочисленных работах таких специалистов в дискретной геометрии, геометрии чисел и комбинаторике, как К.А. Роджерс (см. [79]), Р. Ранкин (см. [80]), Ж. Бургейн и И. Линденштраусс (см. [30]) и др. Более того, деятельность, относящаяся к отысканию верхних оценок на упомянутое минимальное число в проблеме, имеет выход и на задачи нахождения столь значимых аналитических характеристик, как, например, Колмогоровская энтропия. Здесь следует сразу же сослаться и на третью проблему из числа рассматриваемых в диссертации. Это так называемая проблема Грюнбаума (см. [5]), возникшая в середине пятидесятых годов XX столетия и состоящая в изучении минимального количества равных шаров, которыми покрывается произвольное множество в пространстве. Связь между проблемами Борсука и Грюнбаума очевидна, а соотношение последней и перечисленных выше классических вопросов геометрии чисел и анализа еще более прозрачно, чем это было в случае проблемы Борсука. Возвращаясь к последней, стоит дополнительно сказать, что она также имеет тонкие связи с задачами топологии и теории размерности: по-видимому, для самого Борсука возможность отыскания приложений в этих областях и послужила основной мотивировкой вопроса.

Вторая проблема, изучаемая нами в работе, принадлежит нескольким авторам, из которых наибольшую роль в ее становлении сыграли Э. Нелсон, П. Эрдеш и Г. Хадвигер (см.

2], [4], [141]). Проблема сводится к нахождению наименьшего количества цветов, необходимых для такой раскраски метрического пространства, при которой между точками одного цвета не может быть некоторого фиксированного заранее расстояния. Ей также больше 50-и лет, и ее популярность огромна. Во-первых, ясно, что практически все связи, приведенные нами при обсуждении проблем Борсука и Грюнбаума, актуальны и для нее: более того, с точки зрения разбиений и упаковок пространств она даже интереснее, так как в ней разрабатывается техника, относящаяся к так называемым разбиениям Вороного и имеющая непосредственный выход на замечательные статьи [70], [71], [63] и др. Во-вторых, она в значительной мере связана с различными важными задачами теории графов, в том числе и случайных.

На самом деле, особенно тонкие и нетривиальные связи между тремя упомянутыми проблемами были найдены лишь в недавнее время, и теперь (как в отношении приложений, так и в отношении лучшего понимания внутренней структуры проблем) приоритетом пользуется дальнейшее установление подобных связей.

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

Наконец, важно подчеркнуть, что в разное время близкими задачами занимались В.Г. Болтянский, Л. Данцер, Н. Алон, Г.М. Циглер, В. Кли, Г. Калаи, X. Фюрстенберг и многие другие известные математики. Ежегодно в мире проводятся конференции и семинары по этим задачам, им посвящены специализированные журналы. Публикуются обзоры и монографии.

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

Цель и задачи исследования. Основной целью исследования является получение многочисленных результатов относительно проблем Борсука, Нелсона - Эрдеша - Ха-двигера и Грюнбаума. Кроме того, мы преследуем цель единого описания этих задач в терминах общих методов их решения и отыскания новых взаимосвязей между проблемами. Основными задачами являются следующие: разработка линейно-алгебраического метода и его применение к получению различных новых нижних оценок для числа Борсука и хроматических чисел метрических пространств, введенных Нелсоном, Эрдешом и Хадвигером; построение мето да альтернирования, его применение к доказательству нетривиальных нижних оценок на хроматические числа конечных геометрических графов, а также приложение метода к усилению неравенств, которым удовлетворяют числа Бор-сука и Нелсона - Эрдеша - Хадвигера; разработка метода покрытия с зацеплением и применение этого метода для получения новых верхних оценок на минимальное число частей меньшего диаметра в оптимальном разбиении многогранника с заданной координатной структурой вершин (скажем, (0,1) - многогранника, кросс-политопа и пр.) и на минимальное число шаров того же диаметра в оптимальном покры-тиии аналогичного множества; обосновние новых нижних оценок на хроматические числа метрических пространств в малых размерностях; построение метода, позволяющего максимально эффективно работать с проблемой Борсука в малых размерностях - как при оптимальном разбиении произвольных множеств на меньшие части, так и в случае, когда множества суть кросс-политопы; отыскание теоретико-вероятностных асимптотических характеристик поведения хроматических чисел конечных геометрических графов путем вложения в них случайного графа и исследования предельных распределений тех или иных соответствующих величин.

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

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

Основные положения диссертации, выносимые на защиту.

1. Для хроматического числа вещественного евклидова пространства получена оценка хС^) > (1.239. + 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. + »(1))^, верная для хроматических чисел пространств (IV1,1\) и (С^,/1), коль скоро запрещенное расстояние Ь £ К и Ь £ С^, соответственно (теорема 2.2.1.5 из параграфа 2.2.1).

4. Имеет место неравенство Щ > (1 + г + 0(1))*, £ = е(д) > 0 (теорема 2.2.1.6 из параграфа 2.2.1).

5. Для максимального значения хроматического числа вещественного евклидова пространства с двумя запрещенными расстояниями выполнена оценка 2) > (1.439. + о{l))d (теорема 2.2.2.1 из параграфа 2.2.2).

6. Для максимального значения хроматического числа вещественного пространства с метрикой lq и с к запрещенными расстояниями выполнена оценка x((Rd, /д), к) > (cik)C2d, ci,c2 > 0 (теорема 2.2.2.2 из параграфа 2.2.2).

7. Для хроматических чисел геометрических графов с вершинами в точках, имеющих координаты -1, 0, 1, получены серии нетривиальных нижних оценок (теоремы 3.3.1.1 - 3.3.1.4 из параграфа 3.3.1).

8. Для хроматических чисел геометрических графов с вершинами в точках, имеющих координаты-2,-1, 0, 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. Для суммы чисел Борсука и Нелсона - Эрдеша - Хадви-гера получена оценка/ + х > 1.2255.+ 1.239.+<£,<£ >0 (теорема 3.6.2.1 из параграфа 3.6.2).

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. В размерностях {/ = 6,7,9и{/ = 11 найдены новые нижние оценки на хроматические числа пространств В/* и С^ (теоремы 5.2.1 - 5.2.4 из параграфа 5.2).

16. В проблеме Борсука предложены новые оптимальные разбиения трехмерных множеств на части меньшего диаметра (параграф 6.2 и предложение 6.3.1 из параграфа 6.3).

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 гг.

Перечислим теперь семинары: кафедральный семинар кафедры теории чисел механико - математического факультета МГУ под руководством проф. А.Б. Шидловского, чл. - корр. РАН Ю.В. Нестеренко и д.ф.-м.н. Н.Г. Мощеви-тина; кафедральный семинар кафедры математической статистики и случайных процессов механико - математического факультета МГУ под руководством акад. РАН В.В. Козлова; семинар под руководством акад. РАН О.Б. Лупанова в МГУ; семинары д.ф.-м.н. Н.Г. Мощевитина и д.ф.-м.н. Н.П. Долбилина в МГУ; семинар проф. C.B. Конягина в МГУ; семинар проф. С.С. Рышкова в МГУ; семинар проф. И.Х. Сабитова в МГУ; семинар к.ф.-м.н. С.П. Тарасова и чл. - корр. РАН A.A. Разборова в Вычислительном Центре при Российской Академии Наук; семинар д.ф.-м.н. Н.М. Добровольского в Тульском Государственном Педагогическом Университете; семинар проф. А. Шинцеля в Варшаве (Польша, 1999 г.); семинар проф. Р. Тихого в Граце (Австрия, 1999 г.); семинар проф. Г.М. Циглера в Берлине (Германия, 1999 г.); семинар проф. И. Барани в Будапеште (Венгрия, 2000 г.); семинар проф. Л. Секей в Коламбии (США, 2001 г.); семинар проф. Д. Лармана в Лондоне (Великобритания, 2001 г.); семинар проф. И. Лидера в Кембридже (Великобритания, 2001 г.); коолоквиум факультета математики университета Корнелл в Итаке (США, 2001 г.); семинар проф. Р. Эрдала в Кингстоне (Канада, 2001 г.); коллоквиум факультета математики Лондонской Школы Экономики (Великобритания, 2001 г.); семинар факультета математики Университета Бордо (Франция, 2001 г.); семинар проф. В. Кли в Сиэтле (США, 2003 г.); семинар проф. М. Сенешаль в Нортхэмптоне (США, 2003 г.); семинар проф. Р. Поллака в Нью Йорке (США, 2004 г.).

Опубликованность результатов диссертации. Результаты диссертации опубликованы соискателем в работах [138] - [168] списка использованных источников. Всего по теме диссертации опубликована 31 работа, среди которых одна научно - популярная брошюра.

Структура и объем диссертации. В диссертации имеется введение, общая характеристика работы, список использованных обозначений и сокращений, 7 глав, список использованных источников. Полный объем 289 е., из них 19 с. занимает список использованных источников (168 наименований).

Список использованных обозначений с/, п - размерность пространства;

Кё ~ с1 - мерное вещественное (как правило, евклидово) пространство;

С^ - с/ - мерное рациональное (как правило, евклидово) пространство; х = (а?!,., хл) - вектор; х,у) = |х —у| = /г(х,у) - евклидово расстояние между векторами х, у; х,у) =< х,у > - скалярное произведение в евклидовом пространстве;

Я > - гёльдерова метрика;

X, г) - произвольное метрическое пространство с метрикой г(х,у), где х,у Е X] например, (X,г) = (П6',/2), (Х,г) = (С}<111^д) и т.д.; г/), / - числа Борсука; д(в) - число Грюнбаума;

О = {У,Е) или 0 = (V, Е) и пр. - графы с множествами вершин V, V и ребер Е,£; х{0) - хроматическое число графа О] а(С?) - число независимости графа G; u>(G) - количество вершин в максимальной клике графа

G; а) - хроматическое число вещественного евклидова пространства с запрещенным (критическим) расстоянием а;

X(Qd) = x((Qd, ¿2), а) - хроматическое число рационального евклидова пространства с запрещенным (критическим) расстоянием а £ Q;

Х,г),а)) - хроматическое число метрического пространства (X, г) с запрещенным (критическим) расстоянием а;

Х((Х, г), а 1,., o,k) - хроматическое число метрического пространства (X, г) с запрещенным (критическим) набором расстояний ai,.,

Х{{Х,г),к) = maxx((X,r),ab.,ajfc); X - число Хадвигера;

Ш-d - произвольное множество из d элементов; с.о.п. - система общих представителей; т(Л4) - мощность минимальной с.о.п. для совокупности множеств Л4 С 2^; card М - мощность множества М; diam М - диаметр множества М; conv М - выпуклая оболочка множества М;

Сьа = (£) - биномиальный коэффициент; а Ь - существует константа с > 0: а > сб; а< 6 - существует константа с > 0: а < сЬ; а^Ь - значит, а > & и а < 6; ж], {ж} - как правило, целая часть и дробная доля числа ж; п,р) - случайный граф (пространство);

М£к -к - ый момент случайной величины £;

- к - ый факториальный момент случайной величины

Х)£ - дисперсия случайной величины £;

Список литературы диссертационного исследования доктор физико-математических наук Райгородский, Андрей Михайлович, 2004 год

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

2. H. Hadwiger, Ein Uberdeckungssatz für den Euklidischen Raum, Portugaliae Math., 4 (1944), 140 144.

3. A. Soifer, Chromatic number of the plane: a historical essay, Geombinatorics (1991), 13 15.

4. A. Soifer, Mathematical coloring book, Center for Excellence in Mathematical Education, 1997.

5. JI. Данцер, Б. Грюнбаум и В. Кли, Теорема Хелли, Москва, "Мир", 1968.

6. Г. Хадвигер и Г. Дебруннер, Комбинаторная геометрия плоскости, М., "Наука", 1965.

7. К. Borsuk, Uber die Zerlegung einer Euklidischen n di-mensionalen Vollkugel in n Mengen, Verh. Internat Math. Kongr., Zürich, 2 (1932), 192.

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

9. JI.A. Люстерник и Л.Г. Шнирельман, Топологические методы в вариационных задачах, М., 1930.

10. Н. Lenz, Zur Zerlegung von Punktmengen in solche kleineren Durchmessers, Archiv Math., 6 (1955), N5, 413 416.

11. И.M. Яглом и В.Г. Болтянский, Выпуклые фигуры, Гостехиздат, М., 1951.

12. J. Pál, Uber ein elementares Variationsproblem, Danske Videnskab. Selskab., Math.-Fys. Meddel 3 (1920), N2.

13. H.G. Eggleston, Covering a three-dimensional set with sets of smaller diameter J. London Math. Soc. 30 (1955), 11 24.

14. J. Perkal, Sur la subdivision des ensembles en parties de diamètre inférieur, Colloq. Math., 1 (1947), 45.

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

16. D. Gale, On inscribing n-dimensional sets in a regular n-simplex, Proc. Amer. Math. Soc., 4 (1953), 222 225.

17. A. Heppes, Térbeli ponthalmazok felosztása kisebb átmérojü részhalmazok osszegére, A magyar tudományos akadémia, 7 (1957), 413 416.

18. В.В.Макеев, Об аффинных образах ромбододекаэдра, описанных вокруг трехмерного выпуклого тела, Зап. научн. семин. ПОМИ 246 (1997), 191 195.

19. В.В. Макеев, Аффинно-вписанные и аффинно-описанные многоугольники и многогранники, Зап. научн. семин. ПОМИ 231 (1996), 286 298.

20. A. Heppes and P. Révész, Zum Borsukschen Zerteilungsproblem, Acta Math. Acad. Sci. Hung., 7 (1956), 159 162.

21. P. Erdös, On sets of distances of n points, Amer. Math. Monthly 53 (1946), 248 250.

22. H. Hadwiger, Uberdeckung einer Menge durch Mengen kleineren Durchmessers, Comm. Math. Helv. 18 (1945/46), 73 75; Mitteilung betreffend meine Note: Uberdeckung einer Menge durch Mengen kleineren Durchmessers, Comm. Math. Helv. 19 (1946/47), 72 - 73.

23. C.A. Rogers, Symmetrical sets of constant width and their partitions, Mathematika, 18 (1971), 105 111.

24. V.G. Boltyanski, H. Martini and P.S. Soltan, Excursions into combinatorial geometry, Universitext, Springer Verlag, Berlin Heidelberg 1997.

25. K. Borsuk, Some remarks on covering of bounded subsets of the Euclidean d space with sets of smaller diameter, Demonstratio Math., 11 (1978), 247 - 251.

26. M. Lassak, An estimate concerning Borsuk's partition problem, Bull. Acad. Polon. Sei. Ser. Math., 30 (1982), 449-451.

27. H.W.E. Jung, Uber die kleinste Kugel, die eine räumliche Figur einschliesst, J. reine und angew. Math., 123 (1901), 241 257.

28. R. Knast, An approximative theorem for Borsuk's conjecture, Proc. Cambridge Phil. Soc. (1974), N1, 75 76.

29. O. Schramm, Illuminating sets of constant width, Mathematika, 35 (1988), 180 189.

30. J. Bourgain and J. Lindenstrauss, On covering a set in Rd by balls of the same diameter, Geometric Aspects of Functional Analysis (J. Lindenstrauss and V. Milman, eds.), Lecture Notes in Math., 1469, Springer-Verlag, Berlin, 1991, 138 144.

31. P. Erdös, My Scottish book "problemsThe Scottish Book, Mathematics from the Scottish Cafe (R.D. Mauldin ed.), Birkhäuser, 1981, 35 43.

32. C.A. Rogers, Some problems in the geometry of convex bodies, The Geometric Vein The Coxeter Festschrift (C. Davis, B. Grünbaum, and F.A. Sherk, eds.), SpringerVerlag, New York, 1981, 279 - 284.

33. D. Larman, Open problem 6, Convexity and Graph theory (M. Rozenfeld and J. Zaks eds.), Ann. Discrete Math., 20, North Holland, Amsterdam and New - York, 1984, 336.

34. P. Frankl and R. Wilson, Intersection theorems with geometric consequences , Combinatorica, 1 (1981), 357 368.

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

36. A. Nilli, On Borsuk's problem , Contemporary Mathematics, 178 (1994), AMS, 209 210.

37. J. Grey und B. Weissbach, Ein weiteres Gegenbeispiel zur Borsukschen Vermutung, Univ. Magdeburg, Fakultät für Mathematik, Preprint 25, 1997.

38. В. Weissbach, Sets with large Borsuk number, Beiträge zur Algebra und Geometrie, 41 (2000), 417 423.

39. A. Hinrichs, Spherical codes and Borsuk's conjecture, Discrete Math., 243 (2002), 253 256.

40. O. Pikhurko, Borsuk's conjecture fails in dimensions 321 and 322, e-print: arXiv:math. CO/0202112, 2002.

41. A. Hinrichs and Ch. Richter, New sets with large Borsuk numbers, 2002, http://www.minet.uni-jena.de/ hinrichs / paper/18/borsuk.pdf.

42. M. Aigner and G.M. Ziegler, Proofs from THE BOOK, Springer-Verlag, Berlin, 1998.

43. В.Г. Болтянский, О разбиении плоских фигур на части меньшего диаметра, Colloq. Math. (Warszawa), 21 (1970), N2, 253 263.

44. В.Г. Болтянский, В.П. Солтан, Задача Борсука, Мат. заметки, 22 (1977), N5, 621 631.

45. В. Grünbaum, Borsuk's problem and related questions, Proc. Symp. Pure Math., 7 (1963), 271 284.

46. H. Croft, K. Falconer, and R. Guy, Unsolved problems in geometry, Springer-Verlag, New York, 1991, 123 125.

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

48. P.D. Johnson, Jr., Introduction to "Colorings of metric spaces", by Benda and Perles, Geombinatorics, 9 (2000), 110 112.

49. Ф. Харари, Теория графов, М., "Мир", 1973.

50. Р. Дистель, Теория графов, Новосибирск, Изд-во Инст. Мат., 2002.

51. N.G. de Bruijn and Р. Erdös, A colour problem for infinite graphs and a problem in the theory of relations, Proc. Koninkl. Nederl. Acad. Wet., Ser. A, 54 (1951), N5, 371 -373.

52. R. Rado, Axiomatic treatment of rank in infinite sets, Canad. J. Math., 1 (1949), 337 343.

53. L.A. Szekely, Measurable chromatic number of geometric graphs and sets without some distances in Euclidean space, Combinatorica, 4 (2 3) (1984), 213 - 218.

54. Дж. Шенфилд, Математическая логика, Москва, "Наука", 1975.

55. D.R. Woodall, Distances realized by sets covering the plane, J. Combin. Th. (A), 14 (1973), 187 200.

56. L. Moser and W. Moser, Solution to problem 10, Canad. Math. Bull., 4 (1961), 187 189.

57. H. Hadwiger, Ungelöste Probleme N 40, Elemente der Math., 16 (1961), 103 104.

58. Д.Е. Райский, Реалиизация всех расстояний при разбиении пространства R" на п+1 часть, Мат. заметки, 7 (1970), 319 323.

59. D. Coulson, On 18-colouring of 3-space omitting distance one, Discrete Math., 170 (1997), 241 247.

60. D. Coulson, A 15-colouring of 3-space omitting distance one, Discrete Math., 256 (2002), 83 90.

61. K.B. Chilakamarri, On the chromatic number of rational five-space, Aequationes Mathematicae, 39 (1990), 146 -148.

62. K.B. Chilakamarri, The unit-distance graph problem: a brief survey and some new results, Bull, of the ICA, 8 (1993), 39 60.

63. D.G. Larman and C.A. Rogers, The realization of distances within sets in Euclidean space, Mathematika, 19 (1972), 1 24.

64. J. Zaks, On the four-colourings of rational four-space, Aequationes Mathematicae (1989), 259 266.

65. J. Zaks, On the chromatic numbers of some rational spaces, Ars Combinatoria, 1992.

66. L.A. Székely, Erdos on unit distances and the Szemerédi -Trotter theorems, Paul Erdós and his Mathematics, Bolyai Series Budapest, J. Bolyai Math. Soc., Springer, 11 (2002), 649 666.

67. L.A. Székely, Erdos on unit distances and the Szemerédi Trotter theorems, Paul Erdós and his Mathematics, Abstracts of invited talks held in the memory of Paul Erdos, Budapest, Hungary, July 4 - 11, 1999.

68. D.G. Larman, A note on the realization of distances within sets in Euclidean space, Comment. Math. Helvet., 53 (1978), 529 535.

69. P. Frankl, Extremal problems and coverings of the space, European J. Combs., 1 (1980), 101 106.

70. G.J. Butler, Simultaneous packing and covering in Euclidean space, Proc. Lon. Math. Soc., Ser. 3, 25 (1972), N4, 721 735.

71. P. Erdös and C.A. Rogers, Covering space with convex bodies, Acta Arithmetica, 7 (1962), 281 285.

72. L. Babai and P. Frankl, Linear algebra methods in combinatorics, Part 1, Department of Computer Science, The University of Chicago, Preliminary version 2, September 1992.

73. V. Klee and S. Wagon, Old and new unsolved problems in plane geometry and number theory, Math. Association of America, 1991.

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

75. H. Lenz, Uber die Bedeckung ebener Punktmengen durch solche kleineren Durchmessers, Arch. Math. 4 (1956), 34 -40.

76. J. Schopp, Die Abdeckung ebener Bereiche mit konstanten Durchmessern durch drei Kreise von kleinerem Durchmesser, Vortrag, gehalten auf der Geometrie-Tegen in Tihany (Ungarn), 1965.

77. P. Katzarowa-Karanowa, Uber ein euklidisch-geometrisches Problem von B. Grünbaum, Arch. Math., XVIII (1967).

78. L. Danzer, On the k-th diameter in Ed and a problem of Griinbaum, Proc. Colloquium on Convexity, Copenhagen, 1965, 41.

79. C.A. Rogers, Covering a sphere with spheres, Mathe-matika, 10 (1963), 157 164.

80. R. Rankin, On the closest packing of spheres in n dimensions, Ann. Math., 48 (1947), 1062 1081.

81. Г.А. Кабатянский, В.И. Левенштейн, Оценки для упаковок на сфере и в пространстве, Проблемы передачи информации, 14 (1978), 1 17.

82. A.J.W. Hilton, Е.С. Milner, Intersection theorems for systems of finite sets, Quart. J. Math., Oxford (2), 18 (1967), 369 384.

83. P. Erdos, Chao Ко and R. Rado, Intersection theorems for systems of finite sets, J. Math. Oxford, Sec., 12 (48) (1961).

84. M. Deza, P. Frankl, Erdos Ко - Rado theorem - 22 years later, SIAM J. Alg. Disc. Methods 4, (1983), 419 -431.

85. N. Alon, L. Babai, and H. Suzuki, Multilinear polynomials and Frankl Ray-Chaudhuri - Wilson type intersection theorems, J. Comb. Th., Ser. A, 58 (1991), 165 - 180.

86. П. Эрдеш и Дж. Спенсер, Вероятностные методы в комбинаторике, Москва, "Мир", 1976.

87. N. Alon and J. Spencer, The probabilistic method, Wiley- Interscience Series in Discrete Math, and Optimization, Second Edition, 2000.

88. D.K. Ray-Chaudhuri and R.M. Wilson, On t designs, Osaka J. Math., 12 (1975), 735 - 744.

89. M. Deza, P. Erdos, and P. Frankl, Intersection properties of systems of finite sets. Proc. Lon. Math. Soc. 36 (1978), 369 384.

90. M. Deza, P. Erdos, N.M. Singhi, Combinatorial problems on subsets and their intersections, Advances in Math., Suppl. Studies, 1 (1978), 259 265.

91. B. Bollobas, Random Graphs, Cambridge Univ. Press, Second Edition, 2001.

92. B. Bollobas, The chromatic number of random graphs, Combinatorica, 8 (1988), 49 56.

93. К. Прахар, Распределение простых чисел, "Мир", Москва, 1967.

94. G.M. Ziegler, Lectures on 0/1 polytopes, in "Polytopes- Combinatorics and Computation" (G. Kalai and G.M. Ziegler, eds.), DMV seminar 29 (2000), Birkhauser - Verlag Basel, 1 - 44.

95. G.M. Ziegler, Coloring Hamming graphs, optimal binary codes, and the 0/1 Borsuk problem in low dimensions, Lect. Notes Comput. Sci., 2122 (2001), 159 - 171.

96. С. Payan, On the chromatic number of cube like graphs, Discrete Math., 103 (1992), 271 - 277.

97. F. Schiller, Zur Berechnung und Abschätzung von Färbungszahlen und der д Funktion von Graphen, Diplomarbeit, TU Berlin 1999, 50 стр.

98. J. Petersen, Färbung von Borsuk Graphen in niedriger Dimension, Diplomarbeit, TU Berlin 1998, 39 стр.

99. N. Linial, R. Meshulam, and M. Tarsi, Matroidal bijec-tions between graphs, J. Combin. Theory, Ser. В, 45 (1988), N1, 31 44.

100. H.H. Кузюрин, Асимптотическое исследование задачи о покрытии, Проблемы кибернетики, 1980, N37, 19 56.

101. Р. Turän, Еду grafelmeletiszelsoertek feladatrol, Mat. Fiz. Lapok, 1941, 48, 436 452.

102. G. Katona, T. Nemetz, M. Simonovitz, On a graph problem of Turan, (in Hungarian), Mat. Lapok, 15 (1964), 228 238.

103. Z. Füredi, Turän's type problems, Surveys in Combinatorics, Proc. of the 13th British Combin. Conference, ed. A.D. Keedwell, Cambridge Univ. Press, London Math. Soc. Lecture Note Series, 166 (1991), 253 300.

104. B.K. Леонтьев, Верхние оценки a глубины (0,1) -матриц, Математические заметки, 15 (1974), N3, 421 -429.

105. Э.И. Нечипорук, О топологических принципах самокорректирования., Проблемы кибернетики, 1969, N21, 5 103.

106. А.А. Сапоженко, О сложности дизъюнктных нормальных форм, получаемых с помощью градиентного алгоритма, Дискретный анализ, N21, Новосибирск, 1972, 62 71.

107. Е.Д. Глускин, Экстремальные свойства ортогональных параллелепипедов и их приложение к геометрии банаховых пространств, Математический сборник, 136 (1988), N1, 85 96.

108. P. Frankl, The Erdos Ко - Rado theorem is true for n = ckt, Combinatorics, Coll. Math. Soc. J. Bolyai, 18 (1978), 365 - 375.

109. R.M. Wilson, The exact bound in the Erdos Ко - Rado theorem, Combinatorica, 4 (1984), 247 - 257.

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

111. R. Ahlswede, L.H. Khachatrian, The complete intersection theorem for systems of finite sets, Europ. J. Combin., 18 (1997), 125 136.

112. Дж. Касселс, Введение в геометрию чисел, Москва, "Мир", 1965.

113. P.M. Gruber and C.G. Lekkerkerker, Geometry of numbers, North-Holland, Amsterdam, 1987.

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

115. К. Роджерс, Укладки и покрытия, Москва, "Мир", 1968.

116. В.В. Макеев, Универсальные покрышки и проекции тел постоянной ширины, Укр. Геометр. Сборник, 32 (1989), 84 88.

117. В. Weissbach, Polyhedral covers, Coll. Math. Soc. J. Bolyai, 48 (Intuitive Geometry), North Holland, Amsterdam et al., 1987, 639 - 646.

118. E. Helly, On a collection of convex bodies with common points, Russian Math. Surveys, 2 (1936), N2.

119. E. Helly, Uber Systeme abgeschlossener Mengen mit gemeinschaftlichen Punkten, Monatsh. Math., 37 (1930), 281 302.

120. F. Reuleaux, Lehrbuch der Kinematik I. Vieweg, Braunschweig 1875.

121. H. Hadwiger, Kleine Studie zur kombinatorischen Geometrie der Sphäre, Nagoya Math. J., 8 (1955), 45 48.

122. H. Hadwiger, Eulers Charakteristik und kombinatorische Geometrie, J. Reine Angew. Math., 194 (1955), 101 110.

123. В.Г. Болтянский, Задача об освещении границы выпуклого тела, Изв. Молдавского филиала АН СССР, N10 (76), 1960, 77 84.

124. В.Ф. Колчин, Случайные графы, Москва, Физматлит, 2002.

125. В.Н. Сачков, Вероятностные методы в комбинаторном анализе, Москва, Наука, 1978.

126. J. Bourgain, A Szemeredi type theorem for sets of positive density in Rn, Israel J. Math., 54 (1986), 307 316.

127. H.T. Croft, Incidence incidents, Eureka (Cambridge), 30 (1967), 22 26.

128. K.J. Falconer, The realization of distances in measurable subsets covering R\ J. Combin. Th. Ser. A, 31 (1981), 187 189.

129. K.J. Falconer, J.M. Marstrand, Plane sets of positive density at infinity contain all large distances, Bull. London Math. Soc., 18 (1986), 475 477.

130. H. Fiirstenberg, Y. Katznelson, B. Weiss, Ergodic theory and configurations in sets of positive density, in: Mathematics of Ramsey theory, J. Nesetril, V. Rodl, eds., Algorithms and Combinatorics 5, Springer-Verlag, 1990, 184 -198.

131. P. Erdos, A. Renyi, On random graphs /, Publ. Math. Debrecen, 6 (1959), 290 297.

132. P. Erdos, A. Renyi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sci., 5 (I960), 17 61.

133. P. Erdos, A. Renyi, On the evolution of random graphs, Bull. Inst. Int. Statist. Tokyo, 38 (1961), 343 347.

134. В. Bollobas, Threshold functions for small subgraphs, Math. Proc. Camb. Phil. Soc., 90 (1981), 197 206.

135. B. Bollobas, Martingales, isoperimetric inequalities, and random graphs, Proceedings, Eger (1987) (A. Hajnal, L. Lovasz, V.T. Sos, eds.), Colloq. Math. Soc. Janos Bolyai, 52 (1987), North Holland, Amsterdam, 113 - 139.

136. B.E. Тараканов, Комбинаторные задачи и (0,1) матрицы, "Наука", Москва, 1985.

137. Г. Эндрюс, Теория разбиений, "Наука", Москва, 1982.

138. A.M. Райгородский, Ю.А. Калнишкан, О проблеме Борсука в R3, Мат. заметки, 74 (2003), N1, 149 151. (A.M. Райгородским разработана техника универсальных покрывающих систем и доказаны основные теоремы; Ю.А. Калнишканом осуществлен компьютерный счет.)

139. A.M. Райгородский, Проблема Борсука для (0,1) -многогранников и кросс политопов, Доклады РАН, 371 (2000), 600 - 603.

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

141. A.M. Райгородский, Проблема Борсука для (0,1) -многогранников и кросс политопов, Доклады РАН, 384 (2002), 593 - 597.

142. A.M. Райгородский, Проблема Борсука для целочисленных многогранников, Мат. сборник, 193 (2002), N10, 139 160.

143. A.M. Райгородский, Проблемы Борсука, Грюнбаума и Хадвигера для некоторых классов многогранников и графов, Доклады РАН, 388 (2003), N6, 738 742.

144. A.M. Raigorodskii, On the Вorsuk partition problem, Abstract of the talk at the International Festival of Geometry dedicated to B. Griinbaum and V. Klee, April 9 16, 2000, Ein - Gev, Israel.

145. A.M. Райгородский, О размерности в проблеме Борсука, УМН 52 (1997), N6, 181 182.

146. A.M. Райгородский, Об одной оценке в проблеме Борсука, УМН 54 (1999), N2, 185 186.

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

148. A.M. Raigorodskii, On the chromatic numbers of R", Abstract of the talk at the Conference on Graph Theory, Algorithms, Combinatorics, and Applications, June 4-9, 2000, Kalamazoo, Michigan, USA.

149. A.M. Райгородский, О хроматических числах некоторых метрических пространств, Тезисы докладов международной конференции по дискретной геометрии, Москва, январь, 2001.

150. A.M. Raigorodskii, Colouring the Erdds unit-distance graphs, Abstract of the talk at the International Conference "Dophantine approximations and uniform distribution", August, 2003, Minsk, Belorus.

151. A.M. Райгородский, Хроматические числа, Московский Центр Непрерывного Математического Образования, Москва, 2003.

152. A.M. Райгородский, Проблемы Борсука и Хадвигера и системы векторов с запретами на скалярные произведения, УМН 57 (2002), N3, 159 160.

153. A.M. Райгородский, Проблема Эрдеша Хадвигера и хроматические числа конечных геометрических графов, Доклады РАН, 392 (2003), N3, 313 - 317.

154. A.M. Райгородский, О хроматических числах метрических пространств, Чебышевский сборник, 5 (2004), N1 (9), 175 185.

155. A.M. Райгородский, О проблемах Борсука и Хадвигера, Тезисы докладов Пятой международной конференции "Алгебра и теория чисел: современные проблемы и приложения", Тула, май, 2003.

156. A.M. Райгородский, Об одной задаче оптимального покрытия множеств шарами, Чебышевский сборник, Т. 3, Вып. 2 (4), 2002, 100 106.

157. A.M. Raigorodskii, On Borsuk's problem, Abstract of the talk at the Second Conference of Project "Algebra, Geometry and Combinatorics", July 9-11, 1998, Porto, Portugal.

158. A.M. Raigorodskii, An estimate in Borsuk's problem, Abstract of the talk at the Third Conference of Project "Algebra, Geometry and Combinatorics", June 28-30, 1999, Porto, Portugal.

159. A.M. Raigorodskii, On two combinatorial problems, Paul Erdos and his Mathematics, Abstracts of talks held in the memory of Paul Erdos, Budapest, Hungary, July 4-11,1999.

160. A.M. Райгородский, Системы общих представителей, Фунд. и Прикл. Мат., 5 (1999), N3, 851 860.

161. A.M. Райгородский, Системы общих представителей, Тезисы докладов Третьей международной конференции "Современные проблемы теории чисел и ее приложения", Тула, 1996, стр. 118.

162. A.M. Райгородский, Дефект допустимых шаров и октаэдров в решетке и системы общих представителей, Мат. сборник, 189 (1998), N6, 117 141.

163. A.M. Raigorodskii, Probabilistic approach to the problem of the defects of good admissible sets in a lattice, Abstract of the talk at the International Conference "XXI Journees Arithmétiques", July 12-17, 1999, Rome, Italy.

164. A.M. Райгородский, Вероятностный подход к задаче о дефектах допустимых множеств в решетке, Мат. заметки, 68 (2000), N6, 910 916.

165. A.M. Raigorodskii, The defects of admissible sets in a lattice, and systems of common representatives, "Beitrâge zur zahlentheoretischen Analysis", Grazer Mathematische Berichte, N338 (1999), 31 62.