Discrete Mathematics and Theoretical Computer Science

TITLE: "EXPANDING GRAPHS"

EDITORS: Joel Friedman

Published by the American Mathematical Society

To order through AMS contact the AMS Customer Services Department, P.O. Box 6248, Providence, Rhode Island 02940-6248 USA. For Visa, Mastercard, Discover, and American Express orders call 1-800-321-4AMS.

You may also visit the
AMS Bookstore and
order directly from there.
DIMACS ** does not** distribute or sell these books.

The DIMACS Workshop on Expander Graphs took place at Princeton University, May 11-14, 1992. There were 70 participants. The program featured 22 talks and two open problem sessions. This volume contains much of the material covered at this workshop, in the form of unrefereed papers or summaries of the talks.

The field of expanding graphs involves a number of different field of study, and gives rise to important connections between them. We were happy to have many of these fields represented at the workshop, including theoretical computer science, combinatorics, probability theory, representation theory, number theory, and differential geometry; the workshop was a wonderful opportunity to assemble researchers and topics with a diversity not usually found in more regular conferences and meetings. We received many positive responses >from the participants of the workshop.

We would like to thank the DIMACS executive committee for sponsoring the workshop. Fan Chung, Daniel Gorenstein, Fred Roberts, Bob Tarjan, Tom Trotter, Pat Toci, Carol Rusnak, Adam Buchsbaum, and Ramesh Sitaraman all helped us greatly. We regret the untimely passing of Daniel Gorenstein, whose energies greatly contributed to DIMACS in many ways. Winnie Waring was of especial help in organizing the workshop. Persi Diaconis helped with the proposal for the workshop. We also wish to thank Christine Thivierge and Donna Harmon at the AMS for helping to prepare this volume.

Foreword vii Preface ix Random Cayley Graphs and Expanders (Abstract) Noga Alon and Yuval Roichman 1 Spectral Geometry and the Cheeger Constant Robert Brooks 5 The Laplacian of a Hypergraph Fan R.K. Chung 21 Uniform Sampling Modulo a Group of Symmetries Using Markov Chain Simulation Mark Jerrum 37 On the Second Eigenvalue and Linear Expansion of Regular Graphs Nabil Kahale 49 Numerical Investigation of the Spectrum for Certain Families of Cayley Graphs John Lafferty and Daniel Rockmore 63 Some Algebraic Constructions of Dense Graphs of Large Girth and of Large Size Felix Lazebnik and Vasiliy A. Ustimenko 75 Groups and Expanders A. Lubotzky and B. Weiss 95 Ramanujan Graphs and Diagrams Function Field Approach Moshe Morgenstern 111 Highly Expanding Graphs Obtained from Dihedral Groups Holger Schellwat 117 Are Finite Upper Half Plane Graphs Ramanujan? Audrey Terras 125

Index of Volumes

DIMACS Homepage

Contacting the Center

Document last modified on October 28, 1998.