Avoidance of a giant component in half the edge set of a random graph

被引:53
作者
Bohman, T [1 ]
Frieze, A
Wormald, NC
机构
[1] Carnegie Mellon Univ, Dept Math Sci, Pittsburgh, PA 15213 USA
[2] Univ Melbourne, Dept Math & Stat, Melbourne, Vic 3010, Australia
关键词
D O I
10.1002/rsa.20038
中图分类号
TP31 [计算机软件];
学科分类号
081202 ; 0835 ;
摘要
Let e(1), e(2),... be a sequence of edges chosen uniformly at random from the edge set of the complete graph K-n (i.e., we sample with replacement). Our goal is to choose, for m as large as possible, a subset E subset of or equal to {e(1),e(2),..., e(2m)}, \E\ = m, such that the size of the largest component in G = ([n], E) is o(n) (i.e., G does not contain a giant component). Furthermore, the selection process must take place on-line; that is, we must choose to accept or reject on e(i) based on the previously seen edges e(1),..., e(i-1). We describe an on-line algorithm that succeeds whp for m = 9668n. A sequence or events F, is said to occur with high probability (whp) if lim(n-->infinity) Pr(E-n) = 1. Furthermore, we find a tight threshold for the off-line version of this question; that is, we find the threshold for the existence of m out of 2m random edges without a giant component. This threshold is m = c*n where c* satisfies a certain transcendental equation, c* is an element of [.9792,.9793]. We also establish new upper bounds for more restricted Achlioptas processes. (C) 2004 Wiley Periodicals, Inc.
引用
收藏
页码:432 / 449
页数:18
相关论文
共 7 条
  • [1] [Anonymous], RANDOM GRAPHS
  • [2] Bohman T., 2002, Random Structures & Algorithms, V20, P126, DOI 10.1002/rsa.10018
  • [3] Avoiding a giant component
    Bohman, T
    Frieze, A
    [J]. RANDOM STRUCTURES & ALGORITHMS, 2001, 19 (01) : 75 - 85
  • [4] ERDOS P, 1960, B INT STATIST INST, V38, P343
  • [5] Janson S, 2000, WIL INT S D
  • [6] Spencer Joel, 1992, Combinatorial Probability Comput., V1, P81, DOI 10.1017/S09635483000000802,4,6
  • [7] Wormald N C, 1999, LECT APPROXIMATION R, P73