Testing the Expansion of a Graph.
Asaf Nachmias, A. Shapira · 2007
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 1|V | has a neigh-2 borhood 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 / log n). 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]. 1