Предельные теоремы для случайных графов и карт

• Автор: Крикун, Максим Андреевич
• Шифр специальности: 01.01.05
• Научная степень: Кандидатская
• Год защиты: 2003
• Место защиты: Москва
• Количество страниц: 87 с. : ил.

Оглавление
Введение

1 Случайные деревья

1.1 Случайная модель и основные результаты

1.2 Классификация

1.3 Асимптотика высоты в транзиентном случае

2 Случайные триангуляции с границами

2.1 Определения

2.2 Основные результаты

2.3 Рекуррентные соотношения

2.4 Анализ особенностей
2.5 Триангуляция с одной границей
2.6 Триангуляция с двумя границами
2.7 Триангуляции без корня
3 Локальные свойства бесконечной случайной сферы
3.1 Определения
3.2 Модель
3.3 Скелет
3.4 Статистическая сумма
• 3.5 Предельные распределения
4 Асимптотическое число карт на компактных ориентируемых
поверхностях
4.1 Определения
4.2 Доказательство
Список литературы

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

Случайные деревья
Глава 1 посвящена исследованию случайного процесса, состояниями которого являются конечные деревья. В рассматриваемой модели новые ребра добавляются с интенсивностью А, а листья дерева могут быть удалены с интенсивностью д. Нас интересует, прежде всего, классификация (условие эргодичности / транзиентности) и асимптотика высоты дерева в транзиентном случае.
Такой процесс похож на простейший процесс размножения-гибели, и ясно, что он будет транзиентен при д < А. Однако поскольку не всякая вершина дерева может быть удалена, транзиентность сохраняется и при некоторых д > А. Распределение время жизни некоторой отдельно взятой вершины становится зависимым от ее потомков. Лемма 1.1 описывает плотность этого распределения как решение системы интегрально-дифференциальных урав-• нений (1.1), (1-2), которая впервые была получена автором в статье [11].
На анализе этой системы основана теорема 1.1, в которой дана полная классификация процесса. Оказывается что он эргодичен при А/д < е~г, и транзиентен в противном случае. Интересно, что нуль-возвратность при критическом значении параметров, обычная для подобного рода задач, в данной задаче не имеет места.
В транзиентном случае высота дерева растет линейно по времени. В теореме 1.2 доказано, что с вероятностью единица имеет место предел
(->00 £

В случае чистого роста (ц = 0) скорость роста дерева составляет 5 = еА, что соответствует известным результатам для бинарных случайных деревьев, [5].
Эргодический случай был исследован в совместной работе с Г. Файолем и Ж-М. Ласгуттом [10]. Были получены предельные распределения для числа вершин и высоты дерева, а также рассмотрена обобщенная модель, в которой конечное число типов вершин обладает различными интенсивностями порождения потомков и гибели. Эти результаты в диссертации не приводятся.
Данная задача была предложена В.А. Малышевым в качестве элементар-ного случая граф-грамматики [8, 9]. С другой стороны, дерево с N вершинами может быть закодировано последовательностью длины 2N из двух символов; таким образом задача сводится к случайной грамматике [7], которая является, однако, контекстно-зависимой. Уже в таком простейшем случае требуется нетривиальный анализ, что служит подтверждением сложности исследования контекстно-зависимых случайных грамматик.
Случайные карты
Предметом исследования в главе 2 являются двумерные случайные объекты - многокорневые плоские триангуляции с несколькими границами.
Рассматриваются графы на плоскости, у которых все грани - треугольники, кроме нескольких помеченных граней, которые называются границами триангуляции; требуется чтобы триангуляция была двусвязна и никакие две границы не имели общих точек. Таким образом, триангуляцию с несколь-Ф кими границами можно считать триангуляцией связной (но не обязательно
односвязной) области на плоскости с конечным числом компонент связности границы.
В корневой триангуляции выделяется "начало координат": вершина графа исходящее из нее ребро, которое называется корнем. Корневые триангуляции считаются эквивалентными, если существует гомеоморфизм плоскости, переводящий ребра в ребра, вершины в вершины, и сохраняющий корень. Таким образом корневая триангуляция не имеет других автоморфизмов кроме тривиального.
Согласно общепринятому определению (см. [12]), корневое ребро выбирается на границе триангуляции; в нашем случае - на внешней границе, которая называется, соответственно, корневой, а остальные границы - внутренними.

Возьмем триангуляцию Т из класса Б*(И, ш, т!) и выберем среди секущих ребер, соединяющих вершины Ь, Ьт'+ крайнее - то, которое встречается первым после корневого ребра при обходе вершины Ь по часовой стрелке (см. рис. 2.3). Разрежем Т вдоль этого ребра на две части, триангуляцию общего вида Ті Є С {N1, то + 1) и Т2 Є ІЇ*(ІУ2, тп' + 1).
Рис. 2.3: Разрезание по секущему ребру
Таким образом
Б0(х, у, из) = 110( х, у)И0(х, из), (2.12)

.До (ж, га) = ^ т)^«;"1“2.
Далее, любая триангуляция Т может быть разрезана на Т £ С*(№Д 0) и Т2 £ Д*(ЛГ2,то) вдоль секущего ребра, параллельного корню (если такого секущего ребра нет, то пусть Т - особая триангуляция типа (2,0)). Следовательно
С(ЛГ,ш)= £ ОД»2)*«) №,т),

ио{х, у) = и0(х, 0)До(ж, у). (2.13)
Доказательство для к = 0 закончено.
Для общего класса £>*(1У, то,т';с*) применимо то же рассуждение с той разницей что каждый раз при разрезании триангуляции следует учитывать