The University of Michigan Combinatorics Seminar


Abstract 

An (n,d,\lambda)graph is a dregular graph on n vertices so that the absolute value of each eigenvalue of its adjacency matrix, besides the largest one, is at most \lambda. I will survey some of the remarkable pseudorandom properties of such graphs in which \lambda is much smaller than d, describe various constructions, and present several applications of these graphs in the solution of problems in Extremal Combinatorics, Geometry and Complexity. 