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?

  • $\begingroup$ I'm curious about this also. Did you find or produce a more explicit answer than the one given below? $\endgroup$ Jun 4 '17 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$ Jun 4 '17 at 15:24

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).


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.