Title: Expander graphs and applications of graph theory
Speaker: Robert DeMarco, Rutgers University
Date: Wednesday, March 3, 2010 12:10pm
Location: Graduate Student Lounge, 7th Floor, Hill Center, Rutgers University, Busch Campus, Piscataway, NJ
Expander graphs are sparse regular graphs which, as one might expect, "expand" well. More mathematically, but still not precisely, these are graphs in which the neighborhood of any set of vertices is sufficiently large relative to the size of the initial set. The applications of such graphs to Monte Carlo algorithms (e.g. primality testing) will be discussed. In doing so we will discuss the relationship between the spectral properties of a graph and it's expanding properties, and discuss the extension of such ideas to quasi-random graphs. This talk will mostly follow much of the material from Alon-Spencer 9.2