Cheeger inequalities for nonregular graphs I'm looking for a reference for something I thought was easy and well known.
There are (at least) two definitions of expander graphs. There is a combinatorial definition via edge expansion, and an algebraic definition using the spectral gap. 
Neither of these definitions require the graph to be regular.
Now, I always thought that the Cheeger inequalities implied that these definitions were equivalent up to the constants. However, when I looked up the Cheeger inequalities it seems that they only talk about regular graphs.
Is there a version of Cheeger's inequalities for nonregular graphs as well? In general, is it true that a family of (not necessarily regular) graphs is a family of expanders in the first sense iff they are expanders in the second sense?
 A: I eventually found the answer to this question in a paper of Chung.
http://www.math.ucsd.edu/~fan/wp/cheeger.pdf
Turns out there is a nice theory of spectral expansion for nonregular graphs, but the relevant matrix is $D^{-1/2} A D^{-1/2}$, where A is the adjacency matrix and D is a diagonal matrix containing the vertex degrees.
A: For graphs that are not regular, the right matrix to look at is $A_G' := D^{−1/2}A_GD^{−1/2}$. (Here $D^{−1/2}$ is simply the diagonal matrix whose $(i; i)$th entry is $(\deg(i))^{−1/2}$. We assume there are no isolated vertices, so none of the degrees is zero).
This matrix is sometimes called the normalized adjacency matrix of a graph. Note that it also symmetric. Now consider the vector u, whose ith entry is $(\deg(i))^{−1/2}$. So that
$D^{−1/2}u = 1_n \rightarrow D^{−1/2}A_GD^{−1/2}u = D^{−1/2}A_G1_n = u$.
The last equality is because $A_G1_n$ is a vector whose ith entry is $\deg(i)$.
Thus $u$ is an eigenvector with eigenvalue 1. It turns out $λ_{\max}(A_G') = 1$. This is not entirely trivial. From the characterization of $λ_{\max}$, we have:
$$λ_{\max}(A_G')=\max_{x}\frac{x^TA_G'x}{x^Tx}
=\max_{x}
\frac{\sum_{ij\in E}(2x_ix_j)/(\deg(i)\deg(j))^{1/2}}{\sum_i x^2_i}.$$
Notice that $\sum_{ij\in E}x_i^2+x_j^2 =\sum_{k}\deg(k)x_k^2,\quad k=(1,2,...,\text{end})$.
We have
$$\sum_{ij\in E}(2x_ix_j)/(\deg(i)\deg(j))^{1/2}\leq \sum_{ij\in E}\frac{x_i^2}{\deg(i)}+\frac{x_j^2}{\deg(j)}=\sum_i x_i^2.$$
Because in the basic linear algebra this classical equation:
$\lambda_{k+1}=\min_{x\perp \text{span}(v_1,...,v_k)}\frac{x^TMx}{x^Tx}$,where the $x$ is the unit vector written as $\sum_i \alpha_i v_i$ ($\sum_i \alpha_i^2=1$).
So here we have
$\sum_{ij\in E}\frac{x_i^2}{deg(i)}+\frac{x_j^2}{deg(j)}=\sum_i x_i^2=\sum_i x_i^2=1$.
So $λ_{\max}(A_G')\leq 1$.
It turns out that Cheeger’s inequality also holds in terms of the second smallest eigenvalue of $L_G'$ (without the factor d in the denominator, as you can see, no $d$-regular contains in this equations with $d$ terms).
