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

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

На правах рукописи УДК 519.214

Крикун Максим Андреевич

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

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

статистика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

Москва, 2004

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

Научный руководитель: доктор физико-математических наук, профессор МГУ В. А. Малышев

Официальные оппоненты:

доктор физико-математических наук, в.н.с. В.Б. Приезжее кандидат физико-математических наук, в.н.с. С.А. Пирогов

Ведущая организация:

Санкт-Петербургское отделение Математического института им. В.А. Стек-лова РАН

Защита состоится 20 февраля 2004 года в 16 часов 15 минут на заседании диссертационного совета Д.501.001.85 в Московском Государственном Университете им. М.В. Ломоносова но адресу: 119992, ГСП-2, Москва, Ленинские горы, МГУ, механико-математический факультет, аудитория 16-24.

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

Автореферат разослан 20 января 2004 года.

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

2004-4

25354

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

Деревья и связанные с ними вероятностные задачи имеют широчайшее применение и встречаются, в частности, в теории массового обслуживания и анализе алгоритмов. При этом особое внимание обычно уделяется таким характеристикам как количество вершин и высота дерева. Рассматриваемая в диссертации модель случайное дерева является частным случаем граф-грамматики, введенной В.А. Малышевым.1 Случайная граф-грамматика задает марковский процесс на графах, определяя набор возможных подстановок, заменяющих один подграф на другой, и соответствующие им интенсивности. В диссертации рассматривается простейший случай, когда граф является деревом в котором новые вершины добавляются независимо в каждой точке с интенсивностью Л а листья удаляются с интенсивностью ц.

С другой стороны, стандартным способом дерево с N вершинами может быть закодировано последовательностью длины 2N из двух символов. Таким образом, задача сводится к случайной грамматике2 которая является, однако, контекстно-зависимой, что уже в таком простейшем случае требует нетривиального анализа. Общие случайные грамматики и L-системы в контекстно-свободном случае были исследованы А.И. Петровым3. Задачи о процессах рождения-гибели на графах, сходные с рассматриваемой в диссертации, рассматривались Пит-толом4 и Девроем5. в частности, последним была найдена скорость роста случайного дерева в случае соответствующем модели без удаления листьев ( = О, т.н. "чистый рост"). Близкие задачи, с ограничением

'Малышев В.А., Случайные графы и грамматики на графах Дискретная Мичемагика, 1998, 10, 2. 30-44.

^Малышев В.А., Случайны? грамматики. Математическое обо?рение, 1998. оЗ, 2, 107 134.

•4104ров А И., Контекстно-свободные L -системы, джтартапия, мех-мат МГУ, 2003.

1Pittel В., Note on the heights of random recurs«)« tree) and random m-ary search trees. Random Structures and Algorithms, 1994, 5,337-347.

'Dovroyo L., Branching processes tn the analysts of the height of trees Acta Tnformatica, 1087, 24, 277-298.

на максимальную степень вершин в дерево, рассматривались также Т. Лигеттом6 и А. Пухой7.

Задача перечисления плоских триангуляции впервые возникла в работах У. Татта8 в связи с задачей четырех красок. Был изобретен метод удаления корневого ребра, позволяющий выписать рекуррентные соотношения для количества триангуляции с данным числом треугольников и с данной длиной границы, которые затем удалось разрешить с помощью приема, получившего название "квадратичного метода". На этой технике основано множество работ, посвященных в основном перечислению' различных плоских карт, среди которых следует отметить работы Э. Бендера и др.9

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

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

"í.iggptt Т.М.. Monotonmty of conditional distributions aniqrowtii moieU on trert. Ann. РгоЫЪ. 2000, 28. lfiíS Iffl».

*Puha A.L., A Reversible Interacting Particle System on the Homogeneous Tree. Ph D. dissertation, Ciiiv. of California, Los Angeles, 1998.

"Tutte W., A Census of Planar Triangulations. Cañad. J. Math., 1962,14, 21-38.; Tutte W., On the enumeration of convex polyhedra. J. Comb. The., 1980, Ser. В 28, 2, 105-126.

'Bender E. A., Wormald N. C, The Asymptotic Number of Rooted Nonseprable Maps on a Surface. Journal of Combinatorial Theory, 1988, A 49, 370 380.: Bender E., Canfield E., Richmond L., The asymptotic number of rooted maps on a surface. II. Enumeration by vertices and faces.. J. Comb. Theory, 1093, A63, 318-329.

'"Малышев B.A., Гиббсовские « квантовые дискретные пространства. Успехи мат. наук, 2001, 56, В5, 117-171......

лучены в совместной работе.11 Случай двух границ рассматривается в диссертации впервые.

Случайные триангуляции возникают также в современной фичике. а именно в теории струн. Чтобы проанализировать поведение струны нужно уметь вычислять интеграл действия по всем траекториям с заданными начальным и конечным состояниями, что эквивалентно интегрированию по всем метрикам на двумерной поверхности. Одна из возможностей определить подобный интеграл — заменить двумерную поверхность с непрерывной кривизной кусочно-плоской триангуляцией, в которой кривизна сингулярна и сконцентрирована в вершинах треугольников, а интегрирование но всем метрикам заменить па суммирование повеем возможным триангуляциям, см. paботы Я. Амбьор-па12 и A.M. Полякова13.

Другая задача, касающаяся плоских триангуляции, возникла относительно недавно. Я. Амбьорн14 выдвинул предположение что внутренняя размерность случайной поверхности равна четырем. Согласно этому предположению, длина границы шара в случайной триангуляции пропорциональна квадрату радиуса, а количесгво треугольников в шаре — четвертой С1епени радиуса. О. Шрамм и О. Ангел10 доказали существование бесконечной случайной плоской триангуляции и получили оценки для скорости роста длины границы и площади с иоч-ностью до логарифмического множичоля. Несколько ранее подобная задача для случайных поверхностей, состоящих из квадратов, была решена Г. Шаффером16. Используя соотношение между квадрангу-ляциями и специальным образом размеченными деревьями, он пока-

"Knkun М , Malysbev V. V, Random Boundary of a Planar Map ш "Treads in Mathematics Mathematics and Computer buence", Ed D Cardy, A Mokkadem. BirkHauser, 2002

"Ambjorn J, Quantization of geometry. Lt Hurts at the 1994 Lei Houchcs Summer School "Fluctuating Geometries m Statistical Mechanics and Field Theory". 1994, arXiy hep th/9411179 "Поляков 4 M , Калибровочные поля u струны Удмуртский университет Ижевск, 1999 UJ Ambjorn, Y. Watabiki, Scaling m quantum gravity Xucl Phys 1995, В 445, 1, 129-142. 150. Angrl, О Schramm, Uniform Infinite Planar Tnangutalwns 2002,arXiv math PR/0207153 , О -Vngel, Ciovith and Percolation on the Uniform Random Infinite Planar Tnanqulation 2002, .irXiv math PR/0208123

"G Sthdeffer, Conjugation d'arbres el catles combmaloirts alealoires PhD thesis, University Bordeaux I, Burdeaiix, 1998; P. Chassamg, G. Schaeffer, Random Planar Lattices and Integrated Superbrouintan Excursion 2002, arXiv math CO/0205226, to appear in Probability Theorj and Related Fields.

зал, что профиль квадратуляции, т.е. зависимость числа вершин от расстояния до корня, сходится к интегрированной супер-броуновской экскурсии17, 'примем диаметр случайной поверхности состоящей из N квадратов пропорционален N1/4.

В третьей главе диссертации уточняется результат О. Ангела, касающийся'длины границы тара в триангуляции. Для отношения l(R)/fir найдено невырожденное предельное распределение, при этом для доказательства используется оригинальная техника, включающая связь случайных триангуляции с критическими ветвящимися процессами особого вида с обращенным временем.

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

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

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

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

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

1TD.J. Alilous, Tree-based models ¡or random distribution о/ mass. J. Statist. Thys., 1993, 73 (3-4). (¡25-641.

'"Walsh Т., Lehman A., Counting rooted тара by genus. I. Journal of Combinatorial Theory (B), 1972, v. 13, 192-218.

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

3. Для бесконечной случайной триангуляции найдено предельное распределение профиля, обпаружеиа связь профиля бесконечной равномерно-распределенной случайной триангуляции с критическим ветвящимся процессом с показателем 1/2.

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

Методы исследования.

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

Теоретическая и практическая ценность.

Работа носит теоретический характер. Ее результаты могу'1 быть полезны в теории случайных карт, а также в математической физике и теории струн.

Апробация диссертации.

Основные результаты настоящей диссертации докладывались на Большом семинаре кафедры теории вероятностей МГУ под руководством член-корр. РАН, профессора А.Н.Ширяева, на семинаре Лаборатории больших случайных систем МГУ под руководством д.ф.-м.н., профессора В.А.Малышева, на семинаре Добрушинской математической лаборатории ИППИ РАН под руководством проф. Р.А. Миилоса и проф. М.С. Пинскера, на международной конференции "Mathinfo 2002"(2002, Версаль. Франция), на международной конференции "Polyhedral surfaces: geometry and сотЫпаШг^"(С-Петербург. 2003).

Публикации.

Основные результаты диссертации опубликованы в 4-х работах автора, из которых в соавторстве написаны 3. Их список приведен в конце автореферата.

Структура и объем работы.

Диссертация состоит из введения и четырех глав, разбитых на параграфы. Общий объем диссертации составляет 87 страниц. Список литературы включает 33 наименования.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Введение.

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

Глава 1.

В первой главе рассматривает! модель случайного дерева.

В параграфе 1.1 даются основные определения и кратно формулируются результаты. Случайное дерево О это марковская цень с непрерывным временем, состояниями которой являются конечные, корневые деревья. В начальный момент времени О состоит из единственной вершины. В любой вершине и £ н&зависимо с интенсивностью А > О может быть добавлено ребро с началом в V и с новой вершиной на конце: любая вершина кроме корня, инцидентная единственному ребру, может быть удалена с интенсивностью 0 вместе с этим ребром.

Качественное поведение таким образом определенной марковской цепи фактически зависит от соотношения параметров А/р = р. При она эргодична. при - транзиентна. Область нуль-

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

В параграфе 1.2 задача классификации поведения модели в зависимости от соотношения параметров сводится к анализу си-

стемы ингсгро-дифференциальных уравнений

«

£(«) = цехр{1(1-р{х))<ь},

р(г) = рсхр

о

^ = ^--¡-¡М-уШУ)

(2)

о

с начальным условием р(0) = 0. Функция р(1) является функцией распределения для времени жизни любой из вершин дерева, следовательно необходимо исследовать поведение р(I) в пределе < оо.

В подпараграфе 1.2.1 доказывается необходимость и достаточность выполнения условия р < е-1 для эргодичности процесса Для доказательства необходимости используется равенство р = Лте~Хт , где т -среднее время жизни вершины дерева. Поскольку 5ирх хе~х = е-1, из предположения конечности т следует р < е-1. Для доказательства досгагочносги строится последовательность функций Ркр), сходящаяся к единственному решению системы (1,2). При этом каждая из Рк{1) является функцией собственною вероятностного распределения с конечным средним т и существует конечный предел Иод-юо т* — т. так что предел последовательности рк(I) также является собственным распределением с конечным средним.

В подпараграфе 1.2.2 доказывается транзиентность процесса при р > е"1. Доказательство полностью аналитическое и также использует равенство р = хс~х

В параграфе 1.3 исседуется асимптотика высоты дерева в тран-зиентном случае. Высотой дерева И(0() = И(1) называется максимальное расстояние от точек дерева до корня, при этом длина одного ребра считается равной единице. Лемма 1.3 представляет собой закон нуля и единицы для событий

Вс = {Нтвир^ро< с}. С помощью Леммы 1.4 и Леммы -1.5 удастся найти значение с. для которого выполняются одновременно оба события. Оно совпадает с единственным положительным корнем уравнения

где

, а , /А(1 — йр*(з))\

а р*($) является преобразованием Лапласа функции Таким образом, с вероятностью единица Нт^«, Н^/Ь — 8 . В случае эргодичности процесса 6 = 0, в случае /х = 0 ("чистый рост") 8 =е.

Глава 2.

Во второй главе исследуются плоские триангуляции с несколькими границами.

В параграфе 2.1 даются необходимые определения и доказываются, основные свойства рассматриваемого класса триангуляции. Триангуляцией с несколькими границами называется граф на плоскости, в котором вес грани являются треугольниками, за исключением нескольких помеченных граней, которые называются границами триангуляции. Требуется, чтобы триангуляция была двусвязна и никакие две границы не имели общих точек, таким образом, триангуляцию с несколькими границами, можно считать триангуляцией связной (но не обязательно односвязной) области на плоскости с конечным числом компонент связности границы. Границы триангуляции считаются занумерованными и отличимыми. Триангуляция с N треугольниками, т ребрами на корневой границе и «!,..., ребрами на остальных границах называется триангуляцией типа

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

На множестве всех многокорневых триангуляции с N треугольниками и к границами вводится распределение, приписывающее каждой триангуляции вероятность 2~1ХМ(Т); где М(Т) - суммарная длина границ триангуляции Т; А • положительный параметр, 2 - нормирующий множитель.

В параграфе 2.2 перечислены основные результаты второй главы.

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

ций относительно количества треугольников и длины каждой из границ

получен алгоритм, позволяющий вычислять их в явном виде.

• Для триангуляции с одной границей получены предельные распределения длины границы ш{Ы) при N -4 с» . В зависимости от значений параметра А имеет место сходимость в разном масштабе. При А < 1/%/б, А = 1/\/б, А > 1/\/б существует предельное распределение соотвегственно для т(Ы), ,

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

А < 1Д/6

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

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

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

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

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

Глава 3.

Третья глава посвящена задаче о скорости роста границы R-окрестности корня в случайной триангуляции сферы при R —> оо.

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

гг.

гуляциями диска. Это отношение обозначается BGS.

В параграфе 3.2 формулируются и доказываются теоремы 3.2 и 3.3 о предельных вероятностях Р{В С S(N)} при N оо , где S(N) -равномерно-распределенная триангуляция сферы с N треугольниками.

В параграфе 3.3 определяется конструкция "екелета"триангуляции. Вначале триангуляция Т разбивается на последовательные слои. R-й слой представляет из себя подтриангуляцию в форме цилиндра, такую что вес точки нижней границы удалены на расстояние (R — 1) от корневой границы Т, а верхней - на R.

Треугольники с одним ребром па верхней границе слоя и одной вершиной ца нижней границе образуют шаблон слоя: совокупность треугольников, принадлежащих шаблонам слоев 1,...,Я. образуеп скелет триангуляции . Таким образом, скелет представляет собой триангуляцию со множеством дырок (гнезд). Согласно Лемме 3.2. при заполнении этих гнезд подходящими триангуляциями дисков произвольным образом получается некоторая окрестность корня радиуса R, причем каждая ил возможных окрестностей получается единственным способом из единственного скелета.

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

ние ребра гнезда, соответствующего этому треугольнику.

В параграфе 3.4 (Теорема 3.3) вычисляется "статистическая еум-ма"по всем слоям, учитывающая количество треугольников и длины границ. Если ¥(?) - некоторая функция, допускающая разложение в ряд Тейлора по г вблизи нуля, г) = с^ , то

где п = п(Ь), I = ¡(Ь), к = к(Ь) - количество треугольников и длины нижней и верхней границ в слое Ь соответственно, а А явно заданный линейный оператор.

Применение итераций оператора А0 = А(х0) к специально подобранным функциям позволяет оценить асимптотику моментов длины верхней границы ^-окрестности в случайной сфере. Итерации оператора Д, ВЫЧИСЛЯЮТСЯ В подпараграфе 3.4.2, для чего вводится "производящий оператор" М = Ац ; асимптотика моментов вычисляется в параграфе 3.5. Предельное распределение вычисляется в последнем параграфе третьей главы с помощью обратного преобразования Лапласа.

Глава 4. Четвертая глава посвящена задачи перечисления комбинаторных карт произвольного рода.

В параграфе 4.1 дается определение комбинаторной карты: это формальная тройка (2Е, Р, (—)), где 1Е множество "полуррбер"с четным числом элементов а Р и (—) две перестановки на этом множестве, причем (—) состоит из циклов длины два каждый. Такая конструкция определяет плоский граф на некоторой двумерной поверхности. Циклы перестановки (—) определяют ребра графа, циклы перестановки Р порядок ребер в каждой из вершин.

Используется следующее рекуррентное соотношение для числа ./'б.р корневых комбинаторных карт с р+ 1 вершинами и Ь + р ребрами

^ = £ Е 1 + (2(6 + Р)~ 1)^-1*, (3)

и рассматриваются параметризованные суммы но картам с к ребрами

в пределе к —> оо . Основной результат четвертой главы заключается в Теореме 4.2, согласно которой для любого фиксированного у £ [0,1/2] при к оо выполняется соотношение

Ш ~ /(у)*!24*Н.

В параграфе 4.2 проводится доказательство Теоремы 4.2. Основная идея доказательства состоит в том чтобы представить каждый из коэффициентов

в виде суммы по специального вида двоичным деревьям,

лы = £/сп.

При этом член суммы, соответствующий дереву Т, определяется как произведение но всем вершинам дерева в котором множитель в вершине V опрслсястся размером поддеревьев слева и справа от V.

Аккурагная оценка этих множителей позволяет ограничить член суммы соответствующий дереву с п вершинами величиной с~". с < 1/4. А поскольку количество двоичных деревьев с п вершинами не превосходит это дает сходимость суммы

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

Публикации по теме диссертации

1. Krikun M., Height of a Random Tree. Markov Processes and Related Fields, 2000 v.6, B2, 135-146.

2 Крикун М., Малышев B.A.. Асимптотическое число карт на компактных ориентируемых поверхностях Дискретная математика, 2001, т. 13, В2, 89-98.

Доказательство теоремы 2 (в части 3.1 статьи) и леммы 1, 3 принадлежат В.А. Малышеву; доказательства теоремы 2 (в частях 3.2, 3.3 статьи) и леммы 2, 4 принадлежат М.А Крикуну.

3 Krikun M., Malyshcv V.A., Random Boundary of a Planar Map. In "Trends in Mathematics. Mathematics and Computer Science II. Algorithms, Trees, Combinatorics and Probabilities", Ed. B. Chauvin, P. Flajolet, D. Gardy, A. Mokkadem. BirkHauscr, 2002.

Теоремы 1, 2, 3 в части существования пределов получены В.А. Малышевым; Теоремы 1, 2, 3 в части вычисления предельных распределений и лемма 4 получениы М. Крикуном.

4 Fayolle G., Lasgouttes J-M., Krikun M., Birth and death processes on certain random trees: classification and stationary laws. Probability Theory and Related Fields, Springer, 2003, DOI: 10.1007/s00440-003-0311-1

Теоремы 2.1, 4.1 и 4.2 и леммы 2.1, 4.1, 4.2 и 4.3 получениы М.А. Крикуном, теоремы 3.1, 3.2. 5.1 и леммы 2.2, 2.3, 2.4, 5.1 - Г. Файолем и Ж-М. Ласгуттом.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж ¡СО экз. Заказ № ^

»• 163 t

РНБ Русский фонд

2004-4 25354

Введение

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. Kallenberg (2001) Foundations of Modern Probability, Springer, Probability and its Applications.

2. W. Tutte. A Census of Planar Triangulations. Canad. J. Math., 1962, 14, 21-38.

3. W. Tutte. On the enumeration of convex polyhedra. J. Comb. The. Ser. В 28, 1980, 2, 105-126.

4. В. А. Малышев. Гиббсовские и квантовые дискретные пространства. Успехи мат. наук, 2001, т. 56, вып. 5, стр. 117.

5. М. Krikun, V. A. Malyshev. Random Boundary of a Planar Map в сборнике "Trends in Mathematics. Mathematics and Computer Science", Ed. D. Gardy, A. Mokkadem. BirkHauser, 2002

6. P- Flajolet, A.M. Odlyzko (1990) Singularity analysis of generating functions. SIAM Journal of Discrete Mathematics 3, 2, 216-240.

7. P. Flajolet, R. Sedgewick. The Average Case Analysis of Algorithms: Counting and Generating Functions. INRIA Research Report 1888, 1993

8. P. Flajolet, R. Sedgewick. The Average Case Analysis of Algorithms: Complex Asymptotics and Generating Functions. INRIA Research Report 2026, 1993

9. P. Flajolet, R. Sedgewick. The Average Case Analysis of Algorithms: Saddle point Asymptotics. INRIA Research Report 2376, 1994

10. P. Flajolet, R. Sedgewick. The Average Case Analysis of Algorithms: Mellin Transform Asymptotics. INRIA Research Report 2956, 1996

11. P. Flajolet, R. Sedgewick. The Average Case Analysis of Algorithms: Multivariate Asymptotics and Limit Distributions. INRIA Research Report 3162, 1997

12. P. Flajolet, R. Sedgewick. Analytic Combinatorc: Functional Equations, Rational and Algebraic Functions. INRIA Research Report 4103, 2001