Vertex percolation on expander graphs

We say that a graph G=(V,E)G=(V,E) on nn vertices is a ββ-expander for some constant β>0β>0 if every U⊆VU⊆V of cardinality |U|≤n2 satisfies |NG(U)|≥β|U||NG(U)|≥β|U| where NG(U)NG(U) denotes the neighborhood of UU. In this work we explore the process of deleting vertices of a ββ-expander independently at random with probability n−αn−α for some constant α>0α>0, and study the properties of the resulting graph. Our main result states that as nn tends to infinity, the deletion process performed on a ββ-expander graph of bounded degree will result with high probability in a graph composed of a giant component containing n−o(n)n−o(n) vertices that is in itself an expander graph, and constant size components. We proceed by applying the main result to expander graphs with a positive spectral gap. In the particular case of (n,d,λ)(n,d,λ)-graphs, that are such expanders, we compute the values of αα, under additional constraints on the graph, for which with high probability the resulting graph will stay connected, or will be composed of a giant component and isolated vertices. As a graph sampled from the uniform probability space of dd-regular graphs with high probability is an expander and meets the additional constraints, this result strengthens a recent result due to Greenhill, Holt and Wormald about vertex percolation on random dd-regular graphs. We conclude by showing that performing the above described deletion process on graphs that expand sub-linear sets by an unbounded expansion ratio, with high probability results in a connected expander graph.