skip to content

Testing expansion in bounded degree graphs

Presented by: 
A Czumaj [Warwick]
Friday 28th March 2008 - 12:15 to 12:45
INI Seminar Room 1

We consider the problem of testing expansion in bounded degree graphs. We focus on the notion of vertex-expansion: an a-expander is a graph G = (V,E) in which every subset U of V of at most |V|/2 vertices has a neighborhood of size at least a|U|. Our main result is that one can distinguish good expanders from graphs that are far from being weak expanders in time approximately O(n^{1/2}).

We prove that the property testing algorithm proposed by Goldreich and Ron (2000) with appropriately set parameters accepts every a-expander with probability at least 2/3 and rejects every graph that is epsilon-far from an a*-expander with probability at least 2/3, where a* = O(a^2/(d^2 log(n/epsilon))), d is the maximum degree of the graphs, and a graph is called epsilon-far from an a*-expander if one has to modify (add or delete) at least epsilon d n of its edges to obtain an a*-expander. The algorithm assumes the bounded-degree graphs model with adjacency list graph representation and its running time is O(d^2 n^{1/2} log(n/epsilon)/(a^2 epsilon^3)). We will also briefly discuss the recent improvements due to Kale and Seshadhri, Nachmias and Shapira, who reduced the dependency in the expansion of the rejected graphs from O(a^2/(d^2 log(n/epsilon))) to O(a^2/d^2).

Related Links

The video for this talk should appear here if JavaScript is enabled.
If it doesn't, something may have gone wrong with our embedded player.
We'll get it fixed as soon as possible.
University of Cambridge Research Councils UK
    Clay Mathematics Institute London Mathematical Society NM Rothschild and Sons