10
$\begingroup$

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?

Improve this question
$\endgroup$
2
  • $\begingroup$ I'm curious about this also. Did you find or produce a more explicit answer than the one given below? $\endgroup$
    – Elle Najt
    Commented Jun 4, 2017 at 13:38
  • $\begingroup$ 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 $\endgroup$
    – Elle Najt
    Commented Jun 4, 2017 at 15:24

2 Answers 2

Reset to default
3
$\begingroup$

All the inequalities relating the three "definitions" of expander graphs are known in fully explicit forms, so that one can see what happens in first approximation for not completely regular graph (the versions I know only involve the minimal and maximal degrees, which might be too coarse for what you have in mind?) But whether one definition is or is not "better" might then depend on applications, and in different contexts, one of the three aspects might be more suitable (and close to the traditional expanders), while the others have different behavior.

(For instance, Valiant has proposed computation algorithms based on graphs that he feels might be realistic models for the way the brain works, and he mentions explicitly that expansion is a useful property, but if I understand right, his graphs have typically a degree that is approximately the square-root of the number of vertices, which is much more than a classical expander).

Improve this answer
$\endgroup$
0
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .