On connectivity, conductance and bootstrap percolation for a random k-out, age-biased graph

Hüseyin Acan, Boris Pittel

Published 2018-10-04Version 1

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 $(\log n)^{-r/(r-1)}$ is a threshold probability of initial infection for the spread of the disease to the whole vertex set.