Overview

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 both comprehend 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 and answers 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:· Graph spectra· A Cheeger-Buser-type inequality for regular graphs· Group quotients and graph coverings· Subgroups and Schreier generators· Ramanujan graphs and the Alon-Boppana theorem· The zig-zag product and its relation to semidirect products of groups· Representation theory and eigenvalues of Cayley graphs· 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 problems with 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.

Full Product Details

Author:   Mike Krebs (Assistant Professor of Mathematics, Assistant Professor of Mathematics, California State University, Los Angeles) ,  Anthony Shaheen (Assistant Professor of Mathematics, Assistant Professor of Mathematics, California State University, Los Angeles)
Publisher:   Oxford University Press Inc
Imprint:   Oxford University Press Inc
Dimensions:   Width: 23.90cm , Height: 2.00cm , Length: 16.30cm
Weight:   0.539kg
ISBN:  

9780199767113

ISBN 10:   0199767114
Pages:   288
Publication Date:   17 November 2011
Audience:   College/higher education ,  Undergraduate
Format:   Hardback
Publisher's Status:   Active
Availability:   Manufactured on demand  
We will order this item for you from a manufactured on demand supplier.

Table of 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 Alon-Boppana theorem Part 2. Combinatorial techniques Chapter 4. Diameters of Cayley graphs and expander families Chapter 5. Zig-zag products Part 3. Representation-theoretic 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

Reviews

Author Information

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.

Tab Content 6

Author Website:  

Customer Reviews

Recent Reviews

No review item found!

Add your own review!

Countries Available

All regions