Birth control for giants (Q949755): Difference between revisions

From the authors' introducton: ``We consider a problem of \textit{Dimitris Achlioptas} that has received considerable attention. Paul is given \(n\) vertices and a graph \(G\) on those vertices that will change with time. Initially \(G\) has no edges. Each round two edges of \(K_n\), call them \(e_1=\{v_1,v_2\}\) and \(e_2=\{v_3,v_4\}\) are generated independently and uniformly at random. Paul must select one of those edges and add it to \(G\). Paul's object is to avoid creating a giant component, a component of size \(\Omega(n)\), for as long as possible. For us, size always denotes number of vertices. It shall be convenient to parametrize the number of rounds \(m\) by \(m=t\frac{n}{2}\). We shall think of \(t\) as the ``time'' of the process. For any \(t<1\) Paul can succeed by simply always taking the first edge - the graph then selected is the usual Erdős-Rényi random graph which has component sizes \(O(\ln{n})\). (Our statements about Paul's achievements are all with probability tending to \(1\) as \(n\to\infty\).)'' ``While the Achlioptas problem was our original motivation we have become intrigued by what we shall call an Achlioptas process. Fix any algorithm that determines which edge Paul shall select. Let \(G_m\) denote the graph after \(m\) rounds. Then \(G_0,G_1,\dots\) forms a random graph process, that evolves from the empty graph to a graph with a giant component and, of course, beyond. For a class of algorithms we shall be able to analyze this process. There are interesting analogies to the well-studied Erdős-Rényi evolution - some of which we can prove and others of which remain conjectures.'' In this paper the authors study the susceptibility \(S(t)\) at time \(t\) defined as the expected component size of a uniformly chosen vertex. They show that the expected change in \(S(t)\) produces a differential equation for \(S(t)\) as \(n\to\infty\). There is a critical point \(t_c\) so that \(S(t)\to\infty\) as \(t\) approaches \(t_c\) from below. The authors show that, for all subcritical \(t<t_c\), the discrete random process asymptotically follows the differential equation and that the component sizes of the graph have an exponential tail. In particular, it is shown that the largest component is only logarithmic in size. The proofs of these results employ classic branching processes technique. In the supercritical regime \(t>t_c\) the existence of a giant component is shown, so that \(t=t_c\) may be fairly considered a phase transition. The paper also contains approximate results obtained using computer aided solutions to the possible differential equations for susceptibility. In this way the authors establish lower and upper bounds on the extent to which one can either delay or accelerate the birth of the giant component.