Expanders, Universal Graphs and Disjoint Paths
|Affiliation:||Tel Aviv University|
|Room:||Mathematics & Computer Building (MC) 5158|
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.
200 University Avenue West
Waterloo, ON N2L 3G1