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?]