Eve, Adam and the preferential attachment tree
成果类型：
Article
署名作者：
Contat, Alice; Curien, Nicolas; Lacroix, Perrine; Lasalle, Etienne; Rivoirard, Vincent
署名单位：
Universite Paris Saclay; Universite PSL; Universite Paris-Dauphine
刊物名称：
PROBABILITY THEORY AND RELATED FIELDS
ISSN/ISSBN：
0178-8051
DOI：
10.1007/s00440-023-01253-1
发表日期：
2024
页码：
321-336
关键词：
摘要：
We consider the problem of finding the initial vertex (Adam) in a Barab & aacute;si-Albert tree process (T(n) : n >= 1) at large times. More precisely, given epsilon > 0, one wants to output a subset P (epsilon)(n) of vertices of T(n) so that the initial vertex belongs to P (epsilon)(n) with probability at least 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 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).