Addario-Berry, L., Broutin, N. and Goldschmidt, C. (Christina) (2010) Critical random graphs : limiting constructions and distributional properties. Electronic Journal of Probability, Vol.15 . pp. 741-775.

Preview

PDF WRAP_Goldschmidt_Critical_random_graphs.pdf - Published Version - Requires a PDF viewer. Download (395Kb)

Request Changes to record.

Abstract

We consider the Erdos-Renyi random graph G(n, p) inside the critical window, where p = 1/n + lambda n(-4/3) for some lambda is an element of R. We proved in Addario-Berry et al. [2009+] that considering the connected components of G(n, p) as a sequence of metric spaces with the graph distance rescaled by n(-1/3) and letting n -> infinity yields a non-trivial sequence of limit metric spaces C = (C-1, C-2,...). These limit metric spaces can be constructed from certain random real trees with vertex-identifications. For a single such metric space, we give here two equivalent constructions, both of which are in terms of more standard probabilistic objects. The first is a global construction using Dirichlet random variables and Aldous' Brownian continuum random tree. The second is a recursive construction from an inhomogeneous Poisson point process on R+. These constructions allow us to characterize the distributions of the masses and lengths in the constituent parts of a limit component when it is decomposed according to its cycle structure. In particular, this strengthens results of Luczak et al. [1994] by providing precise distributional convergence for the lengths of paths between kernel vertices and the length of a shortest cycle, within any fixed limit component.

Item Type:	Journal Article
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Statistics
Library of Congress Subject Headings (LCSH):	Random graphs
Journal or Publication Title:	Electronic Journal of Probability
Publisher:	University of Washington. Dept. of Mathematics
ISSN:	1083-6489
Official Date:	2010
Dates:	Date Event 2010 Published
Volume:	Vol.15
Number of Pages:	35
Page Range:	pp. 741-775
Status:	Peer Reviewed
Publication Status:	Published
Access rights to Published version:	Open Access
Funder:	Natural Sciences and Engineering Research Council of Canada (NSERC), Engineering and Physical Sciences Research Council (EPSRC)
Grant number:	EP/D065755/1 (EPSRC)

Data sourced from Thomson Reuters' Web of Knowledge

Request changes or add full text files to a record

Repository staff actions (login required)

View Item

Downloads