betaFeedback

WorksMathematics

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.

Introduction

Dynamic graph models have emerged as useful tools for modeling systems whose interaction structure changes over time. Examples include social networks, where the times at which interactions occur form an essential part of the data [7], and stochastic graph-rewriting models for biochemical systems [6]. More broadly, random graph theory contains a wide variety of static and evolving models. It started with the classical Erdős–Rényi random graph process [21], which has been extensively studied and is nowadays well-covered by [9, 27] and ranges to more recent models for social networks like the preferential attachment model surveyed by Albert and Barabási [1].

In the classical dynamic models there is typically no or no strict separation between the growth in the number of vertices and the growth in the number of edges, see [14] [1]. For instance, in the Erdős–Rényi models the number of vertices, say nn, is fixed and the number of edges grows. Then one lets nn tend to infinity and studies asymptotic properties, where a dependence on nn for the number of edges is usually imposed on the model. In [23] a new random graph growth model is suggested where the size as well as the order of a graph may grow according to the inherent structure of the graph process itself. Classical accounts on dynamic random graphs focus on the study of several popular models such as the copying model, the small-world graph, and the preferential attachment model as well as variations in [10], power law graphs and duplication models (static and dynamic) in [12] and the treatment largely based branching processes in [20].

In this paper, we study a process on multi-graphs which may grow independently with respect to order as well as size and where the vertices and the edges receive a time stamp. The evolution is accomplished through one of two operations at each discrete time step: the creation of a new vertex or the addition of an edge between two existing vertices. There are several ways to do that and in this work we consider two particular models: the undirected independent growth model (UIG-model) with undirected edges and where no loops are allowed, and the directed independent growth model (DIG-model) with directed edges and where loops are allowed.

For both models, the counting sequence is related to the Legendre–Stirling numbers introduced in [22]. The counting sequence for the UIG-model is, up to a one-step shift, OEIS A124373, while the DIG-model gives the sequence of generalized Bell numbers, OEIS A135920. These sequences belong to a broader algebraic framework of polynomial base changes that traces back to Carlitz [11] and arises naturally in spectral analysis [22]. It was later systematically extended to the Legendre–Stirling framework by Andrews and Littlejohn [2, 3], who also gave a combinatorial interpretation in terms of certain set partitions over sets of integers present in two colors. Across these families, the counting sequences satisfy analogous recurrence relations, and the functional equations for their generating functions differ only by a single parameter. Furthermore, they all admit natural graph-theoretic interpretations as special instances of the diagram families studied in [8].

Our contributions are twofold. First, we derive explicit formulas and asymptotic expressions for the number of random graphs obtainable in nn steps. We regard these graphs as combinatorial structures in the sense of analytic combinatorics and use the machinery developed in [24] to derive differential equations for the generating functions associated with these graphs, which are then analyzed asymptotically. The generating functions we encounter have a radius of convergence equal to zero. In the UIG-model, we express the coefficients as sums involving Bessel functions. The terms of the sum are Gaussian and therefore the asymptotic analysis can be based on the discrete Laplace method (see [24 p. 761–762]). For the DIG-model, we transform the generating function with a rescaled Borel transform [5] (see also [16] for a general introduction to Borel transforms), making it entire after all. For the transformed function we obtain an explicit closed form. We show that it is Hayman admissible [26] in one variable.

Second, we analyze the distribution of the number of vertices that are created after nn steps in both models. In the UIG-model, a perturbed discrete Laplace method applies and so we show a central limit theorem. The Borel transform of the bivariate function of the DIG-model is shown to be e-admissible [18], which yields a normal limit law. We note that in the extended abstract of this work [4], a custom modification of bivariate Hayman admissibility [25] was developed to prove the limit theorem. Bivariate Hayman admissibility is an inherently stronger concept, as it establishes a full bivariate normal distribution. However, since our generating function narrowly misses its conditions, we opt for e-admissibility in this work, which presents a cleaner and more direct approach to derive the result without the need for a conceptual extension.

The paper is organized as follows. Section 2 presents the UIG-model and is devoted to the asymptotic number of graphs that can be generated in nn growth steps. Section 3 is devoted to the central limit theorem for the distribution of the number of vertices in that model. Out of a desire to tune the growth rate of the number of vertices relative to that for the number of edges, we briefly discuss a weighted version of this the UIG-model in Section 4. The DIG-model is introduced in Section 5, where we derive the asymptotic number of graphs that can be generated in nn steps. The central limit theorem for the number of vertices is shown in Section 6. An interesting correspondence to set partitions into even-sized subsets is presented in Section 7. This correspondence can be used to design a uniform sampling algorithm based on Boltzmann samplers [19], which we present in Section 8.

Notations and facts. Throughout the paper we write ∂x\partial_x for denoting the partial derivative with respect to xx. For sequences (an)n∈N(a_n)_{n\in\mathbb{N}} and (bn)n∈N(b_n)_{n\in\mathbb{N}} we write an≍bna_n \asymp b_n synonymous to an=Θ(bn)a_n = \Theta(b_n).

We denote by jν,1j_{\nu,1} the smallest positive zero of the Bessel function JνJ_\nu. It is well-known that for ν>−1\nu> -1 the Bessel function Jν(z)J_\nu(z) is positive on the interval (0,jν,1)(0,j_{\nu,1}). Moreover, ν↦jν,1\nu\mapsto j_{\nu,1} is increasing, jν,1>νj_{\nu,1} > \nu, and j1,1=3.8317…j_{1,1} = 3.8317\ldots, see [17 §10.21].

The UIG-model: undirected graphs without loops

We start out by describing the first graph evolution model we want to analyze. At each discrete time step we create a vertex or an edge and each created item gets a time stamp. Precisely, either (i) a new vertex is created, or (ii) a new undirected edge is added between two distinct existing vertices. The two vertices may already be adjacent. So, loops are forbidden while multiple edges are allowed. We investigate the bivariate generating function that corresponding to all histories generated by this process and keeping track of the number of steps and the number of vertices.

Definition 1. A history in the UIG-model is a multigraph obtained by the construction described above, using steps (i) and (ii), such that each vertex and each edge receives a time stamp.

Thus, a history records not only the resulting multigraph but also the order in which its vertices and edges were created. In particular, two histories may have the same underlying multigraph while differing in their time labels.

Note that the time stamps are not labels in the classical sense of analytic combinatorics, as there are restrictions on where to put them. For instance, two vertices are needed to create edges. So, no edge can have time stamp one or two. So, technically, the class of histories is an unlabelled combinatorial class in the sense of [24], which means that we have to set up ordinary generating functions. To this end, let the variable tt mark time (number of steps) and uu mark the number of vertices, i.e., write

T(t,u)=∑n≥0∑m≥0Tn,mtnumT(t,u) = \sum_{n\geq0}\sum_{m\geq0} T_{n,m}t^n u^m

where the coefficient Tn,m=[tnum]T(t,u)T_{n,m} = [t^n u^m]T(t,u) is the number of histories that can be generated in nn steps and have mm vertices (and hence n−mn-m edges). A step creating a vertex corresponds to a factor utut in the generating function, as we add a vertex and a step. When creating an edge, we must add a step and then choose two distinct vertices. This amounts to two pointing-and-removing operations and then reverting the removals. Moreover, as the edge is undirected, the order of the vertices must not be taken into account. After all, this yields the following differential equation for the generating function T(t,u)T(t,u):

T(t,u)=1+utT(t,u)+u2t2∂u2T(t,u).T(t,u)=1+utT(t,u)+\frac{u^2t}{2}\partial_u^2T(t,u).

Equivalently, as a formal power series in tt,

T(t,u)=∑m≥0∏k=1mtu1−(k2)t.(1)T(t,u)=\sum_{m\geq0}\prod_{k=1}^{m}\frac{tu}{1-\binom{k}{2}t}. \tag*{(1)}

This can be seen, as each vertex creation yields a factor tutu and after having created kk vertices so far, there are (k2)\binom{k}{2} possibilities for each edge that is created before the creation of the (k+1)(k+1)-th vertex.

We are primarily interested in asymptotics of [tn]T(t,1)[t^n]T(t,1), as n→∞n\to\infty. The first few terms can be seen from the expansion

T(t,1)=1+t+t2+2t3+6t4+25t5+135t6+909t7+O(t8).T(t,1)=1+t+t^2+2t^3+6t^4+25t^5+135t^6+909t^7+O\left(t^8\right).

Remark 1. The mm-th summand in (1) has poles at t=2/(k(k−1))t=2/(k(k-1)) for k=2,…,mk=2,\ldots,m. Thus, the poles of T(t,1)T(t,1) accumulate at t=0t=0 and hence the radius of convergence of the series T(t,1)T(t,1) is zero unless there are some miraculous cancellations. (Note that for any z>0z>0 the sum has positive and negative terms!) But a simple lower bound shows that this is indeed the case: Take 1≤k≤n1\leq k\leq n and consider the histories that first create kk vertices and then n−kn-k edges. They are easy to count and yield [tn]T(t,1)≥(k2)n−k[t^n]T(t,1)\geq\binom{k}{2}^{n-k}. Choosing k=⌊n⌋k=\lfloor\sqrt{n}\rfloor gives ([tn]T(t,1))1/n→∞([t^n]T(t,1))^{1/n}\to\infty. To circumvent this problem, the asymptotic analysis is performed at the coefficient level rather than by classical singularity analysis at a dominant singularity.

Proposition 1. For n≥1n\geq1, the coefficients of T(t,u)T(t,u) are given by

[tn]T(t,u)=∑r=1nur∑k=1r(k2)n−1(−1)k−r2r−1(2k−1)(k+r−1)!(r−k)!.(2)[t^n]T(t,u)=\sum_{r=1}^{n}u^r\sum_{k=1}^{r}\frac{\binom{k}{2}^{n-1}(-1)^{k-r}2^{r-1}(2k-1)}{(k+r-1)!(r-k)!}. \tag*{(2)}

with the convention 00=10^0=1. In particular, for u=1u=1, there is a constant c>0c>0 such that

[tn]T(t,1)=∑k=12n(k2)n−12k−12J2k−1(22)+O(e−cnlog⁡n).(3)[t^n]T(t,1)=\sum_{k=1}^{2n}\binom{k}{2}^{n-1}\frac{2k-1}{\sqrt{2}}J_{2k-1}(2\sqrt{2})+O\left(e^{-cn\log n}\right). \tag*{(3)}

where Jα(z)J_\alpha(z) denotes the Bessel function of the first kind.

Proof. We decompose the product into partial fractions. One obtains

T(t,u)=1+∑r=0∞ur∑k=1rt1−(k2)t∏s=1k−11(k2)−(s2)∏s=k+1r1(k2)−(s2).T(t,u)=1+\sum_{r=0}^{\infty}u^r\sum_{k=1}^{r}\frac{t}{1-\binom{k}{2}t}\prod_{s=1}^{k-1}\frac{1}{\binom{k}{2}-\binom{s}{2}}\prod_{s=k+1}^{r}\frac{1}{\binom{k}{2}-\binom{s}{2}}.

Using the Gamma function, this can be rewritten as

T(t,u)=1+∑r=0∞ur∑k=1rt(−1)k−r2r−1(2k−1)(1−(k2)t)Γ(k+r)Γ(r+1−k).T(t,u)=1+\sum_{r=0}^{\infty}u^r\sum_{k=1}^{r}\frac{t(-1)^{k-r}2^{r-1}(2k-1)}{\left(1-\binom{k}{2}t\right)\Gamma(k+r)\Gamma(r+1-k)}.

Observe that the rr-th summand in the original product (1) is of order O(tr)O(t^r). Therefore, any term with r>nr>n does not contribute to the coefficient of tnt^n. Extracting the coefficient of tnt^n from the terms 1≤r≤n1\le r\le n yields (2). Setting u=1u=1 and rewriting the resulting expression in terms of Bessel functions gives

[tn]T(t,1)=∑k>1(k2)n−12k−12J2k−1(22).[t^n]T(t,1)=\sum_{k>1}\binom{k}{2}^{n-1}\frac{2k-1}{\sqrt{2}}J_{2k-1}(2\sqrt{2}).

It remains to show that this sum may be truncated at k=2nk=2n with a superexponentially small error. For fixed zz and ν→∞\nu\to\infty, we use the standard large-order estimate

Jν(z)=1Γ(ν+1)(z2)ν(1+O(ν−1)).J_\nu(z)=\frac{1}{\Gamma(\nu+1)}\left(\frac{z}{2}\right)^\nu\left(1+O(\nu^{-1})\right).

With z=22z=2\sqrt{2} and ν=2k−1\nu=2k-1, Stirling’s formula gives

J2k−1(22)=14πkexp⁡(−2klog⁡k+O(k)).J_{2k-1}(2\sqrt{2})=\frac{1}{\sqrt{4\pi k}}\exp(-2k\log k+O(k)).

On the other hand,

References

  1. [7]Tanya Y. Berger-Wolf and Jared Saia. A framework for analysis of dynamic social networks. In Proceedings of the 12th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining (KDD ’06). ACM, 2006, pp. 523–528. DOI: 10.1145/1 150402.1150462.
  2. [8]Pawel Blasiak and Philippe Flajolet. Combinatorial models of creation-annihilation. Sém. Lothar. Combin. 65 (2010), Art. B65c, 78. ISSN: 1286-4889.arxiv.org/abs/1010.0354
  3. [9]Béla Bollobás. Random Graphs. Second. Vol. 73. Cambridge Studies in Advanced Mathematics. Paperback ISBN: 0-521-79722-5. Cambridge University Press, Cambridge, 2001, pp. xviii+498. ISBN: 0-521-80920-7. DOI: 10.1017/CBO9780511814068. URL: https://doi.org/10.1017/CBO9780511814068.
  4. [10]Anthony Bonato. A Course on the Web Graph. Vol. 89. Graduate Studies in Mathematics. American Mathematical Society, Providence, RI; Atlantic Association for Research in the Mathematical Sciences (AARMS), Halifax, NS, 2008, pp. xii+184. ISBN: 978-0-8218-4467-0. DOI: 10.1090/gsm/089. URL: https://doi.org/10.1090/gsm/089.
  5. [11]L Carlitz and John Riordan. The divided central differences of zero. Canadian Journal of Mathematics 15 (1963), 94–100.DOI
  6. [12]Fan Chung and Linyuan Lu. Complex Graphs and Networks. Vol. 107. CBMS Regional Conference Series in Mathematics. Published for the Conference Board of the Mathematical Sciences, Washington, DC; by the American Mathematical Society, Providence, RI, 2006, pp. viii+264. ISBN: 978-0-8218-3657-6. DOI: 10.1090/cbms/107. URL: https://doi.org/10.1090/cbms/107.
  7. [13]Louis Comtet. Advanced Combinatorics: The Art of Finite and Infinite Expansions. Trans. by J. W. Nienhuys. Reprint of the original 1974 edition. Dordrecht: Springer Science & Business Media, 2012. DOI: 10.1007/978-94-010-2196-8.
  8. [14]Colin Cooper and Alan Frieze. A general model of web graphs. Random Structures Algorithms 22.3 (2003), 311–335. ISSN: 1042-9832,1098-2418. DOI: 10.1002/rsa.10084. URL: https://doi.org/10.1002/rsa.10084.
  9. [15]Robert M. Corless et al. On the Lambert W function. Advances in Computational Mathematics 5.4 (1996), 329–359. DOI: 10.1007/BF02124750.
  10. [16]Ovidiu Costin. Asymptotics and Borel Summability. Monographs and Surveys in Pure and Applied Mathematics. CRC Press / Taylor & Francis, 2008. ISBN: 978-1420070316.DOI
  11. [17]NIST Digital Library of Mathematical Functions. https://dlmf.nist.gov/, Release 1.2.8 of 2026-09-15. F. W. J. Olver, A. B. Olde Daalhuis, D. W. Lozier, B. I. Schneider, R. F. Boisvert, C. W. Clark, B. R. Miller, B. V. Saunders, H. S. Cohl, and M. A. McClain, eds. URL: https://dlmf.nist.gov/.
  12. [18]Michael Drmota, Bernhard Gittenberger, and Thomas Klausner. Extended admissible functions and Gaussian limiting distributions. Mathematics of Computation 74.252 (2005), 1953–1966. DOI: 10.1090/S0025-5718-05-01744-8. URL: https://doi.org/10.1090/S0025-5718-05-01744-8.
  13. [19]Philippe Duchon et al. Boltzmann samplers for the random generation of combinatorial structures. Comb. Probab. Comput. 13.4-5 (2004), 577–625.DOI
  14. [20]Rick Durrett. Random Graph Dynamics. Vol. 20. Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, Cambridge, 2007, pp. x+212. ISBN: 978-0-521-86656-9.DOI
  15. [21]Paul Erdős and Alfréd Rényi. On the evolution of random graphs. Publication of the Mathematical Institute of the Hungarian Academy of Sciences 5 (1960), 17–61.
  16. [22]WN Everitt, LL Littlejohn, and R Wellman. Legendre polynomials, Legendre–Stirling numbers, and the left-definite spectral analysis of the Legendre differential expression. Journal of Computational and Applied Mathematics 148.1 (2002), 213–238.DOI
  17. [23]Michael Farber, Alexander Gnedin, and Wajid Mannan. A random graph growth model. Bulletin of the London Mathematical Society 56.2 (2024), 662–680. DOI: 10.1112/blms.12957.DOI
  18. [24]Philippe Flajolet and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009.
  19. [25]Bernhard Gittenberger and Johannes Mandlburger. Hayman admissible functions in several variables. The Electronic Journal of Combinatorics 13.1 (2006), R106. DOI: 10.37236/1132.DOI
  20. [26]W. K. Hayman. A generalisation of Stirling’s formula. Journal für die reine und angewandte Mathematik 196 (1956), 67–95. DOI: 10.1515/crll.1956.196.67. URL: https://www.degruyterbrill.com/document/doi/10.1515/crll.1956.196.67/html.DOI
  21. [27]Svante Janson, Tomasz Łuczak, and Andrzej Rucinski. Random graphs. Wiley Interscience Series in Discrete Mathematics and Optimization. Wiley-Interscience, New York, 2000, pp. xii+333. ISBN: 0-471-17541-2. DOI: 10.1002/9781118032718. URL: https://doi.org/10.1002/9781118032718.
  22. [28]Taekyun Kim and Dae San Kim. A note on central Bell numbers and polynomials. Russian Journal of Mathematical Physics 27.1 (2020), 76–81. DOI: 10.1134/S1061920820010070.DOI
  23. [29]Martin Klazar. Bell numbers, their relatives, and algebraic differential equations. J. Combin. Theory Ser. A 102.1 (2003), 63–87. ISSN: 0097-3165,1096-0899. DOI: 10.1016/S0097-3165(03)00014–1. URL: https://doi.org/10.1016/S0097-3165(03)00014–1.
  24. [30]Sławomir Michalik and Bożena Tkacz. The Stokes phenomenon for some moment partial differential equations. Journal of Dynamical and Control Systems 25 (2019), 573–598. DOI: 10.1007/s10883–018–9424–9.DOI

Paper details

vlnc:W_ae4926sf
Version
v1 · latest
Published
Fresh — added to the Hub within the last 30 days
Added
License
CC BY 4.0
Usage

views · 0

downloads · 0

A view counts once per browser per day, a download each time the PDF is requested.

  • Mathematics

Not recorded for this paper

View statement
Looking for related papers…
Contents