Eve, Adam and the preferential attachment tree

We consider the problem of finding the initial vertex (Adam) in a Barabási–Albert tree process \( (\mathcal {T}(n): n \ge 1)\) $(\mathcal{T}(n):n\ge 1)$ at large times. More precisely, given \( \varepsilon >0\) $\epsilon >0$ , one wants to output a subset \( \mathcal {P}_{ \varepsilon }(n)\) ${\mathcal{P}}_{\epsilon }(n)$ of vertices of \( \mathcal {T}(n)\) $\mathcal{T}(n)$ so that the initial vertex belongs to \( \mathcal {P}_ \varepsilon (n)\) ${\mathcal{P}}_{\epsilon }(n)$ with probability at least \(1- \varepsilon \) $1-\epsilon$ when n is large. It has been shown by Bubeck, Devroye and Lugosi, refined later by Banerjee and Huang, that one needs to output at least \( \varepsilon ^{-1 + o(1)}\) ${\epsilon }^{-1+o(1)}$ and at most \(\varepsilon ^{-2 + o(1)}\) ${\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).