Expander Families and Cayley Graphs: A Beginners Guide

Hardcover | November 4, 2011

byMike Krebs, Anthony Shaheen

not yet rated|write a review
The theory of expander graphs is a rapidly developing topic in mathematics and computer science, with applications to communication networks, error-correcting codes, cryptography, complexity theory, and much more. Expander Families and Cayley Graphs: A Beginner's Guide is a comprehensive introduction to expander graphs, designed to act as a bridge between classroom study and active research in the field of expanders. It equips those with little or no prior knowledge with the skills necessary to bothcomprehend current research articles and begin their own research. Central to this book are four invariants that measure the quality of a Cayley graph as a communications network-the isoperimetric constant, the second-largest eigenvalue, the diameter, and the Kazhdan constant. The book poses andanswers three core questions: How do these invariants relate to one another? How do they relate to subgroups and quotients? What are their optimal values/growth rates? Chapters cover topics such as:DT Graph spectraDT A Cheeger-Buser-type inequality for regular graphsDT Group quotients and graph coveringsDT Subgroups and Schreier generatorsDT Ramanujan graphs and the Alon-Boppana theoremDT The zig-zag product and its relation to semidirect products of groupsDT Representation theory and eigenvalues of Cayley graphsDT Kazhdan constantsThe only introductory text on this topic suitable for both undergraduate and graduate students, Expander Families and Cayley Graphs requires only one course in linear algebra and one in group theory. No background in graph theory or representation theory is assumed. Examples and practice problemswith varying complexity are included, along with detailed notes on research articles that have appeared in the literature. Many chapters end with suggested research topics that are ideal for student projects.

Pricing and Purchase Info

$104.50

Ships within 1-3 weeks
Ships free on orders over $25

From the Publisher

The theory of expander graphs is a rapidly developing topic in mathematics and computer science, with applications to communication networks, error-correcting codes, cryptography, complexity theory, and much more. Expander Families and Cayley Graphs: A Beginner's Guide is a comprehensive introduction to expander graphs, designed to act...

Mike Krebs 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.
Format:HardcoverDimensions:288 pages, 0.12 × 0.12 × 0.12 inPublished:November 4, 2011Publisher:Oxford University PressLanguage:English

The following ISBNs are associated with this title:

ISBN - 10:0199767114

ISBN - 13:9780199767113

Customer Reviews of Expander Families and Cayley Graphs: A Beginners Guide

Reviews

Extra Content

Table of Contents

PrefaceNotations and conventionsIntroductionPart 1. Basics1. Graph eigenvalues and the isoperimetric constant2. Subgroups and quotients3. The Alon-Boppana theoremPart 2. Combinatorial techniques4. Diameters of Cayley graphs and expander families5. Zig-zag productsPart 3. Representation-theoretic techniques6. Representations of Finite Groups7. Representation theory and eigenvalues of Cayley graphs8. Kazhdan constantsAppendix A. Linear algebraAppendix B. Asymptotic analysis of functionsBibliographyIndex