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

DOI10.1017/JPR.2021.59zbMATH Open1492.05141arXiv1908.02407OpenAlexW3101210987MaRDI QIDQ5086992FDOQ5086992

Hüseyin Acan, Boris Pittel, Alan Frieze

Publication date: 8 July 2022

Published in: Journal of Applied Probability (Search for Journal in Brave)

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

Full work available at URL: https://arxiv.org/abs/1908.02407

Recommendations

• A note on the number of matchings and independent sets in trees
• scientific article; zbMATH DE number 1334618
• On the independence number and the chromatic number of generalized preferential attachment models
• On maximal independent sets of nodes in trees
• On tree census and the giant component in sparse random graphs
• On subgraph number independence in trees
• Connected graphs with a large number of independent sets
• Matchings in random superpositions of bipartite trees
• Scaling limits and influence of the seed graph in preferential attachment trees
• Publication:4726290

zbMATH Keywords

asymptoticsrandom graphpreferential attachment graph

Mathematics Subject Classification ID

Trees (05C05) Random graphs (graph-theoretic aspects) (05C80) Combinatorial probability (60C05) Enumeration in graph theory (05C30)

Cites Work

• Directed scale-free graphs
• Random graphs and complex networks. Volume 1
• Emergence of Scaling in Random Networks
• Title not available (Why is that?)
• Random Graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• The degree sequence of a scale-free random graph process
• Random graphs.
• The Maximum Degree of the Barabási–Albert Random Tree
• The diameter of a scale-free random graph
• Concentration of measure and isoperimetric inequalities in product spaces
• Asymptotic behavior and distributional limits of preferential attachment graphs
• A new class of scale free random graphs
• Note on the heights of random recursive trees and random m‐ary search trees
• Introduction to Random Graphs
• On certain connectivity properties of the internet topology
• The cover time of the preferential attachment graph
• On random trees
• Lower Bounds and Algorithms for Dominating Sets in Web Graphs
• Robustness and Vulnerability of Scale-Free Random Graphs
• Looking for vertex number one
• High Degree Vertices and Eigenvalues in the Preferential Attachment Graph
• On the probable behaviour of some algorithms for finding the stability number of a graph
• On a random graph evolving by degrees
• Joint degree distributions of preferential attachment random graphs
• On Bollobás‐Riordan random pairing model of preferential attachment graph
• Title not available (Why is that?)
• Perfect matchings and Hamiltonian cycles in the preferential attachment model
• Crawling on Simple Models of Web Graphs
• Linearized chord diagrams and an upper bound for vassiliev invariants
• Random Recursive Trees and Preferential Attachment Trees are Random Split Trees
• Preferential attachment without vertex growth: emergence of the giant component
• On a memory game and preferential attachment graphs
• On connectivity, conductance and bootstrap percolation for a random k‐out, age‐biased graph

This page was built for publication: Giant descendant trees, matchings, and independent sets in age-biased attachment graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5086992)