Logo image
Giant descendant trees, matchings, and independent sets in age-biased attachment graphs
Journal article   Open access   Peer reviewed

Giant descendant trees, matchings, and independent sets in age-biased attachment graphs

Hüseyin Acan, Alan Frieze and Boris Pittel
Journal of applied probability, v 59(2), pp 299-324
Jun 2022
url
http://arxiv.org/abs/1908.02407View

Abstract

Original Article
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.

Metrics

3 Record Views

Details

InCites Highlights

Data related to this publication, from InCites Benchmarking & Analytics tool:

Collaboration types
Domestic collaboration
Web of Science research areas
Statistics & Probability
Logo image