Eve, Adam and the Preferential Attachment Tree

Abstract

We consider the problem of finding the initial vertex (Adam) in a Barabási--Albert tree process $(\mathcal{T}(n):n\ge 1)$ at large times. More precisely, given $\epsilon >0$, one wants to output a subset ${\mathcal{P}}_{\epsilon }(n)$ of vertices of $\mathcal{T}(n)$ so that the initial vertex belongs to ${\mathcal{P}}_{\epsilon }(n)$ with probability at least $1-\epsilon$ when $n$ is large. It has been shown by Bubeck, Devroye & Lugosi, refined later by Banerjee & Huang, that one needs to output at least ${\epsilon }^{-1+o(1)}$ and at most ${\epsilon }^{-2+o(1)}$ vertices to succeed. We prove that the exponent in the lower bound is sharp and the key idea is that Adam is either a ``large degree" vertex or is a neighbor of a ``large degree" vertex (Eve).

11 pages, comments are welcome !