# Does it make sense to talk about expansion in irregular graphs?

Usually, one defines an expander graph to be a regular graph satisfying one of the following properties: Either the edge-expansion is large, or the spectral gap is large, or the mixing time is at most logarithmic in the number of vertices, or it satisfies a mixing-lemma type property.

It doesn't really matter much which property we require, since up to a constant they are all equivalent. This is also the reason why the concept of expander graphs is so powerful.

My question is: What happens in graphs that are far from regular? One can look at each of these properties separately, but is there a sense in which they are equivalent? If not, does it make sense to talk about expander graphs in this setting?

• I'm curious about this also. Did you find or produce a more explicit answer than the one given below? Commented Jun 4, 2017 at 13:38
• There is a more general formula relating the spectral gap of the Laplacian to Cheeger constant here (it involves computing the min and max degree of the graph) : people.math.ethz.ch/~kowalski/expanseurs-x-en.pdf Commented Jun 4, 2017 at 15:24

It does make sense, instead of dividing by the min of the number of vertices of the two sets, one can divide by the minimum volume of the two sets. (The volume of a set $$A$$, denoted $$\operatorname{vol}(A)$$, is the sum of degrees in the set, notice that $$\operatorname{vol}(A)=2e(A)+e(A, V\setminus A)$$ where $$e(A)$$ is the number of edges inside set $$A$$, and $$e(A, V\setminus A)$$ is the number of edges between $$A$$ and its complement.)
A nice reference is $$`$$Spectral graph theory' by Chung.