EXPANDER GRAPHS AND THEIR APPLICATIONS 443 10.1.2.Lossless expanders 517 10.2.The construction 517 10.2.1.The zig-zag product for conductors 518 10.2.2.Proof of the main theorem 519 10.2.3.Final comments 522 11.Cayley expander graphs 522 11.1.Representations of finite groups 525 11.1.1.Representations and irreducible representations 526 11.1.2.Schreier graphs 528 11.1.3.Kazhdan constant and expansion of Cayley graphs 529 11.2.The replacement product and semidirect product 531 11.3. Constructing expander families by iterated semidirect products 533 11.3.1.Cayley expanders from group rings 533 11.3.2.Cayley expanders from iterated wreath products 534 11.4.Expansion is not a group property 535 11.5.Hypercontractive inequalities in groups? 536 12.Error correcting codes 536 12.1.Definition of error correcting codes 537 12.2. Linear codes 538 12.3.Asymptotic bounds 538 12.3.1.Lower bounds on size:The Gilbert-Varshamov bound 538 12.3.2.Upper bounds:Sphere packing and linear programming 539 12.4. Codes from graphs 540 12.5. Efficient asymptotically good codes from lossless expanders 541 13.Metric embedding 543 13.1. Basic definitions 543 13.2. Finding the minimal l2 distortion 544 13.3.Distortion bounds via semidefinite duality 546 13.3.1. Embedding the cube into l2 546 13.3.2.Embedding expander graphs into l2 547 13.4.Algorithms for cut problems via embeddings 548 13.5.A glimpse into the bigger picture 551 About the authors 551 References 552 Index 560 1.The magical mystery tour We begin our discussion with three fundamental problems from three different domains.At first sight these problems seem to have very little to do with expander graphs,or even graph theory,but as we shall see,they can all be solved using expander graphs.EXPANDER GRAPHS AND THEIR APPLICATIONS 443 10.1.2. Lossless expanders 517 10.2. The construction 517 10.2.1. The zig-zag product for conductors 518 10.2.2. Proof of the main theorem 519 10.2.3. Final comments 522 11. Cayley expander graphs 522 11.1. Representations of finite groups 525 11.1.1. Representations and irreducible representations 526 11.1.2. Schreier graphs 528 11.1.3. Kazhdan constant and expansion of Cayley graphs 529 11.2. The replacement product and semidirect product 531 11.3. Constructing expander families by iterated semidirect products 533 11.3.1. Cayley expanders from group rings 533 11.3.2. Cayley expanders from iterated wreath products 534 11.4. Expansion is not a group property 535 11.5. Hypercontractive inequalities in groups? 536 12. Error correcting codes 536 12.1. Definition of error correcting codes 537 12.2. Linear codes 538 12.3. Asymptotic bounds 538 12.3.1. Lower bounds on size: The Gilbert-Varshamov bound 538 12.3.2. Upper bounds: Sphere packing and linear programming 539 12.4. Codes from graphs 540 12.5. Efficient asymptotically good codes from lossless expanders 541 13. Metric embedding 543 13.1. Basic definitions 543 13.2. Finding the minimal l2 distortion 544 13.3. Distortion bounds via semidefinite duality 546 13.3.1. Embedding the cube into l2 546 13.3.2. Embedding expander graphs into l2 547 13.4. Algorithms for cut problems via embeddings 548 13.5. A glimpse into the bigger picture 551 About the authors 551 References 552 Index 560 1. The magical mystery tour We begin our discussion with three fundamental problems from three different domains. At first sight these problems seem to have very little to do with expander graphs, or even graph theory, but as we shall see, they can all be solved using expander graphs