Vertex expander bounded away from zero

69 Views Asked by At

Show that for a family of ε-vertex expanders the expansion parameter $h(G_j )$ stays bounded away from 0. Conversely, let $G_1$, $G_2$, . . . be a sequence of k-regular graphs whose number of vertices goes to $\infty$. Show that if the expansion parameter satisfies $h(G_j )$$γ$ for some $γ$ > 0, then $G_1$, $G_2$, . . . is a family of ε-vertex expanders for some ε > 0.

The definition of ε-vertex expanders I am using is as following: a sequence $G_1$, $G_2$, . . . of k-regular graphs on vertex sets $V_1$, $V_2$, . . . is called a family of ε-vertex expanders if |$V_j$ | goes to infinity and for all sets S ⊂ Vj of at most half the vertices, we have |$N(S) \cup S$| ≥ (1 + ε)|$S$|.

I know that a d regular graph that has the largest two eigenvalues, say $\lambda_1$,$\lambda_2$, with $\lambda_1$ bigger than $\lambda_2$, then expansion parameter $h(G) \ge$ $\frac 1 2 (\lambda_1$-$\lambda_2)$, and obviously $ (\lambda_1-\lambda_2) \ge 0$. So is this sufficient to prove the first direction because if it is true for every $G_i$, then it is true for the family of G? For the other direction, I am stuck on how to start the proof (i tried to use the definition of expansion parameter but do not know how to apply it here). Any help is appreciated.

1

There are 1 best solutions below

4
On

Expansion is covered in detail in the book "Pseudorandomness" in the chapter "Expanders" by Vadhan: https://people.seas.harvard.edu/~salil/pseudorandomness/expanders.pdf.

You have asked two perliminary questions on expander graphs recently. I suggest reading up on some literature. This chapter is a good place to start! It includes comparisons between the three main types of expansion: vertex, edge and spectral. See in particular Theorems 4.6, 4.9 and 4.14.