Description 
1 online resource (xxiv, 258 pages) : illustrations 
Contents 
Cover; Contents; Preface; Notations and conventions; Introduction; 1. What is an expander family?; 2. What is a Cayley graph?; 3. A tale of four invariants; 4. Applications of expander families; PART ONE: Basics; 1. Graph eigenvalues and the isoperimetric constant; 1. Basic definitions from graph theory; 2. Cayley graphs; 3. The adjacency operator; 4. Eigenvalues of regular graphs; 5. The Laplacian; 6. The isoperimetric constant; 7. The RayleighRitz theorem; 8. Powers and products of adjacency matrices; 9. An upper bound on the isoperimetric constant; Notes; Exercises 
Summary 
"The theory of expander graphs is a rapidly developing topic in mathematics and computer science, with applications to communication networks, errorcorrecting 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 networkthe isoperimetric constant, the secondlargest 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 CheegerBusertype inequality for regular graphs · Group quotients and graph coverings · Subgroups and Schreier generators · Ramanujan graphs and the AlonBoppana theorem · The zigzag product and its relation to semidirect products of groups · Representation theory and eigenvalues of Cayley graphs · Kazhdan constants The 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" Provided by publisher 

"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" Provided by publisher 
Bibliography 
Includes bibliographical references (pages 247252) and index 
Notes 
Print version record 
Subject 
Cayley graphs.


Eigenvalues.


Cayley algebras.


MATHEMATICS  Graphic Methods.


Cayley algebras


Cayley graphs


Eigenvalues

Form 
Electronic book

Author 
Shaheen, Anthony

ISBN 
9780199877485 

0199877483 

9781283427807 

128342780X 
