Expander Families and Cayley Graphs

A Beginner's Guide
Erscheinungsjahr 2011
ISBN: 978-0-19-976711-3
Verlag: Oxford University Press

Buch, Englisch, 288 Seiten, Format (B × H): 239 mm x 163 mm, Gewicht: 539 g

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.

The central notion in the book is that of expansion, which roughly means the quality of a graph as a communications network. Cayley graphs are certain graphs constructed from groups; they play a prominent role in the study of expander families. The isoperimetric constant, the second largest eigenvalue, the diameter, and the Kazhdan constant are four measures of the expansion quality of a Cayley graph. The book carefully develops these concepts, discussing their relationships to one another and to subgroups and quotients as well as their best-case growth rates.

Topics include graph spectra (i.e., eigenvalues); a Cheeger-Buser-type inequality for regular graphs; group quotients and graph coverings; subgroups and Schreier generators; the Alon-Boppana theorem on the second largest eigenvalue of a regular graph; Ramanujan graphs; diameter estimates for Cayley graphs; the zig-zag product and its relation to semidirect products of groups; eigenvalues of Cayley graphs; Paley graphs; and Kazhdan constants.

The book was written with undergraduate math majors in mind; indeed, several dozen of them field-tested it. The prerequisites are minimal: one course in linear algebra, and one course in group theory. No background in graph theory or representation theory is assumed; the book develops from scatch the required facts from these fields. The authors include not only overviews and quick capsule summaries of key concepts, but also details of potentially confusing lines of reasoning.

The book contains ideas for student research projects (for capstone projects, REUs, etc.), exercises (both easy and hard), and extensive notes with references to the literature.

Zielgruppe

Undergraduate students, graduate students, and faculty in mathematics

Autoren/Hrsg.

Krebs, Mike

Shaheen, Anthony

Fachgebiete

• Mathematik | Informatik Mathematik Operations Research Graphentheorie
• Mathematik | Informatik Mathematik Algebra Algebraische Strukturen, Gruppentheorie
• Mathematik | Informatik Mathematik Mathematik Allgemein Diskrete Mathematik, Kombinatorik

Inhaltsverzeichnis

- 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

Über Autor(innen)

Krebs, Mike
Mike Krebs, Assistant Professor of Mathematics, California State University, Los Angeles

Mike Krebs and Anthony Shaheen are faculty in the mathematics department at California State University, Los Angeles (CSULA) and are the authors of numerous publications on various subjects. They have developed and taught a course using a draft of their book for a text, and they have conducted many student research projects on expander families.

Shaheen, Anthony
Anthony Shaheen, Assistant Professor of Mathematics, California State University, Los Angeles

Mike Krebs and Anthony Shaheen are faculty in the mathematics department at California State University, Los Angeles (CSULA) and are the authors of numerous publications on various subjects. They have developed and taught a course using a draft of their book for a text, and they have conducted many student research projects on expander families.

Mike Krebs and Anthony Shaheen are faculty in the mathematics department at California State University, Los Angeles (CSULA) and are the authors of numerous publications on various subjects. They have developed and taught a course using a draft of their book for a text, and they have conducted many student research projects on expander families.