| Testing the Expansion of a Graph (2008) | |||||||||||||||
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 α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 [11] (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. Finally, our result shows that the conjecture of Goldreich and Ron [9], 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 [3], [9] and [11]. | |||||||||||||||
Publication details | |||||||||||||||
| |||||||||||||||