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

Содержание к диссертации

Введение

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

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

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

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

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

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

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

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

2.4 Анализ особенностей 37

2.5 Триангуляция с одной границей 40

2.6 Триангуляция с двумя границами 45

2.7 Триангуляции без корня 50

3 Локальные свойства бесконечной случайной сферы 53

3.1 Определения 53

3.2 Модель 54

3.3 Скелет 59

3.4 Статистическая сумма 64

3.5 Предельные распределения 72

4 Асимптотическое число карт на компактных ориентируемых поверхностях 75

4.1 Определения 75

4.2 Доказательство 77

Список литературы 85

• Асимптотика высоты в транзиентном случае
• Рекуррентные соотношения
• Триангуляция с двумя границами
• Статистическая сумма

Введение к работе

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

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

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

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

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

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

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

^Pittel В., Note on the heights of random recursive tree) and random m -art/ search trees. Random Structures and Algorithms, 1994, 5,337-347.

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

РОС. НАЦИОНАЛЬНАЯ 1
БИБЛИОТЕКА І
C.4««p«wr fr {
, 08 W0y««Tbfe>j

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

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

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

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

⁶J.iggett Т.М.. Monotomnty of conditional distributions andarotvtk modeU on trert. Ann. РгоЬлЬ. 2000, 28. 1В4Г) 1663.

'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. Canad. J. Math., 1962,14, 21-38.; Tutte W., On the. enumeration of convex polyhedra. J. Comb. The., 1980, Sec. В 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, 1393, A63, 318-329.

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

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

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

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

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

"Ambjorn J, Quantization of geometry. Li Hurts at the 1994 L" Houches Summer School "Fluctuating Geometries tn Statistical Mechanics and Field Theory". 1994, arXiy hep th/9411179

"Поляков 4 M , Калибровочные поля и струны Удмуртский университет Ижевск, 1999

¹⁴J Ambjorn, Y. Watabiki, Scaling m quantum gravity Xucl Pkys 1995, В 445,1, 129-142.

¹⁵0. Angrl, О Schramm, Uniform Infinite Planar Tnangulalions 2002,arXiv math PR/0207153 , О -Vngel, Cwwfh and Percolation on the Uniform Random Infinite Planar Tnanqulalion 2002, .irXiv math PR/0208123

^UG Slhaeffer, Conjugation d'arbres el carles combmaloires alealotres PhD thesis, University Bordeaux I, Burdeaux, 1998; P. Chassamg, G. Schaeffer, Random Planar Lattices and Integrated Superbrowman Excursion 2002, arXiv math CO/0205226, to appear in Probability Theory and Related Fields.

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

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

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

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

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

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

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

^1TD.J. AJdoos, Tree-baaed models Jar landom distribution of mass. J. Statist. Thys., 1993, 73 (3-4). (І25-641.

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

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

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

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

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

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

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

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

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

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

Публикации.

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

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

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

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

В этой части мы исследуем поведение случайной величины H(t) в пределе по t в транзиентном случае. Основным результатом является следующая теорема. Теорема 1.2 Пусть А(1 - sp (s)) def s (1.14) 6(s, с) = - + log С вероятностью -юо где 5 - единственный положительный корень системы уравнений OS В эргодическом случае 6 = 0. Доказательство теоремы опирается на три нижеследующие леммы. Лемма 1.2 Рассмотрим события Ас = (liminf — с], Вс = (limsup— с). I t-ЇОО t і \ t-юо t J Тогда Р{ЛС} = {Ac} u P{AJ = &{вс} Иными словами, Лс и Вс удовлетворяют закону нуля-единицы и следовательно являются тривиальными событиями (т.е. имеют вероятность 0 или 1). Доказательство. Зафиксируем произвольно to и покажем, что Лс не зависит от Go = G(to). Для этого рассмотрим случайный процесс G {t) С G(t), определенный следующим образом: для каждого t дерево G (t) является поддеревом G(t), при t to G {t) содержит только корень, при t to оно содержит часть G, которая выросла из корня после момента to Другими словами, дерево G полностью "заморожено"до момента to Заметим, что G(t) и G (t + to), t 0- одинаково распределенные случайные процессы. Значит вероятность того, что Лс выполняется для G равна вероятности того что Ас выполняется для G (без условия на G(to)). С другой стороны, так как Hgit) HQi(t), По основному свойству условного математического ожидания и следовательно для всякого Go. Так как (1.15) выполняется и при условии на значения G для произвольной возрастающей последовательности моментов to,t\, Значит утверждение леммы в части Ас, является прямым следствием закона нуля-единицы для мартингалов (см. [4]). Аналогичное рассуждение можно провести для Вс. Если событие Вс выполняется для G при условии G(t) = Go, то оно выполняется и для G {t). Отсюда Лемма доказана.

Для всякого целого к и для всех t 0 определим случайные величины То есть Xk{t) обозначает количество вершин на уровне к в момент t. (і) Если, для некоторого целого п и действительного с О, (и) Если, для некоторого целого п и действительного с О, Доказательство. Пусть, для краткости, Jn(k) обозначает отрезок [кп/с, (к + 1)п/с]. (і) Рассмотрим ветвящийся процесс &, количество потомков строго больше единицы, ветвящийся процесс не вырожден с положительной вероятностью у(п,с). С другой стороны, процессу fc может быть сопоставлено поддерево G С G, такое что Нс(кп/с) кп. Тогда Р{ 4С} у(п, с) 0 тогда Р{ 4С} = 1 по лемме 1.2. Чтобы построить такое поддерево, с каждым поколением ветвящегося процесса ассоциируем множество sk вершин дерева G(kr), таким образом, ЧТО & = Sjfe. Пусть so = {VQ} И пусть для каждой вершины v Є Sk, к О Gv - поддерево с корнем в вершине v, состоящее из вершин, появившихся на отрезке Jn(k). Если вершина v удалена на интервале Jn(k), то Gv - пустое. Положим Эта конструкция дает искомое дерево, так как количество вершин в каждом из множеств под знаком объединения распределено как Yn(n/c) и так как каждое из множеств sk состоит из вершин расположенных на высоте не менее кп. (И) Пусть a,k = о[к) - неубывающая последовательность положительных целых чисел. Тогда Так как высота дерева не может уменьшаться быстрее, чем с интенсивностью (і, при условии {Н((к + 1)п/с) (к + 1)п} максимум H(t) на отрезке Jn{k) можно ограничить сверху как где 7г (/т/с) - случайная величина с распределением Пуассона. Следовательно,

Покажем, что правая часть (1.16) положительна. Во-первых, Во-вторых, возьмем последовательность в которой каждое целое положительное число j повторяется j раз. Тогда а& = 0(к1!2). Обозначим v = fin/c. Бесконечное произведение в (1.16) будет и значит ( следует из закона нуля-единицы для Вс. Доказательство леммы закончено. Лемма 1.4 Определим в области Щв) О функции (pk(s) и (fk{s) как преобразования Лапласа с начальным условием EXo(t) = 1. Действительно, первое соотношение следует из ранее использованного рассуждения: число вершин на уровне к равно числу вершин уровня к — 1 в каждом из к 0, в котором количество потомков равно Yn(n/c). Так как по условию леммы среднее количество потомков строго больше единицы, ветвящийся процесс не вырожден с положительной вероятностью у(п,с). С другой стороны, процессу fc может быть сопоставлено поддерево G С G, такое что Нс(кп/с) кп. Тогда Р{ 4С} у(п, с) 0 тогда Р{ 4С} = 1 по лемме 1.2. Чтобы построить такое поддерево, с каждым поколением ветвящегося процесса ассоциируем множество sk вершин дерева G(kr), таким образом, ЧТО & = Sjfe. Пусть so = {VQ} И пусть для каждой вершины v Є Sk, к О Gv - поддерево с корнем в вершине v, состоящее из вершин, появившихся на отрезке Jn(k). Если вершина v удалена на интервале Jn(k), то Gv - пустое. Положим Эта конструкция дает искомое дерево, так как количество вершин в каждом из множеств под знаком объединения распределено как Yn(n/c) и так как каждое из множеств sk состоит из вершин расположенных на высоте не менее кп. (И) Пусть a,k = о[к) - неубывающая последовательность положительных целых чисел. Тогда Так как высота дерева не может уменьшаться быстрее, чем с интенсивностью (і, при условии {Н((к + 1)п/с) (к + 1)п} максимум H(t) на отрезке Jn{k) можно ограничить сверху как где 7г (/т/с) - случайная величина с распределением Пуассона. Следовательно, Покажем, что правая часть (1.16) положительна. Во-первых, Во-вторых, возьмем последовательность в которой каждое целое положительное число j повторяется j раз. Тогда а& = 0(к1!2). Обозначим v = fin/c. Бесконечное произведение в (1.16) будет и значит ( следует из закона нуля-единицы для Вс. Доказательство леммы закончено. Лемма 1.4 Определим в области Щв) О функции (pk(s) и (fk{s) как преобразования Лапласа с начальным условием EXo(t) = 1. Действительно, первое соотношение следует из ранее использованного рассуждения: число вершин на уровне к равно числу вершин уровня к — 1 в каждом из поддеревьев с корнем на уровне 1, не «

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

Чтобы получить рекуррентные соотношения для C(N, т, к; а) мы развиваем метод удаления корня, первоначально примененный Таттом в [13]. Рекурсия основывается на отображении 8 которое каждой триангуляции, содержащей хотя бы один треугольник, ставит в соответствие одну или две триангуляции таким образом, что суммарное число треугольников уменьшается на единицу. Обозначим вершины триангуляции T(N,k,m;a), лежащие на внешней границе символами bo, 61,..., 6m-i в порядке обхода границы, так что bo, b\ - начало и конец корневого ребра. Это обозначение будет использоваться далее в качестве стандартного. Если N 0, то в Т есть единственный треугольник с вершинами bo,bi. Пусть и - третья вершина этого треугольника. Мы удалим ребро Ьо і и сделаем корневым ребро Ьои, которое теперь принадлежит внешней границе. При этом полученная корневая плоская карта Т", вообще говоря, может не быть ни допустимой триангуляцией, ни просто триангуляцией в смысле определения 2.2, так как может содержать точку сочленения первого или второго рода. В зависимости от положения вершины и в Т возможны три случая, в каждом из которых результат применения 5 определяется отдельно. и является внутренней вершиной Т. Тогда Т будет допустимой триангуляцией типа (iV — 1, га +1, к] а) (легко проверить что Т не содержит точек сочленения первого или второго рода), и 8{Т) = Т . и принадлежит внешней границе, то есть совпадает с одной из вершин &2)--ч bm-i, скажем, и = Ь/. В этом случае и - точка сочленения первого рода в Т , и можно разрезать Т" на две части Ті и Тг, так что Ті содержит 6о а Тг содержит Ь\ (отметим, что пара Ті, Ті является упорядоченной). Новыми корневыми ребрами в этом случае будут Ь$и и ub\ а триангуляции будут иметь тип Ti(N\,гаї, к\\ аы) и T2(N2,гаг, fo; a/fc\w), где Ni + N2 = N — 1, гаї 4- mi = га + 1, ki + / = к, си - подмножество (возможно пустое) множества индексов Ik = {1,..., к}, а аи - вектор, содержащий компоненты вектора а индексы которых перечислены в ш в порядке возрастания (т.е. если ш = {1,3,5}, то аи = {«і, «з» s}) и принадлежит внутренней границе, скажем j.

Тогда и - точка сочленения второго рода в Т , и можно разрезать Т в точке и так что получится триангуляция Т" типа T"(N — l,m+aj- + l, А; —1; oeih\{j})- Новым корнем будет Ь0и. Теперь можно формально определить отображение 8. Оно состоит из трех частей. Причина, по которой результат отображения 82 нельзя определить просто как упорядоченную пару триангуляции состоит в том, что этого недостаточно чтобы восстановить отношение порядка на оригинальной триангуляции. То же относится к #з Следующая лемма показывает что отображение 8 сохраняет всю необходимую информацию для восстановления оригинальной триангуляции. Доказательство. Мы покажем существование обратного отображения р, задав в явном виде три его части / = Sf1, і = 1,2,3, а заодно определим образы Si. Результатом 5\ может быть любая триангуляция T(N, m,k ,a) cm 3. Для такой триангуляции добавим ребро 6062 и сделаем его корнем. Получим допустимую триангуляцию р\{Т) = T (N + 1, тп — 1, к; а). Результатом 82 будет тройка, состоящая из триангуляции Ti(iVi,mi;a;), T2(N2, ГП2; ), имеющих j и к — j границ соответственно, и подмножества и С Ik состоящего из j элементов. Возьмем любую такую тройку. Чтобы восстановить оригинальную триангуляцию, склеим конец корня Ті с началом корня Тг и добавим новый корень, начало которого совпадает с началом корня Ті а конец с концом корня Тг. Очевидно что в полученной триангуляции нет точек сочленения, и значит она является допустимой. Остается смешать правильным образом порядок границ в Ті и Тг. Дадим границам из Ті номера перечисленные в ш, так чтобы сохранить изначальный порядок, а границам из Тг дадим номера перечисленные в 1к\ш (например, если а = {ОІ\,ОІ2, аз}, (3 = {ft,/} и ш = {1,4,5} то получится порядок: {ai, /Зі, fa, «2, a3}). Отображение 5з дает тройки вида T(N, m + m! + 1, к; a), j, mr, где N 0,m 2, m 2,1 j к + 1. Однако не все такие тройки могут быть результатом применения (. Чтобы обратить отображение () нужно склеить вершины &i, 6m +i и добавить новый корень &о»&т +2- Результат будет допустимой триангуляцией, если только между склеиваемыми вершинами не было секущего ребра. В противном случае возникнет точка сочленения первого рода (см. рис. 2.2). Лемма доказана. Перейдем к рекуррентным соотношениям. Пусть D(N,m,m ;a) обозначает подкласс C(N,m + m \a), состоящий из триангуляции содержащих секущее ребро между вершинами &i,&m +i внешней границы, либо, в зависимости от контекста, количество триангуляции в этом классе. Пусть также D (N, т,т , а) - аналогичное обозначение для подкласса C (N, т + т \ а). Тогда, как следствие леммы 2.2, получаем: Лемма 2.3 Для N 2, к 0, т 2 и а такого что аг- 2, г = 1,..., к, выполняется соотношение Здесь [/tk] обозначает линейный оператор сдвига степенного ряда влево, т.е. если F(t) = J2jcj&i т0 [A ]- W = 2jcj+kV- Запись [/y2w] эквивалентна УУЧН Функции Dk(x,y,w,z) можно выразить через Uj, j к. Мы приведем это выражение в явном виде для к = 0; общая формула может быть получена аналогичным образом без каких-либо сложностей. Лемма 2.4 Производящие функции Dk(x,y,w,z) могут быть выражены через Uo,..., Uk. В частности, Доказательство. Рассмотрим случай k = 0. Обозначим R (N,m;a) подкласс C {N, т; а) состоящий из триангуляции не содержащих секущего ребра между bo и &i (т.е. секущего ребра параллельного корню).

Триангуляция с двумя границами

Здесь мы следуем методу примененному в [16): вычислить асимптотику фак-ториальных моментов границ, затем выбрать скейлинг, получить (обычные) моменты масштабированной случайной величины и попытаться определить некоторые свойства ее распределения. Вычислив явно несколько производных Ui(x, у, z) по у, z в точке у = Z = А и разложив их по полуцелым степеням t= (XQ — X), получим что по крайней мере для к, I = 0,1,2,3. Предположим что (2.40) выполняется для всех к, L Чтобы проверить это, построим следующее разложение коэффициентами, а точнее Таким образом ащ = [liV]A(u, V) ф 0 и (2.40) выполняется для всех &, Z. Факториальные моменты га, т определяются соотношением Из (2.43) ясно что границы имеют порядок N1!2. Переписав (2.43) для масштабированных случайных величин (771 2) = {N ll2m1N l 2m ), получим утверждение Теоремы 2.5. 2.6.3 Суперкритическая область В суперкритической области границы сильно зависимы. Мы начнем с распределения их суммы, затем найдем маргинальные распределения. Оказывается что этого достаточно чтобы получить полную картину. Вычислим первые и вторые производные U\ (х, у, z) по у, z и совместные моменты т,т . Получим что Em, Era имеют порядок N и что (эти соотношения следует понимать как эквивалентность с точностью до членов порядка меньше N). Из (2.44) видно, что вариация суммы S = га + га имеет порядок 0{1) при N — со. Характеристическая функция суммы S = т + т для фиксированного N есть (для удобства ограничимся действительными значениями аргумента). Нас интересуют семиинварианты S, Очевидно, Разложим Ui(x,y,y) в ряд вблизи точки xi(y), (функция f(y) не приводится в явном виде, так как это не играет роли в дальнейшем). Отсюда Следовательно все семиинварианты S имеют порядок N, и все семиинварианты случайной величины = N 2(S — Е S) кроме первого стремятся к нулю, то есть сходится к нормальному распределению.

Предел математического ожидания S/N и дисперсия нормального распределения здесь в точности те же, что и в случае одной границы, (см. теорему 2.3) Чтобы получить маргинальное распределение га мы будем действовать тем же способом, что и в критической точке. Моменты т определяются производными Ui(x, у, Л) по у. Асимптотику моментов мы получаем из разложения где сі, С2 зависят от параметра Л. Явный вид этой зависимости не важен, так как основное свойство Ф которое нас интересует состоит в том, что и следовательно моменты т равны (с точностью до членов меньшего порядка Заметим, что моменты случайной величины распределенной на [0,1] и имеющей плотность Многокорневые триангуляции диска с несколькими границами являются в определенном смысле более естественным объектом чем триангуляции с единственным корнем, так как они не делают различий между границами. Еще более естественно было бы рассматривать триангуляции без корня, однако нет метода их непосредственного перечисления, и кроме того возникает вопрос о наличии нетривиальной группы автоморфизмов. Пренебрегая этим вопросом (который не является существенным в пределе N —» со), будем считать что число триангуляции без корня с границами га, ai,... ,ak равно (гааі ak ClN, га; а). Тогда оказывается, что результаты полученные для многокорневых триангуляциям легко переносятся на триангуляции без корня. Лемма 2.7 Пусть C(N,m) - неотрицательные числа, такие что для любого N лишь конечное их число отлично от нуля, и пусть случайные вели-чины Хм и XN имеют распределения Из (2.52) видно, что если N qX сходится, то и N qX сходится, так как моменты XN И XN - одного порядка. То же свойство выполняется и для двумерных случайных величин. Если мы применим этот факт и уравнения (2.52), (2.53) к предельным распределениям полученным в параграфах 2.5, 2.6, получим их вариант для не-корневых триангуляции. В субкритической области существует предельное распределение т, и совместное предельное распределение га, га . Теорема 2.4 выполняется в точности, производящие функции распределений получаются из (2.30) и (2.39) заменой Ф(у) на Для двух границ В суперкритической области при переходе к триангуляциям без корня в случае одной границы поведение сохраняется в точности. В случае двух границ придется сделать дополнительные выкладки. Из (2.50) получим совместные моменты 7], rf

Статистическая сумма

Уравнение (3.11) можно переписать в операторной форме, где А - линейный оператор, зависящий от параметра х. Обозначим Ао = А(#о) и сформулируем некоторые следствия теорем 3.3 и 3.1. является производящей функцией распределения длины верхней границы первого слоя в бесконечной случайной сфере с длиной корневой границы I. Следствие 2. Обозначим к, I, п соответственно длину верхней границы, длину нижней границы и число треугольников в триангуляции В Є BR. Тогда Следствие 3. Возьмем случайный слой В Є В\ с фиксированной длиной нижней границы /. Тогда среднее число треугольников в В при больших I растет как Следствие 4. Возьмем случайный слой В Є В\ с фиксированной длиной нижней границы I и случайной верхней границей к. Тогда среднее приращение (к — I) при / - оо растет как I1/2. Два последних утверждения позволяют предположить, что при больших R длина верхней границы В Є BR растет как R2, а число треугольников -как І24. Доказательство следствия 1. Равенство (3.14) проверяется с помощью прямого вычисления. Равенство (3.15) непосредственно вытекает из Теоремы 3.1 и определения суммы (3.11): Функция f{z) действительно является производящей функцией вероятностного распределения, так как при z = 1 имеем Фг = Ф, АдФ = Ф и следовательно /(1) = 1. Доказательство следствия 2. Равенство (3.16) докажем индукцией по R. При R = 1 это утверждение теоремы 3.2. Пусть (3.16) верно для R. BeBj где к,1,пи к , I , п - верхняя и нижняя границы и количество треугольников в L и В соответственно, Вл(к) включает только триангуляции с корневой границей длины к. Доказательство следствий 3 и 4. Поясним значение средней части равенств (3.17) и (3.18) в качестве суммы по слоям: следовательно (3.17) действительно описвыает среднее число треугольников в слое с нижней границей /. Аналогично (3.18) описывает приращение длины границы при переходе от слоя к слою Чтобы получить асимптотику I3/2 И (Ч\ нужно в явном виде разложить в ряд по у вблизи особой точки 2/ = 2/0 функции стоящие в фигурных скобках в (3.17), (3.18), и сравнить скорость роста их длину верхней границы, длину нижней границы и число треугольников в триангуляции В Є BR. Тогда Следствие 3. Возьмем случайный слой В Є В\ с фиксированной длиной нижней границы /. Тогда среднее число треугольников в В при больших I растет как Следствие 4. Возьмем случайный слой В Є В\ с фиксированной длиной нижней границы I и случайной верхней границей к. Тогда среднее приращение (к — I) при / - оо растет как I1/2. Два последних утверждения позволяют предположить, что при больших R длина верхней границы В Є BR растет как R2, а число треугольников -как І24. Доказательство следствия 1. Равенство (3.14) проверяется с помощью прямого вычисления. Равенство (3.15) непосредственно вытекает из

Теоремы 3.1 и определения суммы (3.11): Функция f{z) действительно является производящей функцией вероятностного распределения, так как при z = 1 имеем Фг = Ф, АдФ = Ф и следовательно /(1) = 1. Доказательство следствия 2. Равенство (3.16) докажем индукцией по R. При R = 1 это утверждение теоремы 3.2. Пусть (3.16) верно для R. BeBj где к,1,пи к , I , п - верхняя и нижняя границы и количество треугольников в L и В соответственно, Вл(к) включает только триангуляции с корневой границей длины к. Доказательство следствий 3 и 4. Поясним значение средней части равенств (3.17) и (3.18) в качестве суммы по слоям: следовательно (3.17) действительно описвыает среднее число треугольников в слое с нижней границей /. Аналогично (3.18) описывает приращение длины границы при переходе от слоя к слою Чтобы получить асимптотику I3/2 И (Ч\ нужно в явном виде разложить в ряд по у вблизи особой точки 2/ = 2/0 функции стоящие в фигурных скобках в (3.17), (3.18), и сравнить скорость роста их коэффициентов со скоростью роста а(1), применив теорему 2.7. Перейдем теперь к исследованию, итераций оператора А (ж) в случае х = XQ. Положим Ао = А(гсо) и сделаем замену переменной Доказательство. Выражение (3.21) можно получить из (3.11) прямым вычислением, то есть подставить х = хо, h = ho в (3.11), сделать замену переменной и упростить полученное выражение. Эту выкладку мы опускаем. Чтобы вычисликоэффициентов со скоростью роста а(1), применив теорему 2.7. Перейдем теперь к исследованию, итераций оператора А (ж) в случае х = XQ. Положим Ао = А(гсо) и сделаем замену переменной Доказательство. Выражение (3.21) можно получить из (3.11) прямым вычислением, то есть подставить х = хо, h = ho в (3.11), сделать замену переменной и упростить полученное выражение. Эту выкладку мы опускаем. Чтобы вычислить произвольную k-ю итерацию оператора В, введем "производящий оператор