Giant descendant trees and matching sets in the preferential attachment graph
Hüseyin Acan, ALAN M. FRIEZE, Boris G. Pittel · arXiv (Cornell University) · 2019
We study the $\delta$-version of the preferential attachment graph with $m$ attachments for each of incoming vertices. We show that almost surely the scaled size of a breadth-first (descendant) tree rooted at a fixed vertex converges, for $m=1$, to a limit whose distribution is a mixture of two beta distributions, and that for $m>1$ the limit is $1$. We also analyze the likely performance of a greedy matching algorithm for all $m\ge 1$ and establish an almost sure lower bound for the size of the matching set.