The University of Michigan Combinatorics Seminar
Fall 2006
December 1, 4:10-5:00, 3866 East Hall

Pseudo-random graphs: properties and applications

Benny Sudakov

Princeton University


An (n,d,\lambda)-graph is a d-regular 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 pseudo-random 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.