Testing Expansion in Bounded-Degree Graphs

We consider the problem of testing expansion in bounded degree graphs. We focus on the notion of vertex-expansion: an alpha-expander is a graph G = (V, E) in which even-subset U sube V of at most |V|/2 vertices has a neighborhood of size at least alphaldr|U|. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time O tilde(radicn). We prove that the property testing algorithm proposed by Goldreich and Ron (2000) with appropriately set parameters accepts every alpha-expander with probability at least 2/3 and rejects every graph that is epsiv-far from an alpha*-expander with probability at least 2/3, where alpha*=Theta(alpha 2 /(d 2 log (n/epsiv))) and d is the maximum degree of the graphs. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is O(d 2 (radicn log (n/epsiv))/alpha 2 epsiv 3 ).