Premium
On connectivity, conductance and bootstrap percolation for a random k ‐out, age‐biased graph
Author(s) -
Acan Hüseyin,
Pittel Boris
Publication year - 2020
Publication title -
random structures and algorithms
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.314
H-Index - 69
eISSN - 1098-2418
pISSN - 1042-9832
DOI - 10.1002/rsa.20872
Subject(s) - vertex (graph theory) , combinatorics , mathematics , conductance , random graph , graph , random regular graph , discrete mathematics , preferential attachment , 1 planar graph , complex network , chordal graph
A uniform attachment graph (with parameter k ), denoted G n , k in the paper, is a random graph on the vertex set [ n ], where each vertex v makes k selections from [ v − 1] uniformly and independently, and these selections determine the edge set. We study several aspects of this graph. Our motivation comes from two similarly constructed, well‐studied random graphs: k ‐out graphs and preferential attachment graphs. In this paper, we find the asymptotic distribution of its minimum degree and connectivity, and study the expansion properties of G n , k to show that the conductance of G n , k is of order( log n ) − 1 . We also study the bootstrap percolation on G n , k , where r infected neighbors infect a vertex, and show that if the probability of initial infection of a vertex is negligible compared to( log n ) − r / ( r − 1 )then with high probability (whp) the disease will not spread to the whole vertex set, and if this probability exceeds( log n ) − r / ( r − 1 )by a sub‐logarithmical factor then the disease whp will spread to the whole vertex set.