|
Friday, May 16, 2008 |
|
|
|
|
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. |