Giant descendant trees, matchings, and independent sets in age-biased attachment graphs. (25th June 2022)

• Record Type: Journal Article
• Authors: Acan, Hüseyin; Frieze, Alan; Pittel, Boris
• Is Part Of: Journal of applied probability. Volume 59:Number 2(2022)
• Page Start: 299
• Page End: 324
• Publication Date: 2022-06-25
• Subjects: Random -- preferential attachment graph -- asymptotics; 05C80 -- 05C05 -- 60C05 -- 05C30; 519.2
• DOI: 10.1017/jpr.2021.59
• Languages: English
• ISSNs: 0021-9002

Abstract

Abstract: We study two models of an age-biased graph process: the $\delta$ -version of the preferential attachment graph model (PAM) and the uniform attachment graph model (UAM), with m attachments for each of the 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 a single beta distribution respectively, and that for $m>1$ the limit is 1. We also analyze the likely performance of two greedy (online) algorithms, for a large matching set and a large independent set, and determine – for each model and each greedy algorithm – both a limiting fraction of vertices involved and an almost sure convergence rate.