Abstract:
We study the problem of testing the expansion of graphs with bounded degree d in sublinear time. A graph is said to be an \alpha-expander if every vertex set U \subset V of size at most |V|/2 has a neighborhood of size at least \alpha|U|. We show that the algorithm proposed by Goldreich and Ron (ECCC-2000) for testing the expansion of a graph distinguishes with high probability between \alpha-expanders of degree bound d and graphs which are \eps-far from having expansion at least \Omega(\alpha^2). This improves a recent result of Czumaj and Sohler (FOCS-2007) who showed that this algorithm can distinguish between \alpha-expanders of degree bound d and graphs which are \eps-far from having expansion at least \Omega(\alpha^2/\log n). It also improves a recent result of Kale and Seshadhri (ECCC-2007) who showed that this algorithm can distinguish between \alpha-expanders and graphs which are \eps-far from having expansion at least \Omega(\alpha^2) with twice the maximum degree. Finally, our result shows that the conjecture of Goldreich and Ron, on testing the second eigenvalue of the graph, holds when the second eigenvalue lies in a certain interval of constant size. Our methods combine the techniques of the above three papers.