Expander Families and Cayley Graphs A Beginner's Guide

by Krebs, Mike; Shaheen, Anthony

• ISBN13: 9780199767113
• ISBN10: 0199767114
• Format: Hardcover
• Copyright: 2011-10-21
• Publisher: Oxford University Press

Summary

Expander families enjoy a wide range of applications in mathematics and computer science, and their study is a fascinating one in its own right.Expander Families and Cayley Graphs: A Beginner's Guideprovides an introduction to the mathematical theory underlying these objects. The central notion in the book is that of expansion, which roughly means the quality of a graph as a communications network. Cayley graphs are certain graphs constructed from groups; they play a prominent role in the study of expander families. The isoperimetric constant, the second largest eigenvalue, the diameter, and the Kazhdan constant are four measures of the expansion quality of a Cayley graph. The book carefully develops these concepts, discussing their relationships to one another and to subgroups and quotients as well as their best-case growth rates. Topics include graph spectra (i.e., eigenvalues); a Cheeger-Buser-type inequality for regular graphs; group quotients and graph coverings; subgroups and Schreier generators; the Alon-Boppana theorem on the second largest eigenvalue of a regular graph; Ramanujan graphs; diameter estimates for Cayley graphs; the zig-zag product and its relation to semidirect products of groups; eigenvalues of Cayley graphs; Paley graphs; and Kazhdan constants. The book was written with undergraduate math majors in mind; indeed, several dozen of them field-tested it. The prerequisites are minimal: one course in linear algebra, and one course in group theory. No background in graph theory or representation theory is assumed; the book develops from scatch the required facts from these fields. The authors include not only overviews and quick capsule summaries of key concepts, but also details of potentially confusing lines of reasoning. The book contains ideas for student research projects (for capstone projects, REUs, etc.), exercises (both easy and hard), and extensive notes with references to the literature.

Author Biography

Mike Kerbs and Anthony Shaheen are faculty in the mathematics department at California State University, Los Angeles (CSULA). They have developed and taught a course using a draft of this book for a text and have conducted many student research projects on expander families.

Table of Contents

Preface	p. ix
Notations and conventions	p. xi
Introduction	p. xiii
What is an expander family?	p. xiii
What is a Cayley graph?	p. xviii
A tale of four invariants	p. xix
Applications of expander families	p. xxii
Basics
Graph eigenvalues and the isoperimetric constant	p. 3
Basic definitions from graph theory	p. 3
Cayley graphs	p. 8
The adjacency operator	p. 10
Eigenvalues of regular graphs	p. 15
The Laplacian	p. 20
The isoperimetric constant	p. 24
The Rayleigh-Ritz theorem	p. 29
Powers and products of adjacency matrices	p. 35
An upper bound on the isoperimetric constant	p. 37
Notes	p. 42
Exercises	p. 45
Subgroups and quotients	p. 49
Coverings and quotients	p. 49
Subgroups and Schreier generators	p. 57
Notes	p. 64
Exercises	p. 65
Student research project ideas	p. 66
The Alon-Boppana theorem	p. 67
Statement and consequences	p. 67
First proof: The Rayleigh-Ritz method	p. 71
Second proof: The trace method	p. 76
Notes	p. 88
Exercises	p. 91
Student research project ideas	p. 92
Combinatorial Techniques
Diameters of Cayley graphs and expander families	p. 5
Expander families have logarithmic diameter	p. 95
Diameters of Cayley graphs	p. 99
Abelian groups never yield expander families: A combinatorial proof	p. 102
Diameters of subgroups and quotients	p. 105
Solvable groups with bounded derived length	p. 108
Semidirect products and wreath products	p. 110
Cube-connected cycle graphs	p. 112
Notes	p. 116
Exercises	p. 117
Student research project ideas	p. 118
Zig-zag products	p. 120
Definition of the zig-zag product	p. 121
Adjacencymatrices and zig-zag products	p. 125
Eigenvalues of zig-zag products	p. 129
An actual expander family	p. 132
Zig-zag products and semidirect products	p. 136
Notes	p. 138
Exercises	p. 138
Student research project ideas	p. 139
Representation-Theoretic Techniques
Representations of finite groups	p. 143
Representations of finite groups	p. 143
Decomposing representations into irreducible representations	p. 152
Schur's lemma and characters of representations	p. 159
Decomposition of the right regular representation	p. 171
Uniqueness of invariant inner products	p. 174
Induced representations	p. 176
Note	p. 182
Exercises	p. 182
Representation theory and eigenvalues of Cayley graphs	p. 185
Decomposing the adjacency operator into irreps	p. 185
Unions of conjugacy classes	p. 188
An upper bound on ¿(X)	p. 190
Eigenvalues of Cayley graphs on abelian groups	p. 192
Eigenvalues of Cayley graphs on dihedral groups	p. 194
Paley graphs	p. 198
Notes	p. 203
Exercises	p. 206
Kazhdan constants	p. 209
Kazhdan constant basics	p. 209
The Kazhdan constant, the isoperimetric constant, and the spectral gap	p. 217
Abelian groups never yield expander families: A representation-theoretic proof	p. 222
Kazhdan constants, subgroups, and quotients	p. 224
Notes	p. 227
Exercises	p. 228
Student research project ideas	p. 228
Linear algebra	p. 229
Dimension of a vectorspace	p. 229
Inner product spaces, direct sum of subspaces	p. 231
The matrix of a linear transformation	p. 235
Eigenvalues of linear transformations	p. 238
Eigenvalues of circulant matrices	p. 242
Asymptotic analysis of functions	p. 244
Big oh	p. 244
Limit inferior of a function	p. 245
References	p. 247
Index	p. 253
Table of Contents provided by Ingram. All Rights Reserved.