16
$\begingroup$

I need to construct d-regular expander graph for some small fixed d (like 3 or 4) of n vertices.

What is the easiest method to do this in practice? Constructing a random d-regular graph, which is proven to be a.a.s. an expander?

I also read about Margulis constructions and Ramanujan graphs that are expanders and a construction using a zig-zag product. Wikipedia gives a nice but very short overview: http://en.wikipedia.org/wiki/Expander_graph#cite_note-10 But which method do I choose in practice?

For me, these methods seem all very complicated to implement and in particular to understand and maybe quite specific. Aren't there easier methods, maybe based on permutations or so, to practically generate a sequence of d-regular expander graphs?

Is it maybe easier to construct d-regular bipartite expander graphs?

I also have another question: What about families of bad d-regular expanders? Does such a notion make sense? Can one construct a family of d-regular graphs (that are of course connected) that is as bad as possible in the sense of an expander?

Thanks in advance.

Improve this question
$\endgroup$
6
  • 2
    $\begingroup$ There are easier explicit constructions than the ones you listed, but random graphs should do the trick and have better parameters. $\endgroup$
    – Yuval Filmus
    Commented Apr 24, 2013 at 14:13
  • $\begingroup$ Can you maybe give names or references of the constructions? By better parameters, you mean a better (edge) expansion, I guess? $\endgroup$
    – user2145167
    Commented Apr 24, 2013 at 14:32
  • 1
    $\begingroup$ András gave the example I had in mind, but in general, random graphs are (almost always) better than explicit constructions. Not only is the edge expansion larger, any other similar property which is helpful for your algorithm is probably automatically satisfied by random graphs. $\endgroup$
    – Yuval Filmus
    Commented Apr 24, 2013 at 17:16
  • $\begingroup$ Ok, for degree 3, András example or the random graphs seem to be good enough for my application. It would be interesting, in particular with regard to the random graphs, to construct a 3-reg graph family that is not an expander. But this is probably very hard or not possible? $\endgroup$
    – user2145167
    Commented Apr 24, 2013 at 20:22
  • 4
    $\begingroup$ Take a union of $K_4$s. If you want a connected graph, remove one edge from each $K_4$ (forming a graph known as the diamond graph), and connect them in a cycle. $\endgroup$
    – Yuval Filmus
    Commented Apr 25, 2013 at 3:20

2 Answers 2

Reset to default
13
$\begingroup$

If you don't mind graphs with self-loops, the "easiest" expander family is probably this one, giving expanders that are 3-regular.

Start with some prime number $p$, and construct vertices numbered $0$ to $p-1$. For every vertex $u \ne 0$, connect $u$ to $u-1$ and $u+1$, modulo $p$. Also connect $u$ to the unique vertex $v$ such that $uv \equiv 1 \mod p$.

As an example, the 7-vertex graph in the family is a 7-cycle with vertices numbered sequentially around the cycle; there are self-loops on $6$, $0$, and $1$; finally, there are chords joining $3$ and $5$, and $2$ and $4$.

See https://mathoverflow.net/questions/124708/an-expander-graph for further discussion and references. There are lots of more detailed pointers by searching on "expander" at CSTheory, Math.SE, and MO.

As Yuval Filmus points out, the random construction is likely to give better results in general, but of course may not yield an expander (especially for small graphs).

Improve this answer
$\endgroup$
1
  • $\begingroup$ Thanks for the remark. I had searched for expanders before on the other sites but not on MO, there really seems to be more results. $\endgroup$
    – user2145167
    Commented Apr 24, 2013 at 20:11
1
$\begingroup$

Given a random regular graph is an expander w.h.p. (follow the reference given in the documentation of the MATLAB code linked below), I once used the following:

http://www.mathworks.com/matlabcentral/fileexchange/29786-random-regular-generator/content/randRegGraph/createRandRegGraph.m

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.