Vertex percolation on expander graphs

We say that a graph G = (V, E) on n vertices is a P-expander for some constant beta > 0 if every U subset of V of cardinality |U| <= n/2 satisfies |N-G(U)| >= beta|U| where N-G(U) denotes the neighborhood of U. In this work we explore the process of deleting vertices of a beta-expander independently at random with probability n-(alpha) for some constant alpha > 0, and study the properties ofthe resulting graph. Our main result states that as n tends to infinity, the deletion process performed on beta-expander graph of bounded degree will result with high probability in a graph composed of a giant component containing 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, lambda)-graphs, that are such expanders, we compute the values of alpha, 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 d-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 d-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. (C) 2008 Elsevier Ltd. All rights reserved.