2
$\begingroup$

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!

$\endgroup$
  • 3
    $\begingroup$ 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. $\endgroup$ – Dana Moshkovitz Nov 14 '11 at 13:14
  • 1
    $\begingroup$ 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. $\endgroup$ – John Moeller Nov 14 '11 at 16:57
4
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.