Содержание к диссертации
Введение
1: Постановка задачи и формулировки результатов 12
1.1 Определение и свойства случайных графов 12
1.2 Несколько слов о проблеме Нелсона - Эрдеша - Хадвигера 13
1.3 Трудность проблемы Нелсона - Эрдеша - Ха двигера 16
1.3.1 Интерпретация задачи в терминах случайного графа 16
1.3.2 Формулировки результатов 19
1.4 Комментарии 21
2: Доказательство теоремы 3 26
2.1 Основная часть доказательства теоремы 3 26
2.1.1 Предварительные рассуждения 26
2.1.2 Неравенство Азумы 27
2.1.3 Нижняя оценка математического ожидания величины Ym,d+2 28
2.1.4 Завершение доказательства теоремы 3 30
2.2 Доказательство леммы 1 37
2.2.1 Предварительные рассуждения 37
2.2.2 Асимптотика для M\W\ 39
2.2.3 Завершение доказательства леммы 50
3 Доказательство теоремы 4 54
3.1 Основная идея 54
3.2 Отыскание змеев в случайных графах 55
3.3 Оценка математического ожидания 56
3.4 Оценка второго момента и завершение доказательства теоремы 57
- Несколько слов о проблеме Нелсона - Эрдеша - Хадвигера
- Нижняя оценка математического ожидания величины Ym,d+2
- Завершение доказательства леммы
- Оценка второго момента и завершение доказательства теоремы
Введение к работе
Теория случайных графов - это современный и бурно развивающийся раздел комбинаторной теории вероятностей, который появился в середине 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(d + 2)!)a р < '
(l + e)(d+2)8+3lnn
ih
имеем
(теорема 3).
"2(d + 2)! ,(^+2)4
2. Пусть при п —> со выполнено: d(n) = const или d(n) —> со. Тогда для любого є > 0 существует W, такое, что при всех п > N и при любых х, ^ > 1 и
p>f (2(d + 2)l)i Ч^
\(l + )(d + 2)8+hnn
имеем
(d+2)8lnn~
(1 + *)-
^,n,P,x) <
(теорема 3).
3. Пусть р таково, что рпа —»оои (1 — р)п —> со для любого фиксированного а > 0. Тогда, каковы бы ни были заданные наперед d, х < x0^d) (здесь x0^d) ~~ хроматическое число пространства, см. 1.2) и є, найдется по, начиная с которого при всех п выполнена оценка
*(<*,n,p,x) > 2(l-e)jrr (теорема 4).
1-р
Личный вклад соискателя
Все результаты диссертации получены соискателем самостоятельно.
Апробация результатов
Результаты диссертации докладывались на IX международном семинаре "Дискретная математика и ее приложения", посвященном 75-летию со дня рождения академика О.Б. Лупанова (Москва, 2007 г.), на Ломоносовских чтениях в Московском государственном университете, а также
на кафедральном семинаре кафедры математической статистики и случайных процессов механико-математического факультета МГУ, на семинаре проф. Б.М. Гуревича в МГУ, на семинаре проф. СВ. Конягина в МГУ и на семинарах д.ф.-м.н. A.M. Райгородского в МГУ.
Опубликованность результатов
Результаты диссертации опубликованы в работах [37] -[40] списка литературы. Всего по теме диссертации опубликовано 4 работы.
Структура и объем диссертации
В диссертации имеется введение, общая характеристика работы, три главы, список литературы. Полный объем 64 страницы, из них 5 страниц занимает список литературы (40 наименований).
Несколько слов о проблеме Нелсона - Эрдеша - Хадвигера
Задача вероятностной теории случайных графов, исследуемая в данной работе, возникла в связи с известной пробле- мой Нелсона - Эрдеша - Хадвигера, которая состоит в отыскании хроматического числа x( d) евклидова пространства M.d. Напомним, что x(Rd) - это минимальное количество цветов, в которые можно так раскрасить пространство M.d, чтобы не было одноцветных точек на расстоянии 1: Можно переформулировать проблему Нелсона - Эрдеша -Хадвигера в терминах теории графов. Для этого рассмотрим (бесконечный) полный граф расстояний G = (V , Е ), у которого множество вершин V совпадает с Ша, а множество ребер Е состоит из "отрезков" длины единица: Поскольку хроматическим числом графа G называется величина х( ) равная минимальному числу цветов, в которые можно так раскрасить вершины графа G, чтобы никакие вершины одного цвета не были соединены ребром (см. [26]), то ясно, что x( d) — Более того, из теоремы П. Эрдеша и Н.Г. де Брейна (см. [27]) следует, что если хроматическое число (бесконечного) графа конечно, то оно достигается на некотором его конечном подграфе. Таким образом," x( d) = maxx(G0 гЛе максимум берется по всем конечным подграфам полного графа расстояний Gd . Такие конечные графы мы будем называть конечными графами расстояний. Относительно проблемы Нелсона - Эрдеша - Хадвигера в разное время были получены многочисленные результаты (см. [10] - [18]). В частности, известны следующие оценки величины х( )- Очевидно, что для размерности d = 1 хроматическое число удовлетворяет соотношению хО 1) = 2. Однако уже в случае плоскости {d = 2) точного равенства нет, а оценки, найденные в 1961 году (нижняя - братьями Мозерами (см. [28]), верхняя - Г. Хадвигером (см. [29])), не могут быть улучшены до сих пор: Нижная оценка хроматического числа в размерности d = 3 была улучшена сравнительно недавно: в 2002 году О. Не-чуштаном (см. [30]) было получено неравенство которое удалось обобщить на размерность d = 4 в 2006 году Л.Л. Иванову (см. [31]): Самые хорошие на сегодняшний день верхние оценки в размерностях d — 3 и d = 4 принадлежат Д. Кулсону (см. [32]): Также интересны и оценки x( d) ПРИ растущем d.
Имеются следующие результаты: Верхняя оценка получена Д. Ларманом и К.А. Роджерсом в 1972 году (см. [33]). Нижняя - A.M. Райгородским в 2000 году (см. [34]). Видно, что зазор между нижними и верхними оценками велик даже для случая d = 2, а при d — со этот зазор растет экспоненциально. В связи с этим в работах [22], [23], [24] A.M. Райгородский, следуя Эрдешу (см. [21]), ввел некоторую величину, в определенном смысле характеризующую трудность отыскания в M.d конечного графа расстояний с большим хроматическим числом. В следующих разделах мы определим и исследуем эту величину. 1.3 Трудность проблемы Нелсона - Эрдеша — Ха-двигера 1.3.1 Интерпретация задачи в терминах случайного графа Пусть при п — со заданы некоторые функции d(n), р(п), х(п) и є(п). Мы предполагаем, что при каждом п выполнено р{п) Є [0,1], є(п) Є (0,1), d(n) Є N, х(п) Є N. Зафиксируем п и положим d — d(n), р = р(п), х — х(п) Е — є(п). Для каждого к — 1, ...,п рассмотрим свойство Qk случайного графа в модели G(n,p): в графе G = (V, Е) є Оп существует такой индуцированный подграф Н = (U,F), что \U\ — к, х{Щ X и Н изоморфен некоторому конечному графу расстояний в M.d. Положим Прокомментируем введенное определение. Пусть при данных значениях параметров получилось t(d, п, р, %, є) — 0. Возьмем совершенно произвольное натуральное t п. Тогда Pn(Qt) є- Каждому конечному графу расстояний H — (U, F) в Rd, у которого \U\ t и х(Ю Х сопоставим множество А(Н) Є Sn таких графов G Є Qn, что G содержит изоморфную копию Н в качестве индуцированного подграфа. Получается, что Рп I \JA(H) ] є. Иными словами, несмотря на то, что, казалось бы, графов расстояний Н, обладающих указанными свойствами, много и каждому из них отвечает достаточно богатое множество А[Н), мера объединения всех таких множеств А(Н) сравнительно мала. При этом абсолютно не важно, много вершин в графе Н или мало. Можно сказать и еще по-другому: каково бы ни было t, возьмем мы любое п t и каждому t - вершинному графу расстояний ві с достаточно большим хроматическим числом сопоставим целую совокупность графов на п вершинах, которые этот граф содержат в качестве индуцированного подграфа; и все равно графов в G(n,p) получится совсем не много. Это косвенно свидетельствует о том, что в M.d мало попарно неизоморфных графов расстояний с большим хроматическим числом.
Похожий комментарий можно привести и в случае t(d, п,р, х, є) t. Разумеется, чем меньше при данном п величина є, тем интереснее. Однако несомненный интерес представляет даже случай є = . Мы не станем перегружать нашу работу чересчур громоздкими выкладками и потому изучим лишь Пусть Xd - это самая лучшая известная нижняя оценка величины х(М ). Например, xi = 4. В принципе, для дальнейшего изучения наиболее значима именно ситуация, когда Как раз в ее рамках проясняется, отчего же столько лет никому, например, не удается уточнить оценку х(М2) 4. Тем не менее, времена меняются, и величине Xd ничто не мешает меняться вместе с ними. Посему мы будем получать результаты относительно t(d,n,p,x), но всякий раз будем приводить их следствия при х — Xd с нынешним Xd- Отметим, что впервые мотивировка рассмотрения величины t(d,n,p) была дана A.M. Райгородским в работах [22], [23], [24]; там же был установлен ряд оценок этой величины. В настоящей диссертации мы получим весьма точные нижние и верхние оценки для t(d,n,p,x)i практически закрывая во многих случаях задачу. Попытаемся понять заранее, какова зависимость, например, верхних оценок от величины х- Заметим, что, по существу, свойство Q&, за счет которого определялась величина t(d,n,p,x), состоит из двух условий: граф Н имеет х{Н) X, и граф Н реализуется в W1 как граф единичных расстояний. Понятно, что если х, например, больше, чем п, то t(d,n,p,x) = 0. В то же время, если при некоторых х и к свойство Qk выполнено, то при том же х выполнены и все Qi с I к, т.е. в этом случае t(d, п,р, х) — п (в предположении, что второе условие имеет место). Значит, если не думать об условии реализуемости графа в пространстве, то условие х{Н) X работает, как "переключатель": либо искомая величина есть 0, либо п. Таким образом, трудно рассчитывать на то, что значение х сильно повлияет на нетривиальные верхние оценки: либо сразу же окажется, что t(d,n,p,x) 05 либо не возникнет ничего лучшего, нежели t(d, n,p, x) n, что и так очевидно. Из сказанного следует, что получение верхних оценок для t(d,n,p,x), к каковому мы, в частности, стремимся, будет в максимальной степени зависеть именно от вложимости случайного графа в полный граф расстояний, а не от его хроматического числа (если, конечно, не говорить про случаи t(d, п,р, х) — 0).
Нижняя оценка математического ожидания величины Ym,d+2
Выполнена следующая теорема (см. [1], [8]). Теорема 5 (Неравенство Азумы). Пусть ZQ,...,ZS - мар-тингалънал последовательность на некотором вероятностном пространстве (&,Ъ,Р). Предположим, что ZQ = const и что \Zi{uj) — Zi-i(uS)\ 1 для всех і = 1,.., s и UJ Є Q. Тогда для любого А 0 справедливо: P(ZS — ZQ Заметим, что неравенство Азумы играет центральную роль при доказательстве теорем о плотной концентрации тех или иных случайных величин около своих средних значений. Для оценки хроматического числа "почти всякого" случайного графа оно было применено Б. Боллобашем в работах [35], [36]. Но вернемся к нашей задаче. По случайной величине Ym;d+2, возникшей в предыдущем параграфе, построим некоторую мартингальную последовательность ZQ, ..., ZQI на вероятностном пространстве G(m, р). А именно, рассмотрим множество U, \U\ = m, являющееся множеством вершин для каждого графа Н из G(m,p). Пусть ei,...,ec2 - ребра полного графа на U. Для произвольного графа Н = (U, F) положим (ср. [8]) (8) Напомним, что величина Y на пространстве случайных графов называется липшицевой по ребрам, если \Y{H) —Y{H )\ 1 для любых Н и Н , отличающихся друг от друга не более чем на одно ребро. Нетрудно видеть, что Ymjd+2 обладает этим свойством, а значит, \Zi{H) — Zi-i(H)\ 1 для любого г = 1,..., С и любого Н из G(m,p). При этом очевидно, что ZQ = MYm +2, a Zci = Ymjli+2- Таким образом, применимо неравенство Азумы с Л = —гт і и в результате получаем, что Теперь нам необходимо как можно точнее оценить снизу величину MYmjd+2, и это мы сделаем в следующем пункте. Лемма 1. Пусть при п — оо выполнено: d(n) = const или d{n) —» со. Пусть, далее, либо d любое и р , либо d 10 и p . Тогда имеют место следующие четыре ситуации. 1. Пусть d = const при п — оо. Пусть, далее, т = т(п) — оо при п — оо и т(п) Є {1, ...,п}. Предположим, что р = р(п) т +1ц){т), где w(m) — оо, т — оо, « Для любого фиксированного а 0 справедливо w(m) = о(та).
Пусть, наконец, выполнено условие Тогда MYm +2 Л и(1 + S(m)) с некоторым 6(т) = о(1). . Пусть d = const при п — оо. Пусть, далее, т — т(п) — оо npw п —- оо и га(тг) {1,...,п}. Предположим, что р = р{п) m 3+2w(m), где w(m) = 0(1), т — оо. Тогда оо. Предположим, что р = p(n) ra_3+2u (m)d+2, причем ew{m) = (d + 2) + /(d + 2), где f(d +2)= o{d) и f(d + 2) (I + /?) ln(d + 2) с произвольным /3 0. Пусть, наконец, выполнено условие Тогда MYmjd+2 м+г) + (m)) с некоторым S(m) = о(1). . Пусть d = rf(n) —» оо при n — оо. Пусть, далее, т{п) Є {1,...,п} и т = т(п) — оо, со. Предположим, что р = р(п) т d+2w(m)d+2, причем ew(m) = {d+2) + f{d + 2), где f{d+2) ln(rf+2). Тогда MYmtd+2 = MXmjd+2(l + 5(m)) c некоторым 6(m) — o(l). В следующем пункте мы применим лемму для завершения доказательства теоремы. Отметим, что в дальнейшем нам понадобятся только первый и третий пункты утверждения леммы. Тем не менее, лемма представляет самостоятельный интерес, так как в ней дается практически исчерпывающее исследование поведения математического ожидания величины Ym}d+2- Подробное доказательство леммы мы приведем в параграфе 2.2. 2.1.4 Завершение доказательства теоремы 3 Пусть дано произвольное є 0. Пусть, кроме того, даны функции d(n) и р(п), а при фиксированном п - числа р = р(п) и d — d(n). Ищем т = т(п), опираясь на (5,6,7,9): Заметим, что мы имеем право искать т из неравенства поскольку Далее, величину MYm +2 мы оцениваем с помощью леммы. В этой оценке и проявится зависимость m от р, которая до сих пор была не очевидна. В любом случае нам понадобятся некоторые ограничения на т, помимо ограничения (11). Рассмотрим отдельно случаи d — const и d —» оо. Случай d = const. Мы вольны выбрать любой из двух соответствующих пунктов леммы, но из некоторых соображений мы выберем первый из них. Тем самым мы имеем следующие ограничения на т: Еще раз подчеркнем, что d(n) и р(п) нам даны, вид функции 6i(m) при желании можно конкретизировать (нам это, впрочем, не понадобится), а w(m) мы можем выбирать более или менее произвольно. Таким образом, система условий (12) - целиком на га. Разрешим как можно аккуратнее каждое из неравенств в этой системе относительно т и, сравнивая полученные ограничения, найдем оптимум.
Предположим, (13) оо. Более при достаточно больших п. Итак, неравенство (13) влечет оценки (а) и (6) из (12). Заменим в (13) величину 1 + 5\{т) на j при больших п, так что неравенство примет вид: Теперь посмотрим на условие (с) из системы (12). Фактически нужно лишь проверить, что то и (16), а значит, и (с) будут иметь место. Но последнее неравенство справедливо тогда и только тогда, когда Итак, мы имеем систему условий которая влечет все неравенства из (12), кроме (d). Изучим неравенство (d). Положим w(n) — In In п. Если выразить w{n) в виде функции аргумента га = т(п), то w(m) = о(та) для любого а, так как за счет первого условия из (18) т Inn. В результате условие (d) превращается в неравенство Если же p nnlnnW+2 т0 выполнено обратное неравенство. Таким образом, имеем две системы на га: при достаточно большом п. Значит, оптимальное решение системы (21) при любом d имеет вид га = pt Объединяя полученный результат с результатом системы (22), имеем окончательный ответ: Подставляя вместо С явное выражение, убеждаемся в справедливости утверждения теоремы в случае d = const. Случай d -+ оо. Как и в предыдущем случае, мы вольны выбрать любой из двух подходящих пунктов леммы. Теперь уже, однако, ясно, что следует предпочесть ее третий пункт. Имеем, стало быть, следующие ограничения на т: Учитывая тот факт, что условия (a), (6), (с) последней системы совпадают с одноименными условиями системы (12), и действуя так же, как и в предыдущем случае, при достаточно больших п получаем равносильную (24) систему условий Отметим, впрочем, что на сей раз С не есть константа. Покажем теперь, что первое условие системы (25) ограничи-тельнее третьего. Для этого достаточно установить неравенство С w-yjp. Поскольку d — 00, формула Стирлинга мгновенно дает асимптотику С . В то же время мы знаем, что w -, а следовательно, гиу/р 0.8 при достаточно больших п, ведь у нас р \- Требуемое неравенство получено, и, стало быть, имеем систему Аналогично тому, как это было сделано в предыдущем случае, окончательно получаем: Таким образом, доказательство теоремы завершено. Пусть фиксированы функции га = т(п),р = p(n),d = d(n), удовлетворяющие условиям одного из пунктов леммы (на данном этапе доказательства нам не важно, о каком именно пункте идет речь). Рассмотрим пространство G(m,p) и случайную величину Хт +2 на нем (см. пункт 2.1.1).
Завершение доказательства леммы
Асимптотическая оценка MW найдена, таким образом, возникают две принципиально различных ситуации: первая ситуация соответствует пунктам 1 и 3 из леммы (в ее рамках мы показали, что MW = д(2)(1 + Si(m)), где Si(m) = о(1), т —» со); вторая ситуация соответствует пунктам 2 и 4 из леммы (в ее рамках мы показали,что MVT C g(d +- 1)). Ситуация 1. Для дальнейшего нам удобно выразить MW через Теперь для каждого фиксированного графа Н = (U, F) из G(m,p) рассмотрим множество % — %(Н) = {Ai,..., As}, состоящее из всех подмножеств А{ С U, таких, что \Ai\ = d+ 2 и Н\А{ Пусть С = &{Н) С %{Н) - это случайное подмножество множества %(Н), в которое каждое А; Є % попадает с вероятностью q Є (0,1) независимо от остальных Aj Є ОС. Здесь q - это величина, оптимальный выбор которой мы осуществим позднее. Вспоминая, что граф Н случайный, получаем множество случайных пар (Н, С(Н)), вероятность каждой из которых естественно положить равной Таким образом, на описанном пространстве Рассмотрим множество W = W (H,G(H)), аналогичное W: Из каждой пары, принадлежащей W, выберем один произвольный элемент. Возникнет совокупность {В\, ...,Bt} С Є, где t \W \. Положим Є = Є (Я) = Q\{Bb ..., Bt}. Тогда Є Є-Ж ,идлялюбьіхЛ,Б Є Є выполнено АГ\В 1, то єсть (d+2) - клики Н\А и Н\в пореберно не пересекаются, а значит, Утд+2(Н) С (ІЇ) и, следовательно, Так как последнее выражение есть квадратичная функция по q , то ее максимум асимптотически достигается в точке где 6(т) — о(1), га — со, ив ситуации 1 (то есть в случаях 1 и 3) лемма доказана. Ситуация 2. Здесь MW C g(d + 1), где С - константа. Будем действовать так же, как и в предыдущей ситуации. Рассмотрим величину C g(d+ 1) подробнее: Выражая последнее через MXmtd+2 = C 2pCd+2, получаем, что Для каждого графа Н строим множество X = Х (Н) С X — Х(Н), удаляя из X по одному представителю из каждой пары, принадлежащей множеству W = W{H). Тогда и, следовательно, поскольку d — о (ms J. Таким образом, MYm,d+2 MXmjd+2(l + SA(m)), где 54(ra) — o(l), m — со. В то же время очевидно, что MYmjd+2 MXmid+2. Значит, MYm4+2 = MXm,d+2{l + 5{m)), где 5(m) = o(l), m —» oo, и во второй ситуации лемма доказана.
Пусть к = 2(1 — g)Irn" Ясно, что, ввиду наших предположений о скорости изменения величины р, справедлива (грубая) оценка к п. Таким образом, 1 к п. Допустим, далее, нам удалось найти такой граф расстояний Н = (W, F) в Rd, что \W\ = к, х(Н) X и вероятность наличия в случайном графе G Є Q,n индуцированного подграфа, изоморфного Н, больше 1/2. Тогда, разумеется, мы показали, что t(d,n,p,x) к. Рассмотрим любой граф Г в M.d с хроматическим числом Х- По условию он непременно существует. Обозначим через D количество его вершин, а через е количество его ребер. Понятно, что величины D, с зависят лишь от d и %, каковые у нас фиксированы. Иначе говоря, с ростом п число О есть константа, в то время как к — со. Возьмем любую вершину графа Г и "вытянем" из нее простую цепь такой длины, чтобы в новом графе Н = (W, F) оказалось ровно к вершин. Очевидно, Н - граф расстояний в Md и у него \W\ = к: х(ії") Х- Назовем такой граф воздушным змеем: в самом деле, Г - это "голова змея", а простая цепь — "веревочка", присоединенная к голове. Все, что теперь следовало бы показать, — это то, что с вероятностью, близкой к единице, случайный граф в модели G(n,p) содержит воздушного змея в качестве индуцированного подграфа. В следующем параграфе мы сведем доказательство интересующего нас утверждения к отысканию первых двух моментов некоторой случайной величины. Пусть V = {1,..., п} — множество вершин случайного графа в модели G{n,p). Пусть, далее, «Si,..., «S - все к-элементные подмножества множества V. На каждом из них можно построить определенное число различных змеев. Однако мы зададимся каким-либо конкретным змеем Z{ на Si, г = 1,..., С%, и в дальнейшем будем работать только с ним. Положим для каждого % — 1,..., С 1, если Zi — индуцированный подграф графа G, О — иначе. Пусть, кроме того, - число выделенных индуцированных fc-вершинных змеев в графе G. Понятно, что для каждого конкретного графа G последняя величина зависит от изначального выбора змеев Z\,..., Z k. Однако на ее математическое ожидание и прочие моменты способ фиксации змеев на множествах S{ не влияет. Этим мы и воспользуемся. Нам нужно показать, что Рп{Хп,к 1) 2 или эквивалентно, Рп(ХПгк 0) -. Применим неравенство Чебышева: Дальнейшее искусство состоит в обосновании оценки В следующем параграфе мы покажем, что при нашем выборе параметров математическое ожидание Хп к стремится к бесконечности.
В параграфе 3.4 мы найдем второй момент величины ХП;к и завершим доказательство теоремы. 3.3 Оценка математического ожидания Из линейности математического ожидания сразу же получается соотношение Замечая, что одновременно к —»оо при п —» со и к — о (па) с любым а 0; полагая, кроме того, С — с — 0, имеем (при п щ) с учетом формулы Стирлинга и с подходящими Прежде всего заметим, что DXn k — МХ\ к — {МХп )2- Вычитаемое нам известно: оно стремится к бесконечности, и, если мы покажем, что второй момент асимптотически ему равен, то нужная нам оценка будет установлена, а доказательство теоремы завершено. Итак, Очевидно, (-) = - пі а значит первое слагаемое в последнем выражении есть МХп = о ( (MXn k) ) Следовательно, остается подтвердить асимптотику Суммирование в левой части предполагаемой асимптотики идет, фактически, по всем упорядоченным парам i,j, которым отвечают различные змеи Z{, Zj. Обозначим через Vij количество общих вершин в таких Z{,Zj. Понятно, что О v j к — 1. Тогда м ( лм) =ЁЕм( «) = Второе слагаемое есть, разумеется, Поскольку fc = о(л/гг), имеем C%_k/Cn 1. Таким образом, для обоснования интересующей нас асимптотики надо проверить соотношение М «»Х«) = о ((MXn,kf) . Нетрудно видеть, что при данном t коль скоро г, j таковы, что Vij = t. Более того, величины Дг-равномерно ограничены по г, j, а потому рассмотрим Оценим сверху первую часть последнего произведения. Поскольку l t k—1нк=о (па) с любым а О, имеем при достаточно большом п По аналогичным причинам, при больших п Очевидно, суммируя последнюю величину по t = 1,..., к-1, получаем о(1), и теорема доказана.
Оценка второго момента и завершение доказательства теоремы
Теория случайных графов - это современный и бурно развивающийся раздел комбинаторной теории вероятностей, который появился в середине 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) при различных соотношениях и зависимостях между параметрами.
