no. 17 · Wednesday 18 November 2026
Asymptotic enumeration of histories and limit laws in two random graph evolution models
Abstract
We study growth models for random graphs where the growth is established by vertex or edge creations and where there is no dependence between vertices and edges. Creations are logged by time stamps such that the history of the resulting graph can be reconstructed. We investigate two prototypical models, an undirected and a directed one, called undirected independent growth model (UIG-model) and directed independent growth model (DIG-model). The generating functions for the number of histories have radius of convergence equal to zero. In the UIG-model, we express the asymptotic number of histories as a sum that is amenable to the discrete Laplace method. We derive the asymptotic number of histories, study the number of vertices of a random history, and prove a central limit theorem. In the DIG-model we use a rescaled Borel transform to get an entire function. Then we show that this function is Hayman admissible, which enables us to derive the asymptotic number of histories in this model. The counting sequence is closely related to the framework of generalized Legendre-Stirling numbers. To determine the number of vertices in a random history, we prove that the bivariate generating function is e-admissible and infer that again a normal limit law holds. Finally, we discuss a correspondence to set partitions with even block sizes and present an algorithm based on Boltzmann samplers that generates such graphs uniformly at random.
- comments
- 37 pages, 1 figure
- fields
- Combinatorics, Probability