Friday, May 16, 2008 3:30 pm
-
4:30 pm
EDT (GMT -04:00)
Expanders, Universal Graphs and Disjoint Paths
Speaker: | Noga Alon |
---|---|
Affiliation: | Tel Aviv University |
Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
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.