Expander families and Cayley graphs [[electronic resource] ] : a beginner's guide / / Mike Krebs and Anthony Shaheen

• Autore: Krebs Mike
• Pubblicazione: Oxford ; ; New York, : Oxford University Press, c2011
• Descrizione fisica: 1 online resource (283 p.)
• Disciplina: 511/.5
• Soggetto topico: Cayley graphs; Eigenvalues; Cayley algebras
• Soggetto genere / forma: Electronic books.
• Altri autori: ShaheenAnthony
• Note generali: Description based upon print version of record.
• Nota di bibliografia: Includes bibliographical references (p. [247]-252) and index.
• Nota di contenuto: 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 Rayleigh-Ritz theorem; 8. Powers and products of adjacency matrices; 9. An upper bound on the isoperimetric constant; Notes; Exercises ; 2. Subgroups and quotients1. Coverings and quotients; 2. Subgroups and Schreier generators; Notes; Exercises; Student research project ideas; 3. The Alon-Boppana theorem; 1. Statement and consequences; 2. First proof: The Rayleigh-Ritz method; 3. Second proof: The trace method; Notes; Exercises; Student research project ideas; PART TWO: Combinatorial Techniques; 4. Diameters of Cayley graphs and expander families; 1. Expander families have logarithmic diameter; 2. Diameters of Cayley graphs; 3. Abelian groups never yield expander families: A combinatorial proof ; 4. Diameters of subgroups and quotients5. Solvable groups with bounded derived length; 6. Semidirect products and wreath products; 7. Cube-connected cycle graphs; Notes; Exercises; Student research project ideas; 5. Zig-zag products; 1. Definition of the zig-zag product; 2. Adjacency matrices and zig-zag products; 3. Eigenvalues of zig-zag products; 4. An actual expander family; 5. Zig-zag products and semidirect products; Notes; Exercises; Student research project ideas; PART THREE: Representation-Theoretic Techniques; 6. Representations of finite groups; 1. Representations of finite groups ; 2. Decomposing representations into irreducible representations3. Schur's lemma and characters of representations; 4. Decomposition of the right regular representation; 5. Uniqueness of invariant inner products; 6. Induced representations; Note; Exercises; 7. Representation theory and eigenvalues of Cayley graphs; 1. Decomposing the adjacency operator into irreps; 2. Unions of conjugacy classes; 3. An upper bound on ?(X); 4. Eigenvalues of Cayley graphs on abelian groups; 5. Eigenvalues of Cayley graphs on dihedral groups; 6. Paley graphs; Notes; Exercises; 8. Kazhdan constants ; 1. Kazhdan constant basics2. The Kazhdan constant, the isoperimetric constant, and the spectral gap; 3. Abelian groups never yield expander families: A representation-theoretic proof; 4. Kazhdan constants, subgroups, and quotients; Notes; Exercises; Student research project ideas; Appendix A: Linear algebra; 1. Dimension of a vector space; 2. Inner product spaces, direct sum of subspaces; 3. The matrix of a linear transformation; 4. Eigenvalues of linear transformations; 5. Eigenvalues of circulant matrices; Appendix B: Asymptotic analysis of functions; 1. Big oh ; 2. Limit inferior of a function
• Sommario/riassunto: 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 fou
• Titolo autorizzato: Expander families and Cayley graphs
• ISBN: 1-283-42780-X; 9786613427809; 0-19-987748-3
• Formato: Materiale a stampa
• Livello bibliografico: Monografia
• Lingua di pubblicazione: Inglese
• Record Nr.: 9910457774803321
• Lo trovi qui: Univ. Federico II