Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

Diffusion Approximation for the Components in Critical Inhomogeneous Random Graphs of Rank 1.

Turova, Tatyana LU (2013) In Random Structures & Algorithms 43(4). p.486-539
Abstract
Consider the random graph on n vertices 1,...,n. Each vertex i is assigned a type x(i) with x(1),...,x(n) being independent identically distributed as a nonnegative random variable X. We assume that EX3 < infinity. Given types of all vertices, an edge exists between vertices i and j independent of anything else and with probability min{1, x(i)x(j)/n (1 + a/n(1/3))}. We study the critical phase, which is known to take place when EX2 = 1. We prove that normalized by n(-2/3) the asymptotic joint distributions of component sizes of the graph equals the joint distribution of the excursions of a reflecting Brownian motion with diffusion coefficient root EXEX3 and drift a - EX3/EX s. In particular, we conclude that the size of the largest... (More)
Consider the random graph on n vertices 1,...,n. Each vertex i is assigned a type x(i) with x(1),...,x(n) being independent identically distributed as a nonnegative random variable X. We assume that EX3 < infinity. Given types of all vertices, an edge exists between vertices i and j independent of anything else and with probability min{1, x(i)x(j)/n (1 + a/n(1/3))}. We study the critical phase, which is known to take place when EX2 = 1. We prove that normalized by n(-2/3) the asymptotic joint distributions of component sizes of the graph equals the joint distribution of the excursions of a reflecting Brownian motion with diffusion coefficient root EXEX3 and drift a - EX3/EX s. In particular, we conclude that the size of the largest connected component is of order n(2/3). (c) 2013 Wiley Periodicals, Inc. Random Struct. Alg., 43, 486-539, 2013 (Less)
Please use this url to cite or link to this publication:
author
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
Critical Random Graph, Martingale, Connected Components
in
Random Structures & Algorithms
volume
43
issue
4
pages
486 - 539
publisher
John Wiley & Sons Inc.
external identifiers
  • wos:000326026400005
  • scopus:84886443897
ISSN
1098-2418
DOI
10.1002/rsa.20503
language
English
LU publication?
yes
id
3c29ccfd-2955-4ce9-b223-09e452d3888f (old id 4157898)
date added to LUP
2016-04-01 10:17:16
date last changed
2022-04-04 08:33:13
@article{3c29ccfd-2955-4ce9-b223-09e452d3888f,
  abstract     = {{Consider the random graph on n vertices 1,...,n. Each vertex i is assigned a type x(i) with x(1),...,x(n) being independent identically distributed as a nonnegative random variable X. We assume that EX3 &lt; infinity. Given types of all vertices, an edge exists between vertices i and j independent of anything else and with probability min{1, x(i)x(j)/n (1 + a/n(1/3))}. We study the critical phase, which is known to take place when EX2 = 1. We prove that normalized by n(-2/3) the asymptotic joint distributions of component sizes of the graph equals the joint distribution of the excursions of a reflecting Brownian motion with diffusion coefficient root EXEX3 and drift a - EX3/EX s. In particular, we conclude that the size of the largest connected component is of order n(2/3). (c) 2013 Wiley Periodicals, Inc. Random Struct. Alg., 43, 486-539, 2013}},
  author       = {{Turova, Tatyana}},
  issn         = {{1098-2418}},
  keywords     = {{Critical Random Graph; Martingale; Connected Components}},
  language     = {{eng}},
  number       = {{4}},
  pages        = {{486--539}},
  publisher    = {{John Wiley & Sons Inc.}},
  series       = {{Random Structures & Algorithms}},
  title        = {{Diffusion Approximation for the Components in Critical Inhomogeneous Random Graphs of Rank 1.}},
  url          = {{http://dx.doi.org/10.1002/rsa.20503}},
  doi          = {{10.1002/rsa.20503}},
  volume       = {{43}},
  year         = {{2013}},
}