A point process describing the component sizes in the critical window of the random graph evolution

被引:10
作者
Janson, Svante
Spencer, Joel
机构
[1] Uppsala Univ, Dept Math, S-75106 Uppsala, Sweden
[2] NYU, Courant Inst, New York, NY 10012 USA
关键词
D O I
10.1017/S0963548306008327
中图分类号
TP301 [理论、方法];
学科分类号
081202 ;
摘要
We study a point process describing the asymptotic behaviour of sizes of the largest components of the random graph G(n, p) in the critical window, that is, for p = n(-1) + lambda n(-4/3), where;. is a fixed real number. In particular, we show that this point process has a surprising rigidity. Fluctuations in the large values will be balanced by opposite fluctuations in the small values such that the sum of the values larger than a small E: (a scaled version of the number of vertices in components of size greater than epsilon n(2/3)) is almost constant.
引用
收藏
页码:631 / 658
页数:28
相关论文
共 26 条
[1]  
Aldous D, 1997, ANN PROBAB, V25, P812
[2]  
Barbour AD, 1992, Poisson approximation
[3]  
Billingsley P., 1968, Convergence of probability measures
[4]  
Bollobas B, 1985, RANDOM GRAPHS
[5]  
Gut A., 2005, PROBABILITY GRADUATE
[6]   THE BIRTH OF THE GIANT COMPONENT [J].
JANSON, S ;
KNUTH, DE ;
LUCZAK, T ;
PITTEL, B .
RANDOM STRUCTURES & ALGORITHMS, 1993, 4 (03) :233-358
[7]   The center of mass of the ISE and the Wiener index of trees [J].
Janson, S ;
Chassaing, P .
ELECTRONIC COMMUNICATIONS IN PROBABILITY, 2004, 9 :178-187
[8]   Cycles and unicyclic components in random graphs [J].
Janson, S .
COMBINATORICS PROBABILITY & COMPUTING, 2003, 12 (01) :27-52
[9]   The Wiener index of simply generated random trees [J].
Janson, S .
RANDOM STRUCTURES & ALGORITHMS, 2003, 22 (04) :337-358
[10]   MULTICYCLIC COMPONENTS IN A RANDOM GRAPH PROCESS [J].
JANSON, S .
RANDOM STRUCTURES & ALGORITHMS, 1993, 4 (01) :71-84