Arora/Barak, in Chapter 21, Theorem 21.9, Page 428, proves:Algebraic Expansion implies Combinatorial ExpansionIf 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 ExpansionIf 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!
Combinatorial Expansion implies Algebraic Expansion
cc.complexity theory;expanders