On the Second Eigenvalue of Hypergraphs
Report ID: TR-232-89Author: Friedman, Joel / Wigderson, Avi
Date: 1989-11-00
Pages: 26
Download Formats: |PDF|
Abstract:
We define a notion of second eigenvalue for regular hypergraphs. It turns out that a random hypergraph has a very small second eigenvalue. A class of applications of graphs with small second eigenvalue would be greatly improved if we could explicity construct hypergraphs with as small a second eigenvalue as random ones have. Unfortunately we have no such constructions as yet. In this paper we define the second eigenvalue, discuss the second eigenvalue of random hypergraphs, discuss some constructions and applications.