LEADER 05391nam 2200673Ia 450 001 9910457774803321 005 20200520144314.0 010 $a1-283-42780-X 010 $a9786613427809 010 $a0-19-987748-3 035 $a(CKB)2550000000079359 035 $a(EBL)845893 035 $a(OCoLC)773937205 035 $a(SSID)ssj0000590278 035 $a(PQKBManifestationID)12290863 035 $a(PQKBTitleCode)TC0000590278 035 $a(PQKBWorkID)10665565 035 $a(PQKB)10084828 035 $a(MiAaPQ)EBC845893 035 $a(Au-PeEL)EBL845893 035 $a(CaPaEBR)ebr10524954 035 $a(CaONFJC)MIL342780 035 $a(EXLCZ)992550000000079359 100 $a20110811d2011 uy 0 101 0 $aeng 135 $aur|n|---||||| 181 $ctxt 182 $cc 183 $acr 200 10$aExpander families and Cayley graphs$b[electronic resource] $ea beginner's guide /$fMike Krebs and Anthony Shaheen 210 $aOxford ;$aNew York $cOxford University Press$dc2011 215 $a1 online resource (283 p.) 300 $aDescription based upon print version of record. 311 $a0-19-976711-4 320 $aIncludes bibliographical references (p. [247]-252) and index. 327 $aCover; 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 327 $a2. 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 327 $a4. 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 327 $a2. 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 327 $a1. 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 327 $a2. Limit inferior of a function 330 $aThe 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 606 $aCayley graphs 606 $aEigenvalues 606 $aCayley algebras 608 $aElectronic books. 615 0$aCayley graphs. 615 0$aEigenvalues. 615 0$aCayley algebras. 676 $a511/.5 700 $aKrebs$b Mike$0977915 701 $aShaheen$b Anthony$0977916 801 0$bMiAaPQ 801 1$bMiAaPQ 801 2$bMiAaPQ 906 $aBOOK 912 $a9910457774803321 996 $aExpander families and Cayley graphs$92227869 997 $aUNINA