Изучаются числа расширений в плотном биномиальном случайном графе, а имен-
но нахождение асимптотического распределения максимального числа расширений.
Под расширением заданного множества вершин (корней) V (небольшого размера)
подразумевается непересекающееся с этим множеством множество U , ребра в кото-
ром (а также между U и V ) должны быть проведены в соответствии с некоторым
шаблоном. Так, например, степень вершины – это количество расширений, для кото-
рых шаблоном является ребро, одна из вершин которого является корнем. Другими
примерами количеств расширений являются число треугольников, содержащих за-
данную вершину, количество общих соседей заданного набора вершин, количество
путей заданной длины между двумя фиксированными вершинами, и так далее. Ряд
работ (восходящих к Боллобашу и Спенсеру) посвящены изучению распределения максимального числа расширений (по всем способам выбрать корни).