Return to Answer

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 http://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).

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

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 http://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).

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 http://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).

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 http://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).

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 http://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).