Premium
Avoiding a giant component
Author(s) -
Bohman Tom,
Frieze Alan
Publication year - 2001
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.1019
Subject(s) - combinatorics , graph , mathematics , struct , random graph , giant component , enhanced data rates for gsm evolution , discrete mathematics , computer science , artificial intelligence , programming language
Let e 1 , e ′ 1 ; e 2 , e ′ 2 ;…; e i , e ′ i ;⋅⋅⋅ be a sequence of ordered pairs of edges chosen uniformly at random from the edge set of the complete graph K n (i.e. we sample with replacement). This sequence is used to form a graph by choosing at stage i , i =1,…, one edge from e i , e ′ i to be an edge in the graph, where the choice at stage i is based only on the observation of the edges that have appeared by stage i . We show that these choices can be made so that whp the size of the largest component of the graph formed at stage 0.535 n is polylogarithmic in n . This resolves a question of Achlioptas. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 19, 75–85, 2001