Combinatorial Expansion implies Algebraic Expansion

Question

Arora/Barak, in Chapter 21, Theorem 21.9, Page 428, proves:

Algebraic Expansion implies Combinatorial Expansion

If G is a $(n, d, x)$ expander graph, then it is an $(n, d, (1-x)/2)$ edge expander.

(good, I understand this part)

They they go on to state:

Combinatorial Expansion implies Algebraic Expansion

If G is a (n, d, p) edge expander, then i's second largest eigen value (without taking the absolute values) is at most $1 - p^2/2$. Furthermore, if G has all self loops, then it is an $(n, d, 1-\epsilon)$ expander where $\epsilon = min(2/d, p^2/2$).

Now, this is the part I am unhappy with. Here is what I understand:

If G is bipartite, it has an eigen value of -1, and thus we can't say much about the 2nd largest absolute value of the eigen values.

If G has all self loops, it's clearly not bipartite.

However, the above theorem does not make any guarantees about graphs G, which are:

(1) non-bipartite (2) do not contain all self loops.

For graphs in this class, do we have a proof of "combinatorial expansion" implies "algebraic expansion"? [If the answer is yes, can you please provide a reference?]

Thanks!

Answer 1

If we have combinatorial expansion, then the second eigenvalue (without taking absolute value) is not too large (or, equivalently, second eigenvalue of the Laplacian is not too small) no matter what (that is, regardless of bipartiteness or having self-loops or even all vertices having the same degree, if notions are defined properly). See the proof of Cheeger's inequality, for example here:

Spielman's lecture notes on Cheeger's inequality.