Expansion properties of a random regular graph after random vertex deletions (Q925017)

Random regular graphs of order \(n\) and constant degree \(d>2\) are considered. Each vertex is independently deleted with probability \(n^{-\alpha}\) where \(\alpha=\alpha(n)\) is bounded away from 0 for increasing \(n\). It is shown that asymptotically almost surely the remaining graph has a connected component of size \(n-o(n)\) that is a \(\beta\)-expander, and all other components are trees of bounded size. Here a \(\beta\)-expander is a graph in which any \(k\)-subset of vertices has at least \(\beta k\) outside neighbours for \(k\) at most equal to half the number of vertices. Sharper results are obtained with extra conditions on \(\alpha\). An internet application with client failure is discussed.