Экстремальные характеристики вложений случайных графов в геометрические графы тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

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

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

На правах рукописи УДК 519.174.7+519.175.4

Нагаева Светлана Вячеславовна

ЭКСТРЕМАЛЬНЫЕ ХАРАКТЕРИСТИКИ ВЛОЖЕНИЙ СЛУЧАЙНЫХ ГРАФОВ В ГЕОМЕТРИЧЕСКИЕ ГРАФЫ

01.01.05 — теория вероятностей и математическая статистика

Автореферат

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

Я,

Москва 2009

003470707

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

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

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

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

профессор

Александр Антонович Сапоженко

кандидат физико-математических наук,

Роман Григорьевич Степанов

Ведущая организация: Центральный Экономико-

Математический Институт

Защита диссертации состоится 29 мая 2009 г. в 16 часов 45 минут на заседании диссертационного совета Д 501.001.85 при Московском государственном университете им. М.В. Ломоносова по адресу 119991, ГСП-1, Москва, Ленинские горы, МГУ, аудитория 16-24.

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

Автореферат разослан 28 апреля 2009 г.

Ученый секретарь диссертационного совета Д 501.001.85 при МГУ доктор физико-математических наук, профессор

И.Н. Сергеев

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

Актуальность темы.

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

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

По существу, теория случайных графов оформилась в самостоятельную и многоплановую дисциплину на рубеже 50ых и 60ых годов XX века с трудами П. Эрдеша и А. Реньи123. Однако естественная идея вероятностной трактовки науки о графах возникла намного раньше.

Сразу после возникновения теории случайных графов стало ясно, что она имеет не только огромную теоретическую ценность, но также и массу практических приложений. Здесь стоит упомянуть, например, проблематику построения вероятностных алгоритмов на графах и статистический анализ данных в различных "реальных" сетях - социальных, биологических и пр.4

Сейчас роль вероятности в теории графов несомненна. Достаточно процитировать классические монографии таких выдающихся специалистов в области, как Б. Боллобаш5, Н. Алон и Дж. Спенсер0, С. Ян-сон, Т. Лучак, А. Ручиньски7, В.Ф. Колчин8 и др.

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

1Р. Erdös, A.'Rinyi, On random graphs I, Publ. Math. Debrecen, 6 (1959), 290 - 297.

2P. Erdös, A. R(5nyi, On the evolution of random graphs, Publ. Math. Inst. Hungar. Acad. Sei., 5 (1960), 17 - 61.

3P. Erdös, A. Renyi, On the evolution of random graphs, Bull. Inst. Int. Statist. Tokyo, 38 (1961), 343 - 347.

4A.M. Райгородский, Экстремальные задачи теории графов и анализ данных, НИЦ "Регулярная и хаотическая динамика2009.

ЕВ. Bollobäs, Random Graphs, Cambridge Univ. Press, Second Edition, 2001.

6H. Алон, Дж. Спенсер, Вероятностный метод, Бином: Лаборатория знаний, Москва, 2007.

7S. Janson, Т. Luczak, A. Rucinski, Random Graphs, Wiley, New York, 2000.

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

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

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

Проблема Нелсона - Эрдеша - Хадвигера играет заглавную роль в области геометрической комбинаторики. В разное время ею занимались такие крупные специалисты, как Г. Хадвигер9, Д. Ларман и К.А. Роджерс10, П. Франкл и P.M. Уилсон11 и др. Эта проблема допускает естественную теоретико-графовую интерпретацию, и потому к ней применяются методы вероятностной теории графов. В самом деле, как показали П. Эрдеш и Н.Г. де Брёйн12, хроматическое число любого метрического пространства совпадает с хроматическим числом некоторого конечного графа расстояний с вершинами в этом пространстве.

Конкретная задача, решаемая в диссертации, основана на идеях П.

9Н. Hadwiger, Unelöste Probleme N 40, Elemente der Math., 16 (1961), 103 - 104.

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

UP. FVankl and R. Wilson, Intersection theorems with geometric consequences, Combinatorica, 1 (1981), 357- 368.

12N.G. de Bruijn, P. 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.

Эрдеша13 и поставлена в работе A.M. Райгородского14. Интересующая нас вероятностная характеристика - это величина t(d,n,p,x), равная максимальному к, при котором в модели случайного графа G(n,p), предложенной еще Эрдешем и Реньи, с большой вероятностью случайный граф содержит такой индуцированный подграф на к вершинах, что у него хроматическое число не меньше х и он изоморфен какому-либо графу расстояний в Rd. Если при всех к вероятность описанного события мала, то величина t(d,n,p,x) полагается равной нулю.

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

Цель работы и основные задачи. Цель исследования в разработке вероятностных методов теории случайных графов и в получении с помощью этих методов достаточно точных оценок величины t(d,n,p,x) при различных соотношениях и зависимостях между параметрами.

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

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

1. При различных соотношениях между аргументами d,n,p,x установлено равенство нулю величины t(d,n,p,x) (параграф 1.4).

2. В весьма широкой общности, то есть при практически произвольных значениях аргументов d, тг, р, X получены новые нетривиальные верхние оценки для величины t(d,n,p,x) (теорема 3).

3. Доказаны новые нижние оценки для величины t(d,n,p.x) в условиях, когда d не зависит от п (теорема 4).

13Р. Erdös, Unsolved Problems, Congress Numerantium XV - Proceedings of the 5th British Comb. Conf. 1975, (1976), 681.

14 A.M. Райгородский, Проблема Нелсона - Эрдеша - Хадвигера и вложения случайных графов в геометрические, Доклады РАН, 403 (2005), N2, 169 - 171.

4. Показано, что в широком классе ситуаций (например, при постоянных d up) верхние и нижние оценки из пунктов 2 и 3 совпадают по порядку величины и, стало быть, в указанном классе задача отыскания порядка роста функции t(d, п, р, х) решена полностью (параграф 1.4).

Все результаты диссертации получены соискателем самостоятельно.

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

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

Апробация результатов. Результаты диссертации докладывались на IX международном семинаре "Дискретная математика и ее приложения" , посвященном 75-летию со дня рождения академика О.Б. Лупа-нова (Москва, 2007 г.), на Ломоносовских чтениях в Московском государственном университете (2006 г.), а также на кафедральном семинаре кафедры математической статистики и случайных процессов механико-математического факультета МГУ, на семинаре професора Б.М. Гуре-вича в МГУ (2008 г.), на семинаре профессора C.B. Конягина в МГУ (2008 г.), неоднократно на семинарах доктора физико-математических наук A.M. Райгородского в МГУ (2005-2009 гг.), на семинаре доктора физико-математических наук A.M. Райгородского на факультете инноваций и высоких технологий Московского физико-технического института (2009 г.), на семинаре профессора A.A. Сапоженко на факультете Вычислительной математики и кибернетики МГУ (2009 г.) и семинаре в Центральном Экономико-Математическом Институте (2009 г.).

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

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

Краткое содержание работы

Первая глава диссертации посвящена истории проблематики, постановкам задач и формулировкам основных теорем.

В параграфе 1.1 вводится модель Эрдеша- Реньи случайного графа, которую принято обозначать G(n,p). Говоря кратко,

G(n,p) = (fln,Bn,Pn)~

это (конечное) вероятностное пространство, в котором элементарные события суть все возможные графы на п вершинах без петель, кратных ребер и ориентации, алгебра событий представляет собой совокупность всех наборов графов из С2„. а вероятность отдельного графа G — (V, Е) ищется по формуле

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

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

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

В параграфе 1.2 речь идет об истории проблемы Нелсона - Эрдеша - Хадвигера в комбинаторной геометрии, а также дается теоретико-

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

в которые можно так покрасить все точки пространства, чтобы между одноцветными точками не было расстояния 1. Приводятся оценки хроматического числа пространств Rd при d < 4 и при d —» со.

В параграфе 1.3, по существу, дается мотивировка всей дальнейшей деятельности и, собственно, формулируются основные результаты работы. Так, в пункте 1.3.1 определяется основная вероятностная характеристика, изучаемая в диссертации, — величина t{d,n,p,x)• А именно сперва вводится событие Qь, к = 1,...,п, на пространстве G(n,p), состоящее в том,'что в случайном графе G = {V.E) существует такой индуцированный подграф Я = (U,F), у которого |Î7| = к, х(Н) > х и Я изоморфен некоторому конечному графу расстояний в Kd (здесь Х{Н) - хроматическое число графа Я, то есть минимальное количество цветов, в которые можно так покрасить вершины Я, чтобы вершины, соединенные ребром, были разноцветными). И уже затем полагается

t{d,n,p,x,e) =

ГО, если{к€{1,..,п}:Р„(д*)>е}}=0; \ max{k Ç. {!,..,п} : Pn{Qk) > s}, иначе.

В конечном итоге рассматривается t{d,n,p,x) = t(d,n,p,x, 0.5). Замена произвольного е на конкретное 0.5 существа дела не меняет.

В том же параграфе 1.3 детально обсуждается смысл и значимость указанного определения. В пункте 1.3.2 последовательно перечисляются старые и новые результаты относительно поведения величины t{d,n,p, х).

Из числа старых теорем следует привести теоремы A.M. Райгород-ского.

Теорема 1. Пусть I — 1{п,р) - это любая функция, с которой имеет место асимптотическое выражение С„{1 — р)°1 —» 0,п —>• оо. Тогда

t{d,n,p,X) <№d)-

Теорема 2. Пусть m — тп(п) - это некоторая целочисленная функция, удовлетворяющая условиям тп € {l,...,n}, m —* оо при п —+ оо.

к —С2

Для каждого m определим ко — ко{т) из неравенств С™2 ко < 1 < и положим ki = ко — 4. Допустим, что для любого 5 = 5(п) = о(1) выполнено —» 0 при п —» оо и что

fci(m) > d+2 = d(n)+2. Тогда t(d,n,\,x<¡) <m, edexd - самая лучшая ■известная на сегодняшний день нижняя оценка величины

Однако основными теоремами являются теоремы 3 и 4, принадлежащие соискателю:

Теорема 3. Пусть при п —> оо выполнено: d{n) = const или d{ri) оо. Тогда для любого е > 0 существует N, такое, что при всех п> N и либо при любых х, d и р < , либо при любых х> d > 10 и р < ^ имеем: если

Р<

(2(d+2)!)a

то

если же

(l+s)(d+2)8+ilnn t(d,n,p,x) <

Р>

1 d+3

2(tf + 2)!V fl\ 2

(d + 2)4

(2(d + 2)!)з

3=T

mo

t{d>n,p,x) <

(l+s)(d+2)s+i\nnj

(d + 2)8 Inn

Теорема 4. Пусть функция вероятности ребра р такова, что рпа —♦

00 и (1 — р)па оо для любого фиксированного а > 0. Тогда, каковы бы ни были заданные наперед dl х < х(^) и £: найдется щ, начиная с которого при всех п выполнена оценка ¿(с?,п,р,х) >2(1 — е)

ш 1-р

Наконец, в параграфе 1.4 даются подробные комментарии к полученным результатам: выписываются важные частные случаи, оценки из теорем 3 и 4 сопоставляются между собой, а также с оценками из теорем

1 и 2 и прочими оценками такого типа. В частности, описывается важный класс случаев, когда t(d,n,p,x) — 0 и когда результаты теорем 3 и 4 совпадают по порядку величины. Оказывается, что при постоянных d и многих значениях других параметров полученные в диссертации неравенства принципиально неулучшаемы.

Вторая глава диссертации посвящена доказательству теоремы 3.

Поскольку доказательство теоремы 3 нетривиальное и технически весьма тяжелое, оно соответствующим образом структурировано. Прежде всего оно разбито на два параграфа. В параграфе 2.1 развивается техника мартингальных неравенств применительно к изучаемой проблеме (пункты 2.1.1 и 2.1.2), формулируется важная лемма, которая представляет самостоятельный интерес (пункт 2.1.3). В самом деле, пусть Ут,а+2 ~~ случайная величина, равная максимальной мощности множества пореберно непересекающихся (с2+2)-клик (полных графов на ((1+2) вершинах) в случайном графе в модели 0(т,р). Тогда имеют место нижние асимптотические оценки математического ожидания случайной величины 2, сформулированные в лемме (ввиду громоздкости формулировки, здесь она не приводится).

С помощью оценок из этой леммы в том же параграфе завершается доказательство теоремы 3 (пункт 2.1.4). При этом само завершение доказательства, в свою очередь, разделено для большей ясности на несколько частей (случаев). Справедливость леммы устанавливается в параграфе 2.2, который также для удобства подразделен на несколько пунктов (пункты 2.2.1 - 2.2.3).

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

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

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

1. C.B. Нагаева, О вложамости конечных графов расстояний с большим хроматическим числом в случайные графы, Доклады РАН, 418 (2008), N1, 19-22.

2. C.B. Нагаева, A.M. Райгородский, О реализации случайных графов графами расстояний в пространствах фиксированной размерности, Доклады РАН, 424 (2009), N3, 315 - 317.

В этой статье A.M. Райгородскому принадлежит постановка задачи и идея рассматривать "воздушные змеи"; C.B. Нагаевой принадлежит формулировка и доказательство основной теоремы..

3. C.B. Нагаева, О вложимостпи конечных графов расстояний с большим хроматическим числом в случайные графы, Материалы IX Международного семинара "Дискретная математика и ее приложения посвященного 75-летию со дня рождения академика О.Б. Лупанова,' Москва, механико-математический факультет МГУ, 2007, 396 - 398.

4. C.B. Нагаева, A.M. Райгородский, О вложимостпи конечных графов расстояний с большим хроматическим числом в случайные графы, Итоги науки и техники, "Современная математика и ее приложения 62 (2009), 47 - 66.

В этой работе A.M. Райгородскому принадлежит постановка задачи, обзорная часть и общее соображение о пользе применения мар-тингальной техники при решении задач о хроматическом числе случайного графа; C.B. Нагаевой принадлежит: полное решение поставленной задачи, то есть доказательство основной теоремы с помощью развитой ею вероятностно-аналитической техники.

Подписано в печать О*/, О9 Формат 60x90 1/16. Усл. печ. л. О, Тираж №0 экз. Заказ 32

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета МГУ имениМ. В. Ломоносова

Введение

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

1 Глава 1: Постановка задачи и формулировки результатов

1.1 Определение и свойства случайных графов

1.2 Несколько слов о проблеме Нелсона - Эрдеша

- Хадвигера.

1.3 Трудность проблемы Нелсона - Эрдеша - Хадвигера

1.3.1 Интерпретация задачи в терминах случайного графа.

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

1.4 Комментарии.

2 Глава 2: Доказательство теоремы

2.1 Основная часть доказательства теоремы

2.1.1 Предварительные рассуждения.

2.1.2 Неравенство Азумы.

2.1.3 Нижняя оценка математического ожидания величины

Ym,d+2.

2.1.4 Завершение доказательства теоремы

2.2 Доказательство леммы 1.

2.2.1 Предварительные рассуждения.

2.2.2 Асимптотика для M\W\

2.2.3 Завершение доказательства леммы

3 Глава 3: Доказательство теоремы

3.1 Основная идея.

3.2 Отыскание змеев в случайных графах.

3.3 Оценка математического ожидания.

3.4 Оценка второго момента и завершение доказательства теоремы.

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

Серьезным стимулом развития теории случайных графов как самостоятельного раздела теории вероятностей стала и та роль, которую случайные графы играют в различных приложениях. Здесь можно говорить и об алгоритмических аспектах теории графов, и о применении моделей случайного графа для статистического анализа различных сложных сетей - в том числе социальных, биологических и пр. (см. [1], [2], [3]). Во всяком случае на нынешнем этапе своего становления наука о случайных графах имеет как значительную теоретическую, так и огромную практическую со ставляющие.

Систематическое изучение случайных графов было инициировано П. Эрдешем и А. Реньи, которые предложили простейшую и ставшую уже классической модель случайного графа, основанную на схеме испытаний Бернулли (см. [4], [5], [6]). Впрочем, разрозненные работы о случайных графах появлялись и гораздо раньше, поскольку сама идея крайне естественна. Достаточно интересную библиографию подобного сорта можно найти, например, в книге [7].

За те без малого полвека, которые прошли с момента появления упомянутых публикаций, модель Эрдеша - Реньи была очень глубоко исследована (см. [1], [7], [8], [9]). С одной стороны, это привело к изучению многочисленных более сложных моделей, которые подчас точнее отражают реальность (см. [1], [2]). С другой стороны, это позволило по-новому взглянуть на самые разные задачи комбинаторного анализа, допускающие интерпретацию в терминах графов. Имея на руках мощные вероятностные технологии для изучения свойств графов, мы можем отныне с тем же успехом применить их (при необходимости, серьезно доработав) и для исследования других классических проблем комбинаторики.

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

Проблеме Нелсона - Эрдеша - Хадвигера посвящено огромное количество работ (см., например, [10], [11], [12], [13], [14], [15], [16], [17], [18]). По-видимому, первым, кто предложил использовать технику теории вероятностей для изучения свойств "графов расстояний" (т.е. графов с множеством вершин — точек в пространстве и ребер — пар точек на заданном расстоянии), был все тот же Эрдеш. Позднее вероятностный метод применялся в этой области неоднократно (см., например, [13], [19], [20]).

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

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

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

Актуальность темы диссертации

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

Говоря точнее, речь идет прежде всего о случайном графе G(n,p), с рассмотрения которого Эрдешем и Реньи на рубеже 50ых - бОых годов прошлого столетия, по существу, и началась вся современная и многогранная вероятностная теория случайных графов (см. [1] - [9]).

Как уже упоминалось во введении, вероятностная трактовка комбинаторных и геометрических задач, допускающих теоретико-графовые интерпретации, исключительно' важна и плодотворна. Ее актуальность подтверждается и обилием работ, опубликованных крупнейшими специалистами в соответствующих областях за прошедшие с середины XX века десятилетия (см. [8], [13] - [16], [19], [20]).

Также не вызывает сомнений значимость той конкретной комбинаторно-геометрической проблемы, вероятностной интерпретации которой посвящена данная диссертация, — проблемы Нелсона - Эрдеша — Хадвигера о раскраске метрического пространства. Достаточно опять же процитировать лишь некоторые из книг и обзоров, в которых она детально изучается (см. [10] - [18]).

Интересующая нас вероятностная характеристика - это величина t(d, п,р, х), равная максимальному к, при котором в модели G(n,p) с большой вероятностью случайный граф содержит такой индуцированный подграф на к вершинах, что у него хроматическое число не меньше х и он изоморфен какому-либо графу расстояний в Если при всех к вероятность описанного события мала, то величина t(d,n,p,x) полагается равной нулю.

Задача об отыскании величины t(d,n,p,x) глубоко мотивирована работами Эрдеша (см., например, [21]). Кроме того, именно в такой постановке она рассматривалась в цикле работ A.M. Райгородского [22] - [24].

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

Цель и задачи исследования

Цель исследования в разработке вероятностных методов теории случайных графов и в получении с помощью этих методов достаточно точных оценок величины t(d,n,p,x) при различных соотношениях и зависимостях между параметрами.

Научная новизна полученных результатов

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

Практическая значимость полученных результатов

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

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

1. Пусть при п —> оо выполнено: d(n) = const или d(n) —»■ оо. Тогда для любого е > 0 существует N, такое, что при всех п > N и при любых х, d 1 и 2 имеем теорема 3).

2. Пусть при п —» оо выполнено: d(n) = const или d(n) —> оо. Тогда для любого е > 0 существует N, такое, что при всех п > N и при любых х, ^ > 1 и

Р>

2(d + 2)!)i 2 d-1

1 + е) (d + 2)8+з In п имеем теорема 3).

1 + е) с/ + 2)8 Inn

Р'

3. Пусть р таково, что рпа —> оо и (1 — р)па —> оо для любого фиксированного а > 0. Тогда, каковы бы ни были заданные наперед d: х < (здесь ~~ хроматическое число пространства, см. §1.2) и е, найдется по, начиная с которого при всех п выполнена оценка t(d,n,p,X) > 2(1-е)Йг (теорема 4).

1-р

Личный вклад соискателя

Все результаты диссертации получены соискателем самостоятельно.

Апробация результатов

Результаты диссертации докладывались на IX международном семинаре "Дискретная математика и ее приложения", посвященном 75-летию со дня рождения академика О.Б. Лупанова (Москва, 2007 г.), на Ломоносовских чтениях в Московском государственном университете, а также на кафедральном семинаре кафедры математической статистики и случайных процессов механико-математического факультета МГУ, на семинаре проф. Б.М. Гуревича в МГУ, на семинаре проф. С.В. Конягина в МГУ и на семинарах д.ф.-м.н. A.M. Райгородского в МГУ.

Опубликованность результатов

Результаты диссертации опубликованы в работах [37] -[40] списка литературы. Всего по теме диссертации опубликовано 4 работы.

Структура и объем диссертации

В диссертации имеется введение, общая характеристика работы, три главы, список литературы. Полный объем 64 страницы, из них 5 страниц занимает список литературы (40 наименований).

1. В. Bollobas, Random Graphs, Cambridge Univ. Press, Second Edition, 2001.

2. R. Durrett, Random Graph Dynamics, Cambridge Univ. Press, 2006.

3. A.M. Райгородский, Экстремальные задачи теории графов и анализ данных, НИЦ "Регулярная и хаотическая динамика", 2009.

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

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

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

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

8. Н. Алон, Дж. Спенсер, Вероятностный метод, Бином: Лаборатория знаний, Москва, 2007.

9. S. Janson, Т. Luczak, A. Rucinski, Random Graphs, Wiley, New York, 2000.

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

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

12. A.M. Райгородский, Хроматические числа, Москва, МЦНМО, 2003.

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

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

15. P.K. Agarwal, J. Pach, Combinatorial geometry, Wiley, New York, 1995.

16. L.A. Szekely, Erdos on unit distances and the Szemeredi -Trotter theorems, Paul Erdos and his Mathematics, Bolyai Series Budapest, J. Bolyai Math. Soc., Springer, 11 (2002), 649 666.

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

18. А. Сойфер, Хроматическое число плоскости: его прошлое, настоящее и будущее, Мат. просвещение, Вып. 8, 2004.

19. М. Penrose, Random Geometric Graphs, Oxford University Press, 2003.

20. B. Aronov, J. Pach, M. Sharir, G. Tardos, Distinct distances in three and higher dimensions, Combinatorics, Probability and Computing, 13 (2004), 283 293.

21. P. Erdos, Unsolved Problems, Congress Numerantium XV Proceedings of the 5th British Comb. Conf. 1975, (1976), 681.

22. A.M. Райгородский, Проблема Нелсона Эрдеша - Ха-двигера и вложения случайных графов в геометрические, Доклады РАН, 403 (2005), N2, 169 - 171.

23. A.M. Райгородский, Раскраски пространств и случайные графы, Фундаментальная и прикладная математика, 11 (2005), N6, 131 141.

24. A.M. Райгородский, Проблема Нелсона Эрдеша - Ха-двигера и реализация случайных графов в пространстве, Успехи матем. наук, 61 (2006), N4, 195 - 196.

25. В. Bollobas, Threshold functions for small subgraphs, Math. Proc. Camb. Phil. Soc., 83 (1981), 433 436.

26. Ф. Харари, Теория Графов, Москва, "Мир", 1973.

27. N.G. De Bruijn and P. Erdos, 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.

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

29. H. Hadwiger, Uneldste Probleme N40, Elemente der Math., 16 (1961), 103 104.

30. O. Nechushtan, On the space chromatic number, Discrete Math., 256 (2002), 499 507.

31. JI.JI. Иванов, Оценка хроматического числа пространства R4, Успехи матем. наук, 61 (2006), N5, 371 372.

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

33. D.G. Larman, С.A. Rogers, The realization of distances within sets in Euclidean space, Mathematika, 19 (1972), 1 -24.

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

35. В. Bollobas, The chromatic number of random graphs, Com-binatorica, 8 (1988), 49 56.

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

37. C.B. Нагаева, О вложимости конечных графов расстояний с большим хроматическим числом в случайные графы, Доклады РАН, 418 (2008), N1, 19 22.

38. С.В. Нагаева, A.M. Райгородский, О вложимости конечных графов расстояний с большим хроматическим числом в случайные графы, Итоги науки и техники, "Современная математика и ее приложения", 62 (2009), 47 66.

39. С.В. Нагаева, A.M. Райгородский, О реализации случайных графов графами расстояний в пространствах фиксированной размерности, Доклады РАН, 424 (2009), N3, 315 317.