MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!

share|cite|improve this question
up vote 16 down vote accepted

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.

share|cite|improve this answer
Just to show that this is an expander graph one just need a non-trivial bound towards Ramanujan's conjecture, so Sarnak-Xue result will be enough (as well as many others results). – Asaf Mar 16 '13 at 22:18

Here is one secondary reference:

Salil Vadhan, Lecture Notes, 2009. Chapter 4: Expander Graphs. p.62. (PDF download link)


share|cite|improve this answer
Sorry for being unable to accept both answers... Thanks, anyway! – Seva Mar 17 '13 at 7:38

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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