Avoiding a giant component (Q2748427)

This paper deals with random graphs. A sequence of events \(\{E_n\}\) is said to occur with high probability if \(\lim_{n\to\infty} P[E_n]= 1\). Suppose \(e_1, e_1';e_2,e_2';\dots\) is a sequence of ordered pairs of edges selected uniformly at random from the edge set of \(K_n\) (a complete graph with \(n\) vertices). At stage \(i\) we choose one of \(e_i\), \(e_i'\) to be an edge in our graph. The following is the main result of this paper indicating that choices can be made so that with high probability the size of the largest component of the graph formed at stage \(0.535n\) is polylogarithmic in \(n\).NEWLINENEWLINENEWLINETheorem: There is an algorithmic \(A\) and a positive constant \(c_0> 0.535\) such that with high probability the size of the largest component in \(G_A= G_A(m)\), with \(m= c_0n\) is bounded by \((\log n)^{O(1)}\).