The power of 2 choices over preferential attachment

Yury Malyshkin, Elliot Paquette

Published 2013-11-05, updated 2014-02-15Version 2

We introduce a new type of preferential attachment tree that includes choices in its evolution, like with Achlioptas processes. At each step in the growth of the graph, a new vertex is introduced. Two possible neighbor vertices are selected independently and with probability proportional to degree. Between the two, the vertex with smaller degree is chosen, and a new edge is created. We determine with high probability the largest degree of this graph up to some additive error term.