On Bollobás‐Riordan random pairing model of preferential attachment graph. Issue 4 (28th December 2020) - Pittel, Boris
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.