<p>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:</p>

<p><a href="http://www.cs.yale.edu/homes/spielman/561/lect07-09.pdf" rel="nofollow">Spielman's lecture notes on Cheeger's inequality.</a></p>

CC BY-SA 3.0
2011-11-14T21:12:27.920Z
2011-11-14T21:12:27.920Z
Mahdi Cheraghchi
<p>Arora/Barak, in Chapter 21, Theorem 21.9, Page 428, proves:</p>

<blockquote>
  <h3>Algebraic Expansion implies Combinatorial Expansion</h3>
  
  <p>If G is a $(n, d, x)$ expander graph, then it is an $(n, d, (1-x)/2)$
  edge expander.</p>
</blockquote>

<p>(good, I understand this part)</p>

<p>They they go on to state:</p>

<blockquote>
  <h3>Combinatorial Expansion implies Algebraic Expansion</h3>
  
  <p>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$).</p>
</blockquote>

<p>Now, this is the part I am unhappy with. Here is what I understand:</p>

<p>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.</p>

<p>If G has all self loops, it's clearly not bipartite.</p>

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

<p>(1) non-bipartite
(2) do not contain all self loops.</p>

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

<p>Thanks!</p>

CC BY-SA 3.0
2011-11-14T13:14:32.827Z
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
CC BY-SA 3.0
2011-11-14T16:57:47.350Z
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.
Josephine Moeller
<cc.complexity-theory><expanders>
Combinatorial Expansion implies Algebraic Expansion
anonymous coward
# Combinatorial Expansion implies Algebraic Expansion

(Asked by: username_0 on 2011-11-14)

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!

**Tags:** cc.complexity-theory, expanders

> **Comments:**
> **username_1**: 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.  
> **username_2**: 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.  

---

## 1 answers

### Answer by username_3 on 2011-11-14. Score: 4

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.](http://www.cs.yale.edu/homes/spielman/561/lect07-09.pdf)


---

