Friday, May 16, 2008
3:30 pm, MC 5158

Tutte Seminar Series
Combinatorics & Optimization
Spring 2008


Noga Alon
Tel Aviv University

Expanders, Universal Graphs and Disjoint Paths

The tight connection between the eigenvalues of a graph and its combinatorial properties leads to most of the interesting combinatorial and algorithmic applications of expanders. I will illustrate this phenomenon by sketching two recent applications of expanders obtained jointly with Michael Capalbo: the construction of sparse universal graphs and the design of an efficient algorithm for finding edge disjoint paths in expanders deterministically and online.