The Library
Critical random graphs : limiting constructions and distributional properties
Tools
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. ISSN 1083-6489.
|
PDF
WRAP_Goldschmidt_Critical_random_graphs.pdf - Published Version - Requires a PDF viewer. Download (395Kb) |
Official URL: http://www.math.washington.edu/~ejpecp/
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, Engineering and Medicine > 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: |
|
||||
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 (Creative Commons) | ||||
Date of first compliant deposit: | 3 December 2015 | ||||
Date of first compliant Open Access: | 3 December 2015 | ||||
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
Downloads per month over past year