DIMACS Series in
Discrete Mathematics and Theoretical Computer Science

VOLUME TEN
TITLE: "EXPANDING GRAPHS"
EDITORS: Joel Friedman
Published by the American Mathematical Society

Ordering Information

This volume may be obtained from the AMS or through bookstores in your area.

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.

PREFACE

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.

TABLE OF CONTENTS



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 Index of Volumes
DIMACS Homepage
Contacting the Center
Document last modified on October 28, 1998.