9
$\begingroup$

I am looking for a book that covers expander graphs rigorously. Preferably a book aimed at beginners.

$\endgroup$
10
$\begingroup$

Elementary Number Theory, Group Theory and Ramanujan Graphs (Giuliana Davidoff, Peter Sarnak, and Alain Valette, 2003) is intended to make the construction of expander graphs accessible to advanced undergraduates. That's probably about as close to "beginners" as you're going to get for this sort of topic.

$\endgroup$
1
  • $\begingroup$ Sarnak also has an earlier book called "Applications of Modular Forms" which could also complement the reference mentioned above. $\endgroup$ – user135520 May 12 at 17:10
10
$\begingroup$

The recent book of Emmanuel Kowalksi "An introduction to expander graphs" is very nicely written and covers a lot of material, from background to applications, with the description of the classical constructions.

A preliminary version of the book is freely available on Kowalski's webpage https://people.math.ethz.ch/~kowalski/expander-graphs.pdf

$\endgroup$
8
$\begingroup$

One should mention Lubotzky's lovely book "Discrete groups, expanding graphs and invariant measures" (1994), I think the first book written on the subject, which shows how the problem of constructing expander families connects to lots of other interesting mathematics.

My already-mentioned book with Giuliana Davidoff and Peter Sarnak was based on a master class I taught on the subject of Ramanujan graphs, itself based on a set of unpublished notes by Giuliana and Peter. Our aim is to present one family of expanders: the graphs of Lubotzky-Phillips-Sarnak (also constructed independently by Margulis). The prerequisites are those of a 2nd year master class: linear algebra, a standard course in algebra (groups, rings and fields), measure theory, some combinatorics.

The book "Expander families and Cayley graphs - a beginner's guide", by Mike Krebs and Anthony Shaheen (2011), starts lower in terms of prerequisites and has lots of drawings, tons of exercises, as well as students projects. Depending what kind of beginner you are, it may be more suitable...

$\endgroup$
2
$\begingroup$

I recommend "Elementary Number Theory, Group Theory and Ramanujan Graphs", quoted above in David Eppstein's answer.

There is also the following reference, that I know only a little bit but seems interesting.

Expander graphs and their applications

Authors: Shlomo Hoory, Nathan Linial and Avi Wigderson

Journal: Bull. Amer. Math. Soc. 43 (2006), 439-561

DOI: https://doi.org/10.1090/S0273-0979-06-01126-8

$\endgroup$

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.