Journal of Combinatorics

Volume 4 (2013)

Number 1

An example of graph limits of growing sequences of random graphs

Pages: 67 – 80

DOI: http://dx.doi.org/10.4310/JOC.2013.v4.n1.a3

Authors

Svante Janson (Department of Mathematics, Uppsala University, Sweden)

Simone Severini (Department of Computer Science and Department of Physics & Astronomy, University College London, United Kingdom)

Abstract

In this paper, we consider a class of growing random graphs obtained by creating vertices sequentially one by one. At each step, we uniformly choose the neighbors of the newly created vertex; its degree is a random variable with a fixed but arbitrary distribution, depending on the number of existing vertices. Examples from this class turn out to be the Erdős–Rényi random graph, a natural random threshold graph, etc. By working with the notion of graph limits, we define a kernel which, under certain conditions, is the limit of the growing random graph. Moreover, for a subclass of models, the growing graph on any given $n$ vertices has the same distribution as the random graph with n vertices that the kernel defines. The motivation stems from a model of graph growth whose attachment mechanism does not require information about properties of the graph at each iteration.

2010 Mathematics Subject Classification

05C80

Full Text (PDF format)