Paper Info
Title
Creating a Giant Component
Abstract
Let $c$ be a constant and $(e_1,f_1), (e_2,f_2), \dots, (e_{cn},f_{cn})$ be a sequence of ordered pairs of edges on vertex set $[n]$ chosen uniformly and independently at random. Let $A$ be an algorithm for the on-line choice of one edge from each presented pair, and for $i= 1,\hellip,cn$ let $G_A(i)$ be the graph on vertex set $[n]$ consisting of the first $i$ edges chosen by $A$. We prove that all algorithms in a certain class have a critical value $c_A$ for the emergence of a giant component in $G_A(cn) (ie$, if $c \gt c_A$, then with high probability the largest component in $G_A(cn)$ has $o(n)$ vertices, and if $c c_A$ then with high probability there is a component of size $\Omega(n)$ in $G_A(cn))$. We show that a particular algorithm in this class with high probability produces a giant component before $0.385 n$ steps in the process ($ie$, we exhibit an algorithm that creates a giant component relatively quickly). The fact that another specific algorithm that is in this class has a critical value resolves a conjecture of Spencer.In addition, we establish a lower bound on the time of emergence of a giant component in any process produced by an on-line algorithm and show that there is a phase transition for the off-line version of the problem of creating a giant component.
Year
DOI
Venue
2006
10.1017/S0963548306007486
Combinatorics, Probability & Computing
Keywords
Field
DocType
particular algorithm,largest component,on-line algorithm,high probability,gt c_a,vertex set,giant component,critical value,specific algorithm,certain class,lower bound,phase transition
Discrete mathematics,Combinatorics,Phase transition,Vertex (geometry),Upper and lower bounds,Critical value,Ordered pair,Giant component,Omega,Conjecture,Mathematics
Journal
Volume
Issue
ISSN
15
4
0963-5483
Citations 
PageRank 
References 
13
1.01
5
Authors
2
Name
Order
Citations
PageRank
Tom Bohman125033.01
David Kravitz213815.71