## Expanding Graphs: Proceedings of a DIMACS Workshop, May 11-14, 1992This volume contains the proceedings of the DIMACS Workshop on Expander Graphs, held at Princeton University in May 1992. The subject of expanding graphs involves a number of different fields and gives rise to important connections among them. Many of these fields were represented at the workshop, including theoretical computer science, combinatorics, probability theory, representation theory, number theory, and differential geometry. With twenty-two talks and two open problem sessions, the workshop provided a unique opportunity for cross-fertilization of various areas. This volume will prove useful to mathematicians and computer scientists interested in current results in this area of research. |

### What people are saying - Write a review

We haven't found any reviews in the usual places.

### Contents

Spectral Geometry and the Cheeger Constant | 5 |

The Laplacian of a Hypergraph | 21 |

Uniform Sampling Modulo a Group of Symmetries Using Markov Chain | 37 |

On the Second Eigenvalue and Linear Expansion of Regular Graphs | 49 |

Numerical Investigation of the Spectrum for Certain Families of Cayley | 63 |

Some Algebraic Constructions of Dense Graphs of Large Girth and | 75 |

Groups and Expanders | 95 |

Ramanujan Graphs and Diagrams Function Field Approach | 111 |

Highly Expanding Graphs Obtained from Dihedral Groups | 117 |

Are Finite Upper Half Plane Graphs Ramanujan? | 125 |

### Common terms and phrases

2-graph adjacency matrix algebra algorithm amenable group analog asymptotic automorphisms bipartite graph Cagleg Cayley graphs Cheeger constant combinatorial Computer Science Volume conjecture consider corresponding cosets d-regular defined degree denote dense diagram diameter discrete series edge eigenvalues elements example expander family expander graphs explicit construction F. R. K. Chung fc-graph fc-regular graph finite field finite groups finite index Fourier geometry girth graph G group G groups with property hypergraphs implies incidence graph incidence structure infinite family integer irreducible representations isomorphic isospectral Laplacian largest eigenvalue lattice Lemma Let F Let G linear lower bound Lubotzky Markov chain Math n-gon nodes orbits permutation group polynomial prime power principal series problem proof proposition prove quotient Ramanujan graphs regular graph result Sarnak satisfies second eigenvalue Section spectral value spectrum spherical functions subgraph subgroup subset symmetric space Theorem 3.1 Theoretical Computer Science theory upper half plane vertex vertices