For a prime $p$, consider the graph on the vertex set ${\mathbb F}_p$, in which every vertex $z$ is adjacent to $z\pm 1$ and also to $z^{-1}$ (unless $z=0$). I was told that this graph is known to be an expander, but the person who told me this couldn't recall where exactly this graph has been studied. Does anybody know the reference? Thanks!
Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)
|
8
|
|
||
|
|
|
11
|
Here is Theorem 4.4.2 in Lubotzky's lovely book "Discrete groups, expanding graphs and invariant measures". On the projective line over $\mathbb{F}_p$, connect $z$ to $z\pm 1$ and to $-\frac{1}{z}$; this is a family of 3-regular expander graphs. The proof is indeed based on Selberg's 3/16-theorem. |
|||||
|
You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.
|
3
|
Here is one secondary reference:
|
|||
|
