# Combinatorial Expansion implies Algebraic Expansion

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!

• The self-loops are, indeed, a sufficient but not necessary condition. You could re-do the proof and check for yourself what's needed there. – Dana Moshkovitz Nov 14 '11 at 13:14
• I'm not sure that I understand your bipartite objection. The statement clearly says "without taking the absolute value", so it implies a result about non-bipartite edge expanders. – John Moeller Nov 14 '11 at 16:57