Departmental Colloquium
Benny Sudakov
Princeton
Pseudo-random graphs: properties and applications
Abstract: 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.
Friday March 23, 2007 at 3:00 PM in SEO 636