On Bollobás‐Riordan random pairing model of preferential attachment graph. Issue 4 (28th December 2020)

• Record Type: Journal Article
• Authors: Pittel, Boris
• Is Part Of: Random structures & algorithms. Volume 58:Issue 4(2021)
• Page Start: 691
• Page End: 725
• Publication Date: 2020-12-28
• Subjects: asymptotics -- chord diagrams -- degrees -- order statistics -- pairings -- random graphs -- recursive trees -- vertex expansion; Random graphs -- Periodicals; Mathematical analysis -- Periodicals; 519
• DOI: 10.1002/rsa.20985
• Languages: English
• ISSNs: 1042-9832

Abstract

Abstract: Bollobás‐Riordan random pairing model of a preferential attachment graph G m n is studied. Let { W j } j ≤ mn + 1 be the process of sums of independent exponentials with mean 1. We prove that the degrees of the first ν m n ≔ n m m + 2 − ε vertices are jointly, and uniformly, asymptotic to { 2 ( m n ) 1 / 2 ( W m j 1 / 2 − W m ( j − 1 ) 1 / 2 ) } j ∈ [ ν m n ], and that with high probability (whp) the smallest of these degrees is n ε ( m + 2 ) 2 m, at least. Next we bound the probability that there exists a pair of large vertex sets without connecting edges, and apply the bound to several special cases. We propose to measure an influence of a vertex v by the size of a maximal recursive tree (max‐tree) rooted at v . We show that whp the set of the first ν m n vertices does not contain a max‐tree, and the largest max‐tree has size of order n . We prove that, for m > 1, ℙ ( G m n is connected ) ≥ 1 − O ( ( log n ) − ( m − 1 ) / 3 + o ( 1 ) ) . We show that the distribution of scaled size of a generic max‐tree in G 1 n converges to a mixture of two beta distributions.