Форма случайных деревьев

В докладе будет сделан обзор последних результатов о форме случайных деревьев. Форма случайного дерева определяется его профилем, т.е. последовательностью $v_k=\#\{x:\mathrm{dist}(x,root)=k\}$ $(k\ge 0)$ чисел вершин, находящихся на расстоянии $k$ от корня. По профилю можно найти ряд других параметров дерева: высоту $h=\max\{k\ge0:v_k>0\}$, ширину $w=\max\{v_k:k\ge 0\}$ и длину путей (= сумму всех расстояний до корня $l=\sum_{k\ge 0} k v_k$.
Будут рассмотрены деревья Гальтона–Ватсона (включающие несколько классических семейств деревьев, в частности двоичные деревья, деревья Мотцкина, корневые плоские деревья, помеченные деревья), деревья Пойа (в которых среднее расстояние до корня имеет порядок $\sqrt{n}$), а также так называемые $(\log n)$-деревья (бинарные деревья поиска, рекурсивные деревья, плоские ориентированные деревья, цифровые деревья поиска), в которых среднее расстояние до корня имеет порядок $\log n$.
Оказывается, профиль $\sqrt{n}$-деревьев можно аппроксимировать случайным процессом — локальным временем броуновской экскурсии, что позволяет получить предельные распределения высоты и ширины. В случае $\log n$-деревьев ситуация совершенно другая. Они больши похожи на «детерминистические». Для них тоже существуют аппроксимации процессами, но эти процессы не являются функционалами от броуновского движения.
Одной из целей доклада является демонстрация силы аналитических методов в специфическом разделе теории векроятностей, связанном с комбинаторными задачами. В основном используются метод производящих функций и их свойства как аналитических функций.