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

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

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

Райгородский, Андрей Михайлович АВТОР

доктора физико-математических наук УЧЕНАЯ СТЕПЕНЬ

Москва МЕСТО ЗАЩИТЫ

2004 ГОД ЗАЩИТЫ

01.01.09 КОД ВАК РФ

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

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

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

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

На правах рукописи УДК 519.174, 519.112.71, 514.174, 511.9

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

ПРОБЛЕМЫ БОРСУКА, НЕЛСОНА - ЭРДЕША - ХАДВИГЕРА И ГРЮНБАУМА В КОМБИНАТОРНОЙ ГЕОМЕТРИИ

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

Автореферат

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

Москва 2004

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

Официальные оппоненты: доктор физико-математических наук,

профессор О.М. Касим-Заде доктор физико-математических наук, профессор Е.П. Барановский доктор физико-математических наук, профессор Н.М. Добровольский

Ведущая организация: Математический Институт

им. В.А. Стеклова РАН

Защита диссертации состоится " Н " и.сО КОС 2004 г. в 16 часов 15 минут на заседании диссертационного совета Д 501.001.84 в Московском государственном университете им. М.В. Ломоносова по адресу 119992, ГСП-2, Москва, Ленинские горы, МГУ, ауд. 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (главное здание, 14 этаж).

Автореферат разослан

2004 г.

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

В.Н. Чубариков

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

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

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

2C.A. Rogers, Covering a sphere with tpheret, Mathematika, 10 (1963), 157 - 164.

3R. Rankin, On the cloiest packing of spheres in n dimensiónг, Ann. Math., 48 (1947), 1062 - 1081.

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

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

РОС. НАЦИОНАЛЬНАЯ' БИБЛИОТЕКА

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

Вторая проблема, изучаемая нами в работе, принадлежит нескольким авторам, из которых наибольшую роль в ее становлении сыграли Э. Нелсон6, П. Эрдеш и Г. Хадвигер7. Проблема сводится к нахождению наименьшего количества цветов, необходимых для такой раскраски метрического пространства, при которой между точками одного цвета не может быть некоторого фиксированного заранее расстояния. Ей также больше 50-и лет, и ее популярность огромна. Во-первых, ясно, что практически все связи, приведенные нами при обсуждении проблем Борсука и Грюнбаума, актуальны и для нее: более того, с точки зрения разбиений и упаковок пространств она даже интереснее, так как в ней разрабатывается техника, относящаяся к так называемым разбиениям Вороного и имеющая непосредственный выход на замечательные статьи Т. Батлера8, П. Эрдеша и К.А. Роджерса9, Д. Лармана и К.А. Роджерса10 и др. Во-вторых, она в значительной мере связана с различными важными задачами теории графов, в том числе и случайных.

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

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

6А. Soifer, Mathematical coloring book, Center for Excellence in Mathematical Education, 1997.

Hadwiger, Ein Uberdeckungssatz für Jen Euklidischen Raum, Portugaliae Math., 4 (1944), 140- 144.

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

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

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

I , > 4 ,. ": . 4

методы теории случайных графов, и топологические методы в геометрии, и аналитические методы, и пр., и пр.

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

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

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

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

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

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

1. Для хроматического числа вещественного евклидова пространства получена оценка > (1.239...+ о(1))<'.

2. Для хроматического числа рационального евклидова пространства получена оценка x(Qd) > (1-173... + ©(l))4.

3. Найдена оценка х((Х, 11), 6) > (1.365... + o(l))d, верная для хроматических чисел пространств (Rd,/i) и (Qd,/i), коль скоро запрещенное расстояние соответственно.

Л. Имеет место неравенство x((Qrf> > (l + c + o(l))rf, е = £(9) >

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

6. Для максимального значения хроматического числа вещественного пространства с метрикой lq и с к запрещенными расстояниями выполнена оценка

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

8. Для хроматических чисел геометрических графов с вершинами в точках, имеющих координаты -2,-1, 0, 1, 2, получены серии нетривиальных нижних оценок.

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

10. Результаты пунктов 7, 8, 9 обобщены на случай геометрических графов с к запрещенными расстояниями.

11. Для суммы чисел Борсука и Нелсона - Эрдеша - Хадвигера получена оценка / + х> 1-2255... + 1.239... + 6, 6 > 0.

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

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

14. Результаты предыдущего пункта обобщены на случай покрытия; многогранников шарами в произвольной норме.

15. В размерностях с1 = 6,7,9 и с1 = 11 найдены новые нижние оценки на хроматические числа пространств И/* и С}*.

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

17. Изучены разбиения кросс-политопов в малых размерностях,

18. Исследованы вероятностные характеристики, связанные с вложением случайных графов в геометрические.

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

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

Перечислим сперва конференции: международная конференция "Современные проблемы теории чисел и ее приложения" (г. Тула, 1996 г.); вторая международная конференция "Алгебра, геометрия и комбинаторика" в Порту (Португалия, 1998 г.); международная конференция "Алгебраическая теория чисел и диофантовы приближения" в Граце (Австрия, 1998 г.); третья международная конференция "Алгебра, геометрия и комбинаторика" в Порту (Португалия, 1999 г.); международная конференция, посвященная памяти П. Эрдеша, в Будапеште (Венгрия, 1999 г.); международная конференция "XXI Арифметические дни" в Риме (Италия, 1999 г.); международная конференция "Решетки, многогранники и разбиения" в Обервольфахе (Германия, 2000 г.); международная конференция, посвященная Кли и Грюнбауму, в Эйн - Геве (Израиль, 2000 г.); международная конференция "Конференция по теории чисел, посвященная смене тысячелетий" в Эрбане (США, 2000 г.); международная конференция "Теория графов, комбинаторика, алгоритмы и приложения" в Каламазу (США, 2000 г.); международная конференция "Дискретная и вычислительная геометрия" в Аноие (Греция, 2000 г.); международная конференция "Современные проблемы теории чисел и ее приложения" (г. Тула, 2001 г.); международная конференция по дискретной геометрии, посвященная семидесятилетию С.С. Рыш-кова (г. Москва, 2001 г.); международная конференция "Дискретная, комбинаторная и вычислительная геометрия" в Пекине (Китай, 2002 г.); международная конференция "Современные проблемы теории чисел и ее приложения" (г. Тула, 2003 г.); международная конференция "Диофантовы приближения и равномерное распределение" в Минске

(Беларусь, 2003 г.); международный семинар по дискретной математике (г. Москва, 2004 г.); Ломоносовские чтения в Московском государственном университете в 1999, 2002, 2003 гг.

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

Публикации. Результаты диссертации опубликованы в тридцать одной работе. Список этих работ приведен в конце автореферата.

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

Содержание работы

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

Вторая глава посвящена детальной разработке линейно-алгебраического метода в экстремальной теории гиперграфов с запретами на мощности пересечения ребер и совокупностей векторов с запретами на скалярные произведения и расстояния. Разработанный метод эффективно применяется для получения многочисленных нетривиальных нижних оценок на величины /(<0,х(&<0>х(<3'1)1Х((^|М.Ь))х((Р<'Л)» 6),'2)»2),^((К.1*,А). (Здесь /(с1) - минимальное число частей меньшего диаметра, на которые может быть разбито произвольное ограниченное множество в Л''; х(К-<<) - наименьшее количество цветов, в которые можно так раскрасить точки евклидова пространства, чтобы между одноцветными точками не было расстояния 1; х(Р<<) - аналогичная характеристика для С^; /1), ¿>) - аналогичная характеристика для метрического пространства X € {К^, С^} с метрикой 1\ и расстоянием 6, которое не должно достигаться между одноцветными точками; х№*,1я),Ь) - аналогичная характеристика в случае, когда X = С^, а роль метрики играет ^((В^Ы^) - максимальное число цветов, которые потребуются для оптимальной раскраски евклидова пространства, коль скоро точкам одного цвета запрещается отстоять друг от друга на любое из (некоторых) двух расстояний, а максимум берется по всем возможным парам подобных запретов; - аналогич-

ная характеристика для случая произвольной метрики и произвольного количества к запрещенных расстояний.) Типичный пример результата сформулирован, скажем, в теореме 2.2.1.2 из параграфа 2.2.1:

Теорема 2.2.1.2. Положим

(здесь х и у - независимые вещественные переменные). Определим, далее, величины хо,уо как такие корни системы нелинейныхуравнений

2А31оё Л4 + (1 - 4Л3) 1о8(Лх - 2Л4) + {2А3 - 1) 1ой(1 - А1 + А4)

С), (**)

log у + log(z - у) = О,

(1 — х)2у_ {Х-у)3

что а;о = 0.36063..., а уо = 0.063907.... Наконец, зададим величину у равенством

где А° = Ai(x0,y0). Тогда x(R.d) > (7 + °(l))d = (1.239...+ о(1))й.

Подобные результаты приведены также в теоремах 2.2.1.1, 2.2.1.3 - 2.2.1.6 нз параграфа 2.2.1 и в теоремах 2.2.2.1, 2.2.2.2 из параграфа 2.2.2. Кроме того, установлена тонкая спязь между задачами Борсука и Нелсона - Эрдеша - Хадвигера (как в целом - на уровне общности метода, - так и в частности - теорема 2.4.2.1 из параграфа 2.4.2).

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

7 = - 2Л5)л°_2а°(1 - Л? + Л^-^+^Х

х(1 - Жор-Ч-го - yar"55er{,E;-ro2/"Vo ' (* * *)

xff = x({ai..••,at}n;/eI,•..,/„,)= max \(G).

себ,

(Тут ,\(G) - хроматическое число графа G,

класс всех графов, который можно записать в форме

U UG- G=(V,E),E = Eb(V)

VCS,b>0

Eb(V) = {(x,y)eVxV:\x-y\ = b)

где, в свою очередь,

Яд = S({ai,. ..,at}n;/ai,...,/ai) = {x = (xi,...,ar„) :

семейство п - мерных векторов с фиксированными заранее наборами целых чисел ai,..., at и натуральных чисел /<,,,...,/<,,, обладающих свойством +... + 1а, = п, 2 < t = t(n) < n; |х — у| - евклидово расстояние между векторами; card T - мощность множества Т.)

В разных ситуациях (т.е. при различных соотношениях между числами ai,...,at,lai,---,la,) оценки на упомянутую величину даются в теоремах 3.3.1.1 - 3.3.3.4 из параграфа 3.3.1, в теоремах 3.3.2.1 - 3.3.2.4 из параграфа 3.3.2 и теоремах 3.3.3.1, 3.3.3.2 из параграфа 3.3.3. Отдельно рассмотрены случаи t = 3, ai = — 1,аг = 0, аз = 1; t = 5, ai = —2,02 = —1,аз = 0,а4 = 1,а5 = 2. В подробностях исследованы и проиллюстрированы соотношения между областями применимости теорем.

В той же третьей главе изучено важное приложение метода альтернирования, дающее нетривиальный результат относительно величин и свидельствующее, тем самым, об еще более глубокой связи между проблемами Борсука и Нелсона - Эрдеша - Хадвигера, чем та, которую удавалось установить прежде. А именно., в теореме 3.6.2.1 из параграфа 3.6.2 доказано неравенство / + х > 1.239... + 1.2255... + S (S > 0; / определяется из выражения f(d) = (/ + o(l))rf; х - из выражения x(®-d) = ix + o(l))d), хотя ранее было известно только, что / > 1.2255... (теорема 2.2.1.1 из параграфа 2.2.1) и что х > 1.239... (теорема 2.2.1.2 из параграфа 2.2.1).

В четвертой главе разрабатывается новая комбинаторная техника покрытия с зацеплением. Во-первых, она позволяет усилить все имевшиеся ранее верхние оценки для минимального числа частей меньшего диаметра, на которые может быть разбит произвольный многогранник с заданной координатной структурой вершин (грубо говоря, речь идет о выпуклых оболочках совокупностей векторов из Ед при тех или иных значениях величин aj,..., at и пр.). Во-вторых, она с успехом применяется с целью отыскания новых верхних оценок для наименьшего количества шаров того же диаметра, которыми покрывается любой из упомянутых многогранников. В-третьих, она дает новые верхние оценки на хроматические числа всевозможных конечных геометрических графов, т.е., в частности, и на величины типа Хд• Соответствующие результаты сформулированы в теоремах 4.3.2.1 - 4.3.2.5 из параграфа 4.3.2, в

теоремах 4.3.3.1 - 4.3.3.6 из параграфа 4.3.3 и в теоремах 4.3.4.1, 4.3.4.2 из параграфа 4.3.4. Отдельно разобраны случаи (0,1) - многогранников и (-1,0,1) - многогранников (кросс-политопов). Произведено тщательное сопоставление областей применимости теорем. Наконец, результаты, касающиеся покрытия шарами (проблемы Грюнбаума), перенесены на случай шаров в произвольной норме.

Результаты пятой главы легко выписать:

Теорема 5.2.1. Выполнена оценка > М-

Теорема 5.2.2. Выполнена оценка 15.

Теорема 5.2.3. Выполнена оценка х(К-П) > 20.

Теорема 5.2.4. Выполнена оценка х(Р9) > 12.

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

В шестой главе разрабатываются новые геометрические подходы к проблеме Борсука в малых размерностях. Эти подходы связаны с построением универсальных покрывающих систем и резюмируются в лемме 6.2.1 из параграфа 6.2, в предложении 6.3.1 и следствиии 6.3.1 из параграфа 6.3. Здесь разумно сформулировать следствие 6.3.1, так как в нем содержится суть происходящего:

Следствие 6.3.1. Если, например, ЙСЙ-3 таково, что

то П разбивается на четыре части диаметра <0.96.

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

Кроме того, в шестой главе изучены кросс-политопы в размерностях d < 35 с точки зрения разбиения их на части. Соответствую-

щее утверждение содержится в предложении 6.4.1 из параграфа 6.4, и состоит оно в построении кросс-политопов, в любом разбиении которых на d + 1 часть имеется по крайней мере один элемент диаметра > 0.9428...

В седьмой главе осуществляется исследование проблемы Нелсона -Эрдеша - Хадвигера с вероятностной точки зрения, а именно, с точки. зрения асимптотического поведения свойства вложимости случайного графа и его подграфов в геометрические графы на плоскости и в пространстве произвольной размерности. В частности, там рассматривается величина t(n,p), равная максимальному к, при котором свойство

случайного графа в модели выполняется почти наверное; само свойство Q* состоит в том, что в графе G = (К, Е), card V = п, существует такой индуцированный подграф Н = (U,F) = G\ucv, что card U — k, H связен, его хроматическое число х(Н) не меньше четырех и он вкладывается в граф Нелсона - Эрдеша - Хадвигера на плоскости, т.е в бесконечный геометрический "граф расстояний", посредством которого определяется величина Таким образом, t(n,p) отвечает за то, насколько часто в графе расстояний встречаются подграфы с большим хроматическим числом (хорошо известно, что x(R2) "> 4, и есть гипотеза, что такая оценка неулушаема). Следующие результаты даны в параграфе 7.2.2:

Теорема 7.2.2.1. Пусть I = Цп,р) - это минимальное натуральное число, с которым имеет место асимптотическое выражение

cln{l-pf> 0, г» -> оо.

Тогда t(n,p) < 71.

Теорема 7.2.2.2. Пусть р< Тогда t(n,p) log п.

Теорема 7.2.2.3. Пусть пир таковы, что

(Здесь штрих означает, что суммирование распространяется исключительно на нечетные значения переменной к.) Тогда t{n,p) не существует.

. В параграфах 7.3.2,7.3.3,7.3.4 приведены обобщения теорем 7.2.2.1 -7.2.2.3 на случай, когда вместо t(n, p) исследуется схожая с ней величина

t(d,n,p)) отвечающая за вложение подграфов случайного графа в граф расстояний d - мерного пространства.

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

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

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

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

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

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

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

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

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

8. A.M. Райгородский, О размерности в проблеме Борсука // Успехи математических наук, Т. 52 (1997), Вып. 6, стр. 181 - 182.

9. A.M. Райгородский, Об одной оценке в проблеме Борсука // Успехи математических наук, Т. 54 (1999), Вып. 2, стр. 185 - 186.

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

11. A.M. Райгородский, Проблемы Борсука и Хадвигера и системы векторов с запретами на скалярные произведения // Успехи математических наук, Т. 57 (2002), Вып. 3, стр. 159 - 160.

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

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

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

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

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

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

18. A.M. Raigorodskii, The defects of admissible sets in a lattice, and systems of common representatives // "Beitrage zur zahlentheoretischen Analysis", Grazer Mathematische Berichte, №338 (1999), p. 31 - 62.

19. A.M. Райгородский, Ю.А. Калнишкан, О проблеме Борсука // Тезисы докладов Четвертой международной конференции "Современные проблемы теории чисел и ее приложения", Тула, 2001. A.M. Райгородским описаны и доказаны основные теоремы; Ю.А. Калнишканом произведены и представлены расчеты на компьютере.

20. A.M. Raigorodskii, On the Borsuk 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.

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

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

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

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

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

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

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

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

29. A.M. Raigorodskii, Systems of common representatives: applications to the geometry of numbers and to Borsuk's partition problem // Abstract of the talk at the International Millennial Conference on Number Theory, May 21 - 26, 2000, Urbana - Champaign, Illinois, USA.

30. A.M. Raigorodskii, The defects of good admissible sets in a lattice, and systems of common representatives // Abstract of the talk at the International Conference on Algebraic Number Theory and Diophan-tine Analysis, August 31 - September 4, 1998, Graz, Austria.

31. 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 Arithmetiques", July 12-17, 1999, Rome, Italy.

Издательство ЦПИ при механико-математическом факультете МГУ им. М.В.Ломоносова. Подписано в печать

Формат 60x90 1/16. Усл. печ. л./^ЯЬ

Тираж 100 экз. Заказ /2,

Лицензия на издательскую деятельность ИД В 04059, от 20.02.2001г.

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета и Франко-русского центра им. A.M. Ляпунова.

1-7265

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

Введение

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

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

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] и др. Во-вторых, она в значительной мере связана с различными важными задачами теории графов, в том числе и случайных.

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

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

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; ж], {ж} - как правило, целая часть и дробная доля числа ж; п,р) - случайный граф (пространство);

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

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

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

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

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.