Ebook: Expander Families and Cayley Graphs. A Beginners Guide

Издательство Oxford University Press, 2011, -283 pp.
This book provides an introduction to the mathematical theory of expander families. It is intended for advanced undergraduates, graduate students, and faculty.
The prerequisites for this book are as follows. No graph theory is assumed; we develop it all from scratch. One course on introductory undergraduate group theory is assumed. One course on linear algebra is assumed. We provide Appendix A as a refresher on linear algebra for those who need it. In particular, those who are reading the book should either know the spectral theorem (Theorem A.53) or be willing to take it for granted. With these parameters, the book is self-contained. Analysis is helpful but not necessary; we occasionally encounter statements of the form For all ε GT 0, there exists N such that if n>N, then . Appendix B gives a review of big oh notation and the limit inferior of a sequence. This appendix uses the definition of the limit of a sequence. At one point in Chapter 8, we use the fact that a continuous function obtains its maximum on a compact subset of Cⁿ. In Section 6 of Chapter 7, we use the fact that the multiplicative subgroup of the set of integers modulo a prime is cyclic.Introduction.
Part One. Basics.
Graph eigenvalues and the isoperimetric constant.
Subgroups and quotients.
The Alon-Boppana theorem.
Part Two. Combinatorial Techniques.
Diameters of Cayley graphs and expander families.
Zig-zag products.
Part Three. Representation-Theoretic Techniques.
Representations of finite groups.
Representation theory and eigenvalues of Cayley graphs.
Kazhdan constants.