Оглавление
Введение 4
Общая характеристика работы 7
1 Глава 1: Постановка задачи и формулировки результатов 12
1.1 Определение и свойства случайных графов . . 12
1.2 Несколько слов о проблеме Нелсона - Эрдеша
- Хадвигера................................. 33
1.3 Трудность проблемы Нелсона - Эрдеша - Хадвигера ......................................... 16
1.3.1 Интерпретация задачи в терминах случайного графа................................ 16
1.3.2 Формулировки результатов...............19
1.4 Комментарии...................................21
2 Глава 2: Доказательство теоремы 3 26
2.1 Основная часть доказательства теоремы 3 . . . 26
2.1.1 Предварительные рассуждения............26
2.1.2 Неравенство Азу мы.....................27
2.1.3 Нижняя оценка математического ожидания величины
УтМ*...................................28
2.1.4 Завершение доказательства теоремы 3 . 30
2.2 Доказательство леммы 1........................37
2.2.1 Предварительные рассуждения............37
2
2.2.2 Асимптотика для М|РГ| ..................39
2.2.3 Завершение доказательства леммы ... 50
3 Глава 3: Доказательство теоремы 4 54
3.1 Основная идея.................................54
3.2 Отыскание змеев в случайных графах............55
3.3 Оценка математического ожидания...............56
3.4 Оценка второго момента и завершение доказательства теоремы................................57
3
Введение
Теория случайных графов - это современный и бурно развивающийся раздел комбинаторной теории вероятностей, который появился в середине XX века и за прошедшие десятилетия оформился в многогранную и глубоко проработанную самостоятельную дисциплину. В основе теории лежит очень важная идея, состоящая в том, что мощные методы теории вероятностей должны существенно помочь исследованиям свойств графов, дать принципиально новый ракурс для рассмотрения классического комбинаторного объекта. И действительно, зачастую нам интересно знать, с какой ’’степенью достоверности” зыполнено то или иное свойство графа: скажем, граф, скорее, связен, или же, напротив, более правдоподобно предположение о его несвязности. Разумеется, строгий смысл в понятие достоверности вкладывается именно с помощью вероятности.
Серьезным стимулом развития теории случайных графов как самостоятельного раздела теории вероятностей стала и та роль, которую случайные графы играют в различных приложениях. Здесь можно говорить и об алгоритмических аспектах теории графов, и о применении моделей случайного графа для статистического анализа различных сложных сетей - в том числе социальных, биологических и пр. (см. [1], [2], [3]). Во всяком случае на нынешнем этапе своего становления наука о случайных графах имеет как значительную теоретическую, так и огромную практическую составляющие.
Систематическое изучение случайных графов было инициировано П. Эрдешем и А. Реньи, которые предложили нро-
4
стейшую и ставшую уже классической модель случайного графа, основанную на схеме испытаний Бернулли (см. [4], [5], [6]). Впрочем, разрозненные работы о случайных графах появлялись и гораздо раньше, поскольку сама идея крайне естественна. Достаточно интересную библиографию подобного сорта можно найти, например, в книге [7].
За те без малого пол века, которые прошли с момента появления упомянутых публикаций, модель Эрдеша - Репьи была очень глубоко исследована (см. [1], [7], [8], [9]). С одной стороны, это привело к изучению многочисленных более сложных моделей, которые подчас точнее отражают реальность (см. [1], [2]). С другой стороны, это позволило по-новому взглянуть на самые разные задачи комбинаторного анализа, допускающие интерпретацию в терминах графов. Имея на руках мощные вероятностные технологии для изучения свойств графов, мы можем отныне с тем же успехом применить их (при необходимости, серьезно доработав) и для исследования других классических проблем комбинаторики.
Среди классических проблем, лежащих на стыке комбинаторики и геометрии и допускающих указанную теоретико-графовую интерпретацию, особое место занимает задача Нелсона - Эрдеша - Хадвигера о раскраске метрического пространства. Речь идет об отыскании минимального количества цветов, в которые можно так покрасить все точки пространства, чтобы между точками одного цвета не было расстояния из заданного наперед множества вещественных положительных чисел. Иными словами, ищется хроматическое число графа, вершинами которого служат точки метрического пространства, а ребрами - пары точек, отстоящих
5
друг от друга на некоторое расстояние из упомянутого множества.
Проблеме Нелсона - Эрдеша - Хадвигера посвящено огромное количество работ (см., например, [10], [11], [12], [13], [14], [15], [16], [17], '18]). По-видимому, первым, кто предложил использовать технику теории вероятностей для изучения свойств "графов расстояний" (т.е. графов с множеством вершин - точек в пространстве и ребер - пар точек на заданном расстоянии), был все тот же Эрдеш. Позднее вероятностный метод применялся в этой области неоднократно (см., например, [13], [19], [20]).
В диссертации рассматривается один из аспектов вероятностной проблематики теории случайных графов применительно к задаче Нелсона - Эрдеша - Хадвигера. Работа подразделяется на три главы. В первой главе дается история задачи, определяется основная величина, подлежащая дальнейшему исследованию, а также формулируются и сравниваются между собой центральные результаты диссертации. Во второй главе доказывается верхняя оценка основной величины. В третьей главе устанавливается нижняя оценка той же величины.
Автор глубоко признателен научному руководителю д.ф.-м.н. А.М. Райгородскому за постановку задач, постоянный интерес и внимание к работе.
б
- Київ+380960830922