Testing the expansion of a graph

We study the problem of testing the expansion of graphs with bounded degree d in sublinear time. A graph is said to be an α-expander if every vertex set U⊂V of size at most has a neighborhood of size at least α|U|.We show that the algorithm proposed by Goldreich and Ron [9] (ECCC-2000) for testing the expansion of a graph distinguishes with high probability between α-expanders of degree bound d and graphs which are -far from having expansion at least Ω(α2). This improves a recent result of Czumaj and Sohler [3] (FOCS-07) who showed that this algorithm can distinguish between α-expanders of degree bound d and graphs which are -far from having expansion at least Ω(α2/logn). It also improves a recent result of Kale and Seshadhri [12] (ECCC-2007) who showed that this algorithm can distinguish between α-expanders and graphs which are -far from having expansion at least Ω(α2) with twice the maximum degree. Our methods combine the techniques of [3], [9] and [12].