ECCC-Report TR07-118https://eccc.weizmann.ac.il/report/2007/118Comments and Revisions published for TR07-118en-usWed, 28 Nov 2007 09:53:13 +0200
Paper TR07-118
| Testing the Expansion of a Graph |
Asaf Nachmias,
Asaf Shapira
https://eccc.weizmann.ac.il/report/2007/118We 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.
Wed, 28 Nov 2007 09:53:13 +0200https://eccc.weizmann.ac.il/report/2007/118