##### Department of Mathematics,

University of California San Diego

****************************

### Math 295 - Mathematics Colloquium

## Benny Sudakov

#### Princeton University \\ (Hiring Candidate)

## 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 and Complexity.

Host: Fan Chung Graham

### October 12, 2006

### 4:00 PM

### AP&M 6402

****************************