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

DOI10.1002/RSA.20872zbMATH Open1444.05130arXiv1810.02041OpenAlexW2949516145MaRDI QIDQ5113931FDOQ5113931

Hüseyin Acan, Boris Pittel

Publication date: 19 June 2020

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

Abstract: 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 $(logn{)}^{-1}$. We also study the bootstrap percolation on $G_{n,k}$, where, each vertex is either initially infected with probability $p$, independently of others, or gets infected later as a result of having $r$ infected neighbors at some point. We show that, for $2lerlek-1$, if $pll(logn{)}^{-r/(r-1)}$, then, with probability approaching 1, the process ends before all vertices get infected. On the other hand, if $pgeomega(logn{)}^{-r/(r-1)}$, where $omega$ is a certain very slowly growing function, then all the vertices get infected with probability approaching 1.

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

Recommendations

• Bootstrap percolation in random \(k\)-uniform hypergraphs
• On the Connectivity of Random k-th Nearest Neighbour Graphs
• Bootstrap percolation on G(n,p) revisited
• Graph bootstrap percolation
• Bootstrap percolation on the random regular graph

zbMATH Keywords

connectivitybootstrap percolationconductanceuniform attachment graph

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Vertex degrees (05C07) Connectivity (05C40)

Cited In (2)

• Giant descendant trees, matchings, and independent sets in age-biased attachment graphs
• On Bollobás‐Riordan random pairing model of preferential attachment graph

This page was built for publication: On connectivity, conductance and bootstrap percolation for a random \(K\)-out, age-biased graph

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