Expander families and Cayley graphs : a beginner's guide
 Responsibility
 Mike Krebs and Anthony Shaheen.
 Language
 English.
 Imprint
 Oxford ; New York : Oxford University Press, c2011.
 Physical description
 xxiv, 258 p. : ill. ; 25 cm.
Access
Available online
Math & Statistics Library
Stacks
Call number  Status 

QA166.145 .K74 2011  Unknown 
More options
Creators/Contributors
 Author/Creator
 Krebs, Mike.
 Contributor
 Shaheen, Anthony.
Contents/Summary
 Bibliography
 Includes bibliographical references (p. [247]252) and index.
 Contents

 Preface  Notations and conventions  Introduction  Part 1. Basics  Chapter 1. Graph eigenvalues and the isoperimetric constant  Chapter 2. Subgroups and quotients  Chapter 3. The AlonBoppana theorem  Part 2. Combinatorial techniques  Chapter 4. Diameters of Cayley graphs and expander families  Chapter 5. Zigzag products  Part 3. Representationtheoretic techniques  Chapter 6. Representations of Finite Groups  Chapter 7. Representation theory and eigenvalues of Cayley graphs  Chapter 8. Kazhdan constants  Appendix A. Linear algebra  Appendix B. Asymptotic analysis of functions  Bibliography  Index.
 (source: Nielsen Book Data)
 Publisher's 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 Guide provides 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 bestcase growth rates. Topics include graph spectra (i.e., eigenvalues); a CheegerBusertype inequality for regular graphs; group quotients and graph coverings; subgroups and Schreier generators; the AlonBoppana theorem on the second largest eigenvalue of a regular graph; Ramanujan graphs; diameter estimates for Cayley graphs; the zigzag 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 fieldtested 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.
(source: Nielsen Book Data)
Subjects
Bibliographic information
 Publication date
 2011
 ISBN
 9780199767113 (hbk. : acidfree paper)
 0199767114 (hbk. : acidfree paper)