1
|
Giant descendant trees, matchings, and independent sets in age-biased attachment graphs. J Appl Probab 2022. [DOI: 10.1017/jpr.2021.59] [Citation(s) in RCA: 0] [Impact Index Per Article: 0] [Reference Citation Analysis] [Abstract] [Track Full Text] [Journal Information] [Subscribe] [Scholar Register] [Indexed: 11/05/2022]
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.
Collapse
|