Benny Sudakov : Pseudo-random graphs: properties and applications

Posted by Dhruv Mubayi , part of the Departmental Colloquium.

At

March 23, 2007, 3 p.m.

In

SEO 636

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.