Eve, Adam and the Preferential Attachment Tree

2023/03/08 by Alice Contat, Contat, Alice, Nicolas Curien +7 · 1 voice
Mathematics · #Limits and Structures in Graph Theory #Markov Chains and Monte Carlo Methods #Stochastic processes and statistical mechanics #math.PR #math.ST

paper · pdf · doi:10.48550/arxiv.2303.04752

openalex publication_date 2023/03/08 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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

Discussions

• Some more of the resolutions that happened in the last few years: arxiv.org/abs/2406.18672 arxiv.org/abs/2406.06506 arxiv.org/abs/2303.04752 arxiv.org/abs/2211.05753 arxiv.org/abs/2111.11316 [bsky, 6 points, 0 comments]

Related

• Finding Adam in random growing trees
• Vertices of high degree in the preferential attachment tree
• Finding Adam in noisy trees
• Giant descendant trees, matchings and independent sets in the age-biased attachment graphs
• The number of descendants in a preferential attachment graph