I am looking for a book that covers expander graphs rigorously. Preferably a book aimed at beginners.
$\begingroup$
$\endgroup$
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
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
$\begingroup$
$\endgroup$
1
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.
answered May 12, 2021 at 6:46
-
$\begingroup$ Sarnak also has an earlier book called "Applications of Modular Forms" which could also complement the reference mentioned above. $\endgroup$ Commented May 12, 2021 at 17:10
$\begingroup$
$\endgroup$
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...
$\begingroup$
$\endgroup$
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
